Why is the A* search heuristic optimal even if it underestimates costs?

A* search finds optimal solution to problems as long as the heuristic is admissible which means it never overestimates the cost of the path to the from any given node (and consistent but let us focus on being admissible at the moment).

But why does it always find the optimal solution if the heuristic underestimates? For example, if it underestimates a non optimal path by more than what it underestimates the optimal one, isn't that equivalent to over estimating?

• What research have you done? Most textbooks will have an explanation of why A* is correct, which should answer your question. – D.W. Oct 9 '14 at 18:20
• Consider the heuristic which is always zero regardless of the nodes under consideration. This algorithm will always underestimate the non-optimal path by more than the optimal path. Can you show that A* with this heuristic is optimal? Does this give you insight into why A* with a better heuristic is optimal? – Eric Lippert Oct 9 '14 at 19:35

A* maintains a priority queue of options that it's considering, ordered by how good they might be. It keeps searching until it finds a route to the goal that's so good that none of the other options could possibly make it better. How good an alternative might be is based on the heuristic and on actual costs found in the search so far.

If the heuristic underestimates, the other options will look better than they really are. A* thinks those other options might improve the route, so it checks them out. If the heuristic only underestimates by a little bit, maybe some of those routes will turn out to be useful. On the other hand, if the heuristic overestimates, A* can think that the alternatives to the route already has are all terrible, so it won't bother to look at them. But the heuristic overestimates so they might be much better than they seem.

For example, suppose you're trying to drive from Chicago to New York and your heuristic is what your friends think about geography. If your first friend says, "Hey, Boston is close to New York" (underestimating), then you'll waste time looking at routes via Boston. Before long, you'll realise that any sensible route from Chicago to Boston already gets fairly close to New York before reaching Boston and that actually going via Boston just adds more miles. So you'll stop considering routes via Boston and you'll move on to find the optimal route. Your underestimating friend cost you a bit of planning time but, in the end, you found the right route.

Suppose that another friend says, "Indiana is a million miles from New York!" Nowhere else on earth is more than 13,000 miles from New York so, if you take your friend's advice literally, you won't even consider any route through Indiana. This makes you drive for nearly twice as long and cover 50% more distance. Oops.

It is true that if it underestimates a non-optimal path by more than it underestimates the optimal one, then it will explore down those paths before exploring down the optimal one. What is important, and this is what admissibility guarantees, is that while it is exploring down those non-optimal paths it will not find the goal and finish the search before exploring down the optimal path. This is because as it goes down those non-optimal paths, even though they seem great at first, the cost/length of them will start to add up and at some point the algorithm will return to explore down the optimal path. If we were allowed to overestimate the cost to the goal and did so down the optimal path, then we might actually go down the non-optimal path and find the goal (which terminates the search, and therefore prevents us from ever exploring the optimal path).

• Welcome to the site! I hope you find it useful and stick around. Our short tour gives some information about how to effectively use Stack Exchange sites. – David Richerby Nov 3 '17 at 10:33

The important difference between A* and Best-First search is that A* combines the value given by the estimate function $e$ with the length of the (shortest currently known) path to the node under consideration.

Suppose your optimal path to the goal has length $k$; then the estimate for your starting state is at most $k$, and for the $i$-th node along the optimal path, the estimate is at most $k-i$. This gives a bound for how far the algorithm will follow any spurious path $p$; as soon as you have taken more than $k$ steps along $p$, the currently explored prefix of the optimal path will look better, and $p$ will be abandoned.

Essentially, A* search sits in between Breadth-First (uninformed, guaranteed to find a shortest path, but slow) and Best-First (guided by an estimate function, potentially fast, but very dependent on the quality of the estimates).