4

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?

1 Answer 1

6

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.