A* Optimality and Admissibility
What you'll learn: Why A* is guaranteed to find the optimal path when your heuristic never overestimates the true cost.
The Core Idea
A* search is optimal — meaning it always finds the cheapest path to the goal — but only under a specific condition: the heuristic function must be admissible. An admissible heuristic never overestimates the true cost to reach the goal from any state.
Think of it like a GPS that always underestimates travel time. It might say "15 minutes away" when it's really 20, but never says "30 minutes" when it's only 15. This conservative estimate ensures you won't accidentally skip over the truly fastest route.
Why A* with Admissible Heuristics Is Optimal
The Proof Sketch:
-
*A evaluates nodes by f(n) = g(n) + h(n)**, where g(n) is the known cost to reach node n, and h(n) is the heuristic estimate to the goal.
-
Suppose A returns a suboptimal goal* (cost C₂) while an optimal goal exists (cost C₁, where C₁ < C₂).
-
Some node n on the optimal path must still be in the frontier when A* selected the suboptimal goal.
-
For that node n: f(n) = g(n) + h(n) ≤ g(n) + true_cost(n→goal) = C₁ (because h is admissible).
-
The suboptimal goal has: f(goal) = C₂.
-
Since C₁ < C₂, we have f(n) ≤ C₁ < C₂ = f(goal), meaning A* should have expanded n before selecting the suboptimal goal — contradiction!
The Required Conditions
- Admissibility: h(n) ≤ true_cost(n→goal) for all nodes
- Graph search: Must track explored states to avoid re-expansion
Key Takeaway: A* finds the optimal solution when the heuristic is admissible because it cannot prematurely commit to a suboptimal path — any unexplored nodes on a better path will have lower f-values.