Lesson 1

In this section, we explain how the \(A^{*}\)-algorithm can be used to find a shortest solution for the 15 Puzzle.

As before, let us think of the puzzle as a graph. Each vertex of this graph is a configuration of the puzzle, and two vertices are connected by an edge if one configuration can be obtained from the other by a single move. Thus, solving the puzzle amounts to finding a shortest path from the initial configuration to the target configuration.

A natural first idea is to run a breadth-first search. Since every move has the same cost, breadth-first search indeed finds a shortest path. However, the graph of all configurations is far too large, and breadth-first search explores too many positions.

The main idea of the \(A^{*}\)-algorithm is to explore first those configurations that look the most promising. To measure how promising a configuration is, we associate to it two numbers: \[g(v) \text{ and }h(v).\] Here, \(g(v)\) is the number of moves already used to reach the configuration \(v\), while \(h(v)\) is an estimate of how many more moves are still needed to reach the goal. The algorithm always gives priority to configurations with the smallest value \[f(v)=g(v)+h(v).\] Intuitively, \(g(v)\) measures how far we have already come, and \(h(v)\) measures how far we still have to go.