Lesson 5

Thus, the \(A^{*}\)-algorithm combines two ideas:

• it keeps track of the exact number of moves already made;


• it uses a heuristic to estimate how far the current configuration is from the goal.

This makes it much more efficient than plain breadth-first search, while still guaranteeing an optimal solution. In practice, for the 15 Puzzle one usually stores the open set in a priority queue ordered by the value \(f(v)\), and one uses the Manhattan distance as the heuristic.

Of course, even \(A^{*}\) may still examine many configurations for difficult instances. Nevertheless, it is one of the standard methods for solving the 15 Puzzle optimally.