6

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) = g(n) + h(n)$, where $g(n)$ means the same thing as in UCS and $h(n)$, called the "heuristic" function, is an estimate of the distance from $n$ to the goal ...


5

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 is $\frac{1}{4}$, the following is $\frac{1}{8}$, and so on forever. Every edge is greater than zero, meeting the condition being proposed in the question. ...


4

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$, while in the case of the greedy BFS it is $f(n) = h(n)$, where $h(n)$ is the heuristic function that estimates the cost of the path from $n$ to the goal node. ...


3

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 uniform-cost search (UCS) is $f(n) = g(n)$, where $g(n)$ represents the cost of the path from the start node to $n$. The evaluation function of A* is $f(n) = g(n)...


2

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 big enough, that solution is optimal) and it expands nodes with the smallest value of the evaluation function $f(n) = g(n)$, where $g(n)$ is the length/cost of ...


2

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: if not [contains(frontier, state) OR contains(explored, state)] then which is equivalent to your interpretation of if not [contains(frontier, state)] AND not [contains(explored, state)] ...


1

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 DA and UCS, so you should read this paper for all the details. DA and UCS are logically equivalent (i.e. they process the same vertices in the same order), but ...


1

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 is not a correct algorithm -- it is not guaranteed to output the optimal path. But it is possible to adjust the stopping condition to make bidirectional ...


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