Algorithms in a Nutshell

(^190) | Chapter 7: Path Finding in AI
Interestingly, given the initial board state N1, an unbounded DEPTH-FIRST
SEARCHwill actually find a 30-move solution after processing only 30 board
states, with 23 left in itsopenset to be processed. However, this fortunate series of
events is unlikely to be repeated, as you can see from the solutions that
unbounded DEPTH-FIRSTSEARCH found for initial board states N2 and N3.
Breadth-First Search
BREADTH-FIRSTSEARCH(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-FIRSTSEARCHis guaranteed to find the shortest path to
the goal state, if such a path exists.
In truth, the only difference from DEPTH-FIRSTSEARCHis that BREADTH-FIRST
SEARCHmaintains a queue ofopenstates that have yet to be visited, whereas
DEPTH-FIRSTSEARCHuses a stack. At each iteration, BREADTH-FIRSTSEARCH
removes from the front of the queue an unvisited board state and expands it to
Figure 7-8. Breadth-First Search fact sheet
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