Lesson 3

The crucial ingredient in the \(A^{*}\)-algorithm is the choice of the heuristic \(h(v)\). For the 15 Puzzle, a standard choice is the Manhattan distance. For each tile, we compute the distance from its current cell to its target cell, counting only horizontal and vertical steps. We then sum these distances over all tiles: \[h(v)=\sum_{i=1}^{15}d_{i},\] where \(d_{i}\) is the Manhattan distance from the current position of tile \(i\) to its final position.

This heuristic is natural because one move changes the position of only one tile by one cell. Hence, if the total Manhattan distance is, say, \(17\), then at least \(17\) moves are needed to solve the puzzle. In particular, the heuristic never overestimates the true remaining distance.

A heuristic with this property is called admissible. 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.◼