Algorithms in a Nutshell

Depth-First Search | 187

Path Finding

in AI

Table 7-1. Size of search tree (open + closed) for three initial positions

Depth bound d

1111

2333

3777

4 151515

5 313131

6 515151

7 909090

8 25 149 150

9 37 254 259

10 54 345 113

11 81 421 195

12 105 518 293

13 168 728 401

14 216 678 400

15 328 1,133 652

16 1,374 1,991 886

17 2,121 2,786 1,443

18 729 1,954 1,897

19 1,218 3,240 3,575

20 1,601 4,350 2,211

21 1,198 5,496 7,437

22 2,634 6,315 1,740

23 4,993 11,053 6,267

24 3,881 8,031 4,214

25 6,723 20,441 11,494

26 2,071 15,074 15,681

27 5,401 10,796 26,151

28 1,206 16,233 2,081

29 1,958 33,526 22,471

UNBOUNDED 53 1,962 67,808

Table 7-2. Solutions for depth-first search tree by ply depth for three initial

positions

d N1 moves N2 moves N3 moves

1000

2000

3000

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