Algorithms in a Nutshell

Depth-First Search | 183

Path Finding

in AI

Solution

DEPTH-FIRSTSEARCHstoresthesetofopen(i.e.,yettobevisited)boardstatesin

a stack, and retrieves them one at a time for processing. In the implementation

shown in Example7-3, theclosedset is stored in a hash table to efficiently deter-

mine when not to revisit a board state previously encountered within the search

tree; the hash function used is based on the key computed for eachINodeobject.

Figure 7-6. Sample Depth-First Search tree for 8-puzzle

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