7
votes
Accepted
How do I show that uniform-cost search is a special case of A*?
Yes, UCS is a special case of A*.
UCS uses the evaluation function $f(n) = g(n)$, where $g(n)$ is the length of the path from the starting node to $n$, whereas A* uses the evaluation function $f(n) =...
- 39.6k
6
votes
Accepted
Why is the completeness of UCS guaranteed only if the cost of every step exceeds some small positive constant?
Let's consider a problem where all edge costs are greater than zero, but not above some $\epsilon$:
Image a problem where we have an infinite path where the first edge is cost $\frac{1}{2}$, the next ...
- 371
4
votes
What are the differences between uniform-cost search and greedy best-first search?
In the case of UCS, the evaluation function (that is, the function that is used to select the next node to expand) is $f(n) = g(n)$, where $g(n)$ is the cost of the path from the initial node to $n$, ...
3
votes
Accepted
A* and uniform-cost search are apparently incomplete
You forgot to calculate and take into account the costs of the actual paths. You forgot to accumulate the cost of the edges for going forward and backward multiple times!
The evaluation function of ...
- 39.6k
2
votes
Accepted
If uniform cost search is used for bidirectional search, is it guaranteed the solution is optimal?
UCS is optimal (but not necessarily complete)
Let's first recall that the uniform-cost search (UCS) is optimal (i.e. if it finds a solution, which is not guaranteed unless the costs on the edges are ...
- 39.6k
2
votes
Accepted
Understanding the pseudocode of uniform-cost search from the book "Artificial Intelligence: A Modern Approach"
I think this is a problem with missing brackets in pseudocode — clearly the state is only added to the frontier if it hasn't been explored already, so it would be:
...
- 5,362
1
vote
Accepted
What is the difference between the uniform-cost search and Dijkstra's algorithm?
The answer to my question can be found in the paper Position Paper: Dijkstra's Algorithm versus Uniform Cost Search or a Case Against Dijkstra's Algorithm (2011), in particular section Similarities of ...
- 39.6k
1
vote
If uniform cost search is used for bidirectional search, is it guaranteed the solution is optimal?
It depends on the stopping condition. If the stopping condition is "stop as soon as any vertex is encountered by both the forward and backward scan", then bidirectional uniform-cost search ...
- 288
Only top scored, non community-wiki answers of a minimum length are eligible