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 the actual 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". By definition, $g(n)$ holds the least known cost to reach n starting from the origin. Let's name the \b[actual] cost from n to the destination $h^*(n)$ and define \b[$g^*(n)$] as the cost of the \b[optimal] path from our origin to n. Since all previous nodes of the optimal path have already been expanded, we know that $g(n) = g^*(n)$. Here's what we've got:

$
\small
f(n) = g(n) + h(n), \text{ by definition} \newline
f(n) = g^*(n) + h(n), \text{ explained above } \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! However, we know that $C^* < C$, so here's where the \b[contradiction] lies: If $f(n)$ really was less or equal to the length of the optimal path ($C^*$), then the A* algorithm would have expanded this node before trying to expand the destination since $f(destination) = C > f(n)$. A lower $f$ value would have always triggered an immediate expansion. $\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$.


Welcome to OurBigBook, and thanks for this article!

 Comments (0)

Welcome to OurBigBook, and thanks for this article!

 Comments (0)  Subscribe (1)

 Comments (0)