Lesson 4

The reason admissibility matters is explained by the following theorem.

Theorem. If the heuristic \(h(v)\) never overestimates the true distance from \(v\) to the goal, then the \(A^{*}\)-algorithm always finds a shortest solution.

Proof. The algorithm processes configurations in the order of increasing values of \(f(v)=g(v)+h(v)\). Since \(h(v)\) never overestimates the remaining distance, the value \(f(v)\) is always a lower bound on the length of any solution path that goes through \(v\).

Therefore, when the target configuration is removed from the open set, its value \(g(v)\) cannot be larger than the length of a shortest solution. On the other hand, \(g(v)\) is the length of an actual solution path. Hence, it must be exactly the minimum possible length.◼