A* Correctness and Optimality
What You'll Learn
You'll learn why A* is guaranteed to find the shortest path when using admissible heuristics and why it always terminates successfully.
Why A* Always Works
Think of A* like a careful explorer who never gives up on a promising path too early. The algorithm's correctness relies on two fundamental guarantees:
Termination: A* will always finish because it explores nodes in order of their f(n) = g(n) + h(n) value. Since g(n) (actual cost so far) grows as we move away from the start, and we have a finite graph, eventually we must reach the goal or exhaust all possibilities.
Optimality: Here's the key proof: When A* selects the goal node for expansion, it has the lowest f value among all nodes in the open set. If a shorter path existed, some node on that path would have a lower f value (because with an admissible heuristic, h(n) never overestimates). That node would've been expanded first! Since we're expanding the goal now, no better path exists.
The Admissibility Guarantee
An admissible heuristic never overestimates the true remaining cost. This is crucial—it ensures A* doesn't prematurely discard the optimal path. If h(n) is always ≤ true cost, then when we expand a node, we can be confident we haven't missed a better route.
Think of it like optimistic estimation: your GPS says "at least 20 minutes remaining" but never lies by saying 5 minutes when it's actually 30. This honesty keeps A* on track.
Key Takeaway: A* with an admissible heuristic is both correct (always terminates) and optimal (finds the shortest path) because it explores nodes systematically and never prematurely dismisses better alternatives.