In the context of an A* search, a heuristic function is said to be admissible if it does not overestimate the cost to reach the goal. Such functions can also be viewed as being "optimistic".

When using an admissible heuristic, A* is \b[guaranteed to return a cost-optimal solution], i.e. the best path. Let's prove it by contradiction:

Assume that the algorithm returned a path, the cost of which is greater than that of the optimal path $P$. Let's call $C$ the cost of the path that was followed, and $C^*$ the cost of $P$, noting that $C^* < C$. First, we can safely assume that at least one node in $P$ was not expanded during the algorithm's execution (if all nodes of $P$ were expanded, then $P$ would have been chosen instead since that would lead to a lower path cost$^{[1]}$). Without loss of generallity, let's take the first occurance of such unexpanded node and name it "n". Let's call the \b[actual] cost from n to the destination $h^*(n)$ and define \b[$g^*(n)$] as the cost of the \b[optimal] path starting from the origin all the way to n. Remember that A* is a best-first search on the value of $f$, so $f(x) \geq C$ for all unexpanded nodes. Here's what we've got:

$
\small
f(n) \geq C > C^*, \text{ otherwise n would have been expanded} \newline
f(n) = g(n) + h(n), \text{ by definition} \newline
f(n) = g^*(n) + h(n), \text{ n is on an optimal path } \newline
f(n) \leq g^*(n) + h^*(n), \text{ since heuristic is optimistic } (\leq \text{actual cost) } \newline
$

Now note that $g^*(n) + h^*(n)$ is equal to "the cost to reach n following the optimal path" + "the cost to reach the goal starting from n, following the optimal path". That's just equal to the total cost of the optimal path! So, both $f(n) > C^*$ and $f(n) \leq C^*$ hold simultaneously which obviously constitutes a contradiction. $\square$

\[1\]: Remember than $h(n)$ (our heuristic) is just a hint to prioritize certain expansions over others. When everything is expanded however, $g(n)$ is the sole metric that will be considered, which will always lead to the optimal path being selected, that being $P$.


Petros Katiforis @kasoto 1