Algorithms in a Nutshell

Breadth-First Search | 191

Path Finding

in AI

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 theclosedset are discarded. The remaining unvisited board states are

appended to the end of the queue ofopen board states, and the search continues.

Using the example from the 8-puzzle starting at:

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 theopenqueue waiting to be inspected. In total, 25 board states

were processed.

Input/Output

Input

The algorithm starts from an initial board state and seeks a goal state that must be

reached. The algorithm assumes it can iterate through all valid moves given a

board state.

Output

Return a sequence of moves that represents a minimal-cost solution from the

initial state to the goal state (or declare that no such solution was found given

existing resources).

Context

This blind search is practical only if the predicted search space is within the

memory space of the computer. Since BREADTH-FIRSTSEARCHmethodically

checks all shortest paths first, it may take quite a long time to locate paths that

require a large number of moves. This algorithm may not be suitable if all that is

needed is some path from its initial state to the goal (i.e., if there is no need for it

to be the absolute shortest path).

Solution

BREADTH-FIRSTSEARCHstores the set ofopen(i.e., yet to be visited) board states

in a queue, and retrieves them one at a time from the front for processing. The

closedset is stored using a hash table. Each board state stores a back link, called a

Transition, that records the move that generated it and a reference to the previous

state. BREADTH-FIRSTSEARCHgenerates copies of each board state, since the

moves are applied directly to the boards and not undone. Example 7-4 shows the

implementation.

283

164

75

Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.

Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use