Algorithms in a Nutshell

(^188) | Chapter 7: Path Finding in AI
Given the size of the search trees in Figure 7-7, one wonders about the quality of
the solutions produced by this effort. We make the following two observations:
An ill-chosen depth level may prevent a solution from being found
For initial position N2 and a depth of 25, no solution was found after searching
20,441 board states. How is this even possible? Because DEPTH-FIRSTSEARCH
will not visit the same board state twice. Specifically, the closest this particular
search comes to finding the solution is on the 3,451st board state:
4000
5000
6000
7000
8880
9880
108810
118810
12 12 12 10
13 12 0 10
14 8 14 14
15 8 14 14
16 10 0 14
17 10 0 10
18 12 18 10
19 12 18 10
20 20 18 10
21 20 0 14
22 20 18 22
23 20 18 10
24 24 14 22
258018
26 26 14 26
27 20 24 0
28 28 14 28
29 28 26 18
UNBOUNDED 30 1,029 37,980
123
784
65
Table 7-2. Solutions for depth-first search tree by ply depth for three initial
positions (continued)
d N1 moves N2 moves N3 moves
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