Algorithms in a Nutshell

Breadth-First Search

Breadth-First Search ( Figure 7-8) attempts to locate a path by methodically evaluating board states closest to the initial board state without visiting the same state twice. Breadth-First Search is guaranteed to find the shortest path to the goal state, if such a path exists.

Figure 7-8. Breadth-First Search fact sheet

In truth, the only difference from Depth-First Search is that Breadth-First Search maintains a queue of open states that have yet to be visited, whereas Depth-First Search uses a stack. At each iteration, Breadth-First Search removes from the front of the queue an unvisited board state and expands it to compute the set of successor board states given the valid moves. If the goal state is reached, then the search terminates. Any successor board states that already exist within the closed set are discarded. The remaining unvisited board states are appended to the end of the queue of open board states, and the search continues.

Using the example from the 8-puzzle starting at:

2	8	3
1	6	4
7		5

the computed search tree is shown in Figure 7-9. Note how a solution is found with five moves after all paths with four moves are explored (and nearly all five-move solutions were inspected). The 20 dark-gray board states in the figure are board states in the open queue waiting to be inspected. In total, 25 board states were processed.

Figure 7-9. Sample Breadth-First ...