2
$\begingroup$

How do I show that uniform-cost search is a special case of A*? How do I prove this?

$\endgroup$
3
$\begingroup$

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 node. In the A* algorithm, $h(n)$ must be admissible.

UCS is a special case of A* which corresponds to having $h(n) = 0, \forall n$. A heuristic function $h$ which has $h(n) = 0$, $\forall n$, is clearly admissible, because it always "underestimates" the distance to the goal, which cannot be smaller than $0$, unless you have negative edges (but I assume that all edges are non-negative). So, indeed, UCS is a special case of A*, and its heuristic function is even admissible!

To see this with an example, just draw a simple graph, and apply the A* algorithm using $h(n) = 0$, for all $n$, and then apply UCS to the same graph. You will obtain the same results.

$\endgroup$
  • 2
    $\begingroup$ Nice answer :-) I would have left more to the OP to figure out $\endgroup$ – Martin Thoma Nov 26 '18 at 16:08

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.