A* admissibility

This notes elaborates on Admissibility in $A^{*}$ and answers the question of

Why does admissibility guarantee optimality

We know that admissibility means that $$h(n) \leq \pu{True cost from goal}$$
But why does this imply that the algorithm will always end up finding the optimal path to goal vertex?

Let us prove this rigorously using a proof by contradiction. Assume the algorithm has just returned a suboptimal goal node—let us call it $G_{b a d}$ —instead of the true optimal goal node, $G_{o p t}$ .

What is a Node?

Here, a node is not synonymous with a vertex in the graph.
The node being talked about is a search node.
As $A^{*}$ runs and generates a search tree in it's memory. The node we talk about is a node in that search tree.
This node is not just a physical vertex, it encapsulates the entire specific path required to reach that vertex, along with it's accumulated cost $g (n)$ .

Because there are multiple ways to navigate through a graph, the priority queue can simultaneously contain multiple distinct search nodes that all happen to terminate at the exact same physical destination, but arrived there via entirely different routes.

For A* to have selected $G_{b a d}$ as the final destination, the algorithm must have evaluated its priority function $f (G_{b a d} $ ) to be lower than or equal to any other available node in the priority queue. Since $G_{b a d}$ is a goal node, its remaining distance is zero, meaning $h (G_{b a d} )$ =0. Therefore, $f (G_{b a d} ) = g (G_{b a d} )$ , which is the total cost of this sub-optimal path.

Now, consider the true optimal path to $G_{o p t}$ . At the exact moment the algorithm incorrectly popped $G_{b a d}$ , there must have been some unexpanded node $n$ sitting in the priority queue that is currently on the correct, optimal path to $G_{o p t}$ .

Because we are using an admissible heuristic, we are mathematically guaranteed that $h (n)$ does not overestimate the true remaining cost to the goal. Therefore, the estimated total cost through node n, evaluated as $f (n) = g (n) + h (n)$ , must be less than or equal to the true optimal path cost.

Since we assumed $G_{b a d}$ is a sub-optimal path, its actual cost $g (G_{b a d} )$ is strictly greater than the true optimal path cost.
Combining the above two inequalities, we derive the following inequality: $$ f(n)≤ \pu{True Optimal Cost}<f(G_{bad})$$

This exposes the fatal flaw in our initial assumption. If $f (n)$ is strictly less than $f (G_{b a d} )$ , the A* priority queue—which always pops the lowest f score first—would have been mathematically forced to expand node $n$ before it ever finalized $G_{b a d}$ .

This is exactly why an optimistic, non-overestimating heuristic guarantees optimality. By never overestimating the cost to the goal, A* will never permanently ignore a genuinely optimal path in favor of a path that only appears cheaper locally.