5
$\begingroup$

In my AI lecture notes (also many other AI lectures) it's written that uniform cost search is optimal (that is, uniform search always outputs the optimal path), but what if the cost is negative, won't the search algorithm possibly trapped in infinite loops? If solution is using a closed set to track explored nodes, we will lose ability of reopening a node when less cost is seen, thus optimal might compromise.

$\endgroup$
  • 3
    $\begingroup$ Presumably it is only optimal given that some conditions hold. The lecture notes probably mention the conditions, and prove that the algorithm is optimal. $\endgroup$ – Yuval Filmus May 27 '17 at 15:16
6
$\begingroup$

In my AI lecture notes (also many other AI lectures) it's written that uniform cost search is optimal (that is, uniform search always outputs the optimal path)

Kinda. While it's true that the algorithm should output the optimal path, that's probably not what your notes were referring to. Rather, it's likely that they were making a claim about the algorithm itself being optimal in terms of performance.

A blog post, "Artificial Intelligence - Uniform Cost Search (UCS)", provides a claim like this:

Uniform Cost Search is the best algorithm for a search problem, which does not involve the use of heuristics. It can solve any general graph for optimal cost. Uniform Cost Search as it sounds searches in branches which are more or less the same in cost.

The logic behind this claim seems simple enough: you don't want to search down paths that can't be optimal, since that'd be wasteful, but you don't have any way of knowing which paths might be optimal in advance. So, by going down each equally, you don't assume any effective bias.

I'm not 100% if this is true in all cases in which this claim's made, but it seems like a useful tidbit to be aware of.

but what if the cost is negative, won't the search algorithm possibly trapped in infinite loops?

There can't be negative costs. If there are negative nodes, you'd have to modify the algorithm by removing its termination condition, effectively reducing it to a brute force search.

For example, consider using UCS and finding an apparently optimal path without having searched the entire space. Then, it turns out that there's a node that you didn't search that has a cost of $-{\infty}$. Presumably an optimal path should've gone through that node, but the search couldn't have found it since it terminated too soon.

Disclaimer about method names

Basic, widely known methods like this often have some variation in exactly how different sources define them or what name the method is given. For example, below I linked the relevant Wikipedia article, which calls it "Dijkstra's algorithm". The Wikipedia article discusses several different implementations.

Claims about algorithms with fuzzy definitions and frequently confused names should be taken with a grain of salt as there's plenty of room for miscommunication.

Further reading

Wikipedia's article on Dijkstra's algorithm would likely be helpful:

In some fields, artificial intelligence in particular, Dijkstra's algorithm or a variant of it is known as uniform-cost search and formulated as an instance of the more general idea of best-first search.

$\endgroup$
1
$\begingroup$

I had the same confusion. After reading the text I found that there was a condition. The condition was that every step cost should be positive. It can never be zero or negative. Only then the algorithm is optimal.

$\endgroup$
0
$\begingroup$

Nat already made it clear that the costs must be positive, but I'd just like to add that there's an additional condition and is that there must exist a cost $c^\prime$ such that $c^\prime \leq c$ for all other costs in your (possibly infinite) Graph, i.e. there must be some minimal positive cost. Think about it for a second, let's say there is a sequence of monotonically decreasing costs in your graph $G$ like $1, \frac{1}{2}, \frac{1}{4}, \ldots, \frac{1}{2^n}, \ldots$, if your goal $g$ is at a distance $3$ from the start then you may never reach it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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