Algorithms in a Nutshell

Depth-First Search | 189

Path Finding

in AI

which is inspected in the 25thlevel. This board is only three moves away from

the solution! Since it was visited and not expanded upon, it was added to the

closedset. Since the depth limit is reached, no further exploration from this state

is made, and if DEPTH-FIRSTSEARCHwere to encounter this node at anearlier

level, it would not explore further since the node exists in theclosed set.

As the depth level increases, the solution found may be suboptimal

Note how the discovered solutions grow as the depth limit increases, some-

times to be two or three times larger than necessary.

Figure 7-7. Search tree size for Depth-First Search as depth increases

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