Algorithms in a Nutshell

Depth-First Search | 181

Path Finding

in AI

Assumptions

We assume that the problems all have game states that can be represented effec-

tively, and that there are a finite number of possible moves at each game tree or

search tree node. The search space may actually be a graph, rather than a tree,

because there may be multiple move sequences that reach the same state. Even so,

the resulting path-finding algorithms impose a tree-like structure over the graph

by evaluating linear chains of moves.

We use a made-up puzzle, which we call Tiny-Puzzle, as an example within the

pseudocode descriptions of DEPTH-FIRSTSEARCH,BREADTH-FIRSTSEARCH,

and A*SEARCH. In Tiny-Puzzle, a board state consists of two non-negative

numbers,s 0 ands 1. There are two moves available at each board state—(1) incre-

ments 0 , and (2) increments 1 —thus the branching factor is 2 for this game. For

example, given the initial state <s 0 =0,s 1 =0>, the goal state <s 0 =1,s 1 =2> can be

reached in three moves: increments 1 , increments 0 , and increments 1.

Depth-First Search

DEPTH-FIRSTSEARCH(Figure 7-5) attempts to locate a path to the goal state by

making as much forward progress as possible without visiting the same state

twice. Because some search trees explore a high number of board states, DEPTH-

FIRSTSEARCHis practical only if a maximum search depth is fixed in advance.

DEPTH-FIRSTSEARCHmaintains a stack ofopenboard states that have yet to be

visited and a set ofclosedboard states that have been visited. At each iteration,

DEPTH-FIRSTSEARCHpops from the stack an unvisited board state and expands

it to compute the set of successor board states given the available 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 pushed onto the stack ofopenboard states and the search

continues.

Figure 7-6 shows the computed search tree for an initial 8-puzzle board state

using a depth limit of 9. Note how a path of eight moves is found to the solution

(marked as GOAL) after some exploration to depth 9 in other areas of the tree. In

all, 50 board states were processed and 4 remain to be explored (shown in light

gray).

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.

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