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) =...
user avatar
  • 34.4k
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 ...
user avatar
  • 361
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 ...
user avatar
  • 34.4k
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 ...
user avatar
  • 34.4k
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: ...
user avatar
  • 5,062
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 ...
user avatar
  • 34.4k
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 ...
user avatar
  • 111

Only top scored, non community-wiki answers of a minimum length are eligible