How does an admissible heuristic ensure an optimal solution?

Question Detail: 

When using A* or any other best path finding algorithm we say that the heuristic used should be admissible i.e. it should never overestimate the actual solution path (moves).

Can someone tell me how this is true? Please avoid equations and all. I need a logical proof. If you want you can explain using the Manhattan distance heuristic of the 8-puzzle.

Asked By : Ashwin

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/16065

Answered By : Carlos Linares López

While Anton's answer is absolutely perfect let me try to provide an alternative answer: being admissible means that the heuristic does not overestimate the effort to reach the goal, i.e., $h(n) \leq h^*(n)$ for all $n$ in the state space (in the 8-puzzle, this means just for any permutation of the tiles and the goal you are currently considering) where $h^*(n)$ is the optimal cost to reach the target.

I think the most logical answer to see why $A^*$ provides optimal solutions if $h(n)$ is admissible is becauase it sorts all nodes in OPEN in ascending order of $f(n)=g(n)+h(n)$ and, also, because it does not stop when generating the goal but when expanding it:

1. Since nodes are expanded in ascending order of $f(n)$ you know that no other node is more promising than the current one. Remember: $h(n)$ is admissible so that having the lowest $f(n)$ means that it has an opportunity to reach the goal through a cheaper path that the other nodes in OPEN have not. And this is true unless you can prove the opposite, i.e., by expanding the current node.
2. Since $A^*$ stops only when it proceeds to expand the goal node (as oppossed to stop when generating it) you are sure (from the first point above) that no other node leads through a cheaper path to it.

And this is, essentially, all you will find in the original proof by Nilsson et al.

Hope this helps,