How do I show that uniform-cost search is a special case of A*? How do I prove this?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
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.