why Admissible heuristics work?

Question

I came across the term admissible heuristics in context of A* Search algorithm. Can someone explain (or give an intuition) why the heuristic function h is admissible only if it doesn't over-estimate the actual distance?

Answer 1

Think about the stopping condition of A*, the algorithm stops if it reaches the goal node with a certain F value, where F equals G- the path constructed so far from the starting point plus the heuristic value H which represents an estimation of the remaining path to the goal.

At the goal node, F equals G as the estimation of the remaining path to the goal is 0.

The stopping condition is valid only if H is admissible, since then we can determine that if the F value we calculated at the goal node is smaller than any other F value we calculated in any other node, we can surely determine it is the shortest path, as no other path may reach the goal with a smaller F value.

If it wouldn't be admissible, then there may be some other node for whom we calculated F with an overestimation of the remaining path to the goal, and we can't stop the algorithm as a shorter path may exist.

Answer 2

For those who do not seek the resources provided free of cost and free of effort.

In computer science, specifically in algorithms related to pathfinding, a heuristic function is said to be admissible if it never overestimates the cost of reaching the goal, i.e. the cost it estimates to reach the goal is not higher than the lowest possible cost from the current point in the path. An admissible heuristic is also known as an optimistic heuristic.

This is a link to Wikipedia:

http://en.wikipedia.org/wiki/Admissible_heuristic

Concerning the second question

A heuristic is admissible when it doesn't overestimate the true cost, simply because it is defined this way.