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?
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.