patternMinor
Is uniform cost search optimal?
Viewed 0 times
uniformcostoptimalsearch
Problem
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#75950, answer score: 7
Revisions (0)
No revisions yet.