Algorithms in a Nutshell

(^202) | Chapter 7: Path Finding in AI
GoodEvaluatorbased upon the logic of the 8-puzzleGoodEvaluator. With the goal
state of:
and an initial state of:
ASEARCHrapidly locates a 15-move solution after processing 39 board states
with 43 board states in theopenset waiting to be explored, as shown in
Figure 7-13.
With a 15-move limit, DEPTH-FIRSTSEARCHfails to locate a solution after
exploring 22,136 board states. After 172,567 board states (85,213 in theclosedset
and 87,354 remain in theopenset), BREADTH-FIRSTSEARCHran out of memory
with 64MB of RAM trying to accomplish the same task. Of course you could add
more memory or increase the depth limit, but you should not expect those to be
the reasons why you are able to solve these problems.
But do not be fooled by how easily ASEARCHsolved this sample 15-puzzle; when
attempted on a more complicated initial board, such as:
A*SEARCHruns out of memory. Clearly the rough evaluation function for the 15-
puzzle is ineffective for the 15-puzzle, which has over 10^25 possible states (Korf,
2000).
Variations
Instead of only searching forward from the initial state, some have proposed a
bidirectional search algorithm using forward and backward ordered searches
(Kaindl and Kainz, 1997). Initially discarded by early AI researchers as being
unworkable, Kaindl and Kainz have presented powerful arguments that the
approach should be reconsidered.
1234
5678
9 101112
13 14 15
21083
16 4
59711
13 14 15 12
5124
14937
13 10 12 6
15 11 8
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