Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Uniform cost search and completeness

Tags:

algorithm

In my AI textbook, the following has been said about uniform cost search:

Therefore, it will get stuck in an infinite loop if there is a path with an infinite sequence of zero-cost actions.

I understand this part.

However, it also mentions:

Completeness is guaranteed provided the cost of every step exceeds some small positive constant.

I don't understand how the positive constant helps. Even if this condition was satisfied, an infinite path would still cause the algorithm to not find a possible solution.

Could someone explain this part?

like image 860
Cam Avatar asked Nov 06 '25 12:11

Cam


1 Answers

Because those small constants will eventually add up and in total become more than the cost to some node that does not continue that infinite path. At that point, the node continuing the infinite path will not be at the front of the priority queue, so some other node will be explored instead. After that, it may start exploring the infinite path again, but again the costs will add up until it loses to some other node in the queue.

like image 185
harold Avatar answered Nov 08 '25 11:11

harold



Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!