Why does an admissible heuristic mean A* is optimal?

An admissible heuristic never overestimates the cost to reach the goal. However, isn't that only the relative difference between heuristics for two different paths matter?

Say we have optimal path A (cost 100 to reach goal) and sub-optimal path Z (cost 120 to reach goal). Even if the heuristic is admissible, say it gives A a heuristic of cost 99 while it gives Z a heuristic of cost 10.

In both cases, the heuristic is admissible since it's lower than the actual cost it'll take to reach the goal, but still under this, Z is optimal since the heuristic gives a cost of 10 to Z and a cost of 99 to A.

It seems to me then it doesn't even matter that the heuristic is admissible. You still get the suboptimal solution.

What am I missing?

• Eh, sorry, I see two answers now. Does that mean this is on topic here? – Maarten Bodewes Sep 12 '15 at 15:26
• @MaartenBodewes It's a better fit on CS.SE for sure, but the migration options are so bad that a lot of users who browse [algorithm] would rather just answer the question. – David Eisenstat Sep 12 '15 at 15:41

The heuristic defines which nodes will be explored first, but does not change the final path found.

In your example, the heuristic will cause the path to Z to be explored first. The algorithm will discover the true (expensive) cost of 120. Then it will decide to explore the A path and discover the optimal route.

A better heuristic would guess A was the way to go immediately, find the cost of 100, and never bother exploring Z at all (e.g. if the heuristic said the cost was greater than 100).

So the heuristic changes the execution time, but not the final answer.

A* does not guarantee to find optimal path to nodes with h(v) > 0. It only guarantees to find the optimal route to the target node, with h(v) = 0. In the process of doing so, it will find optimal path to many nodes along the way, but not all of them.