Algorithms in a Nutshell

Comparison | 205

Path Finding

in AI

sample game, we created an initial state by randomly movingntiles (ranging from

2, 4, 8, and 16); note that the same tile will not be moved twice in a row, since

that would “undo” the move. Oncenreached 32, the searches ran out of memory.

For each board state, we execute BREADTH-FIRST SEARCH,DEPTH-FIRST

SEARCH(n), DEPTH-FIRSTSEARCH(2*n), and A*SEARCH. For each move sizen:

• We total the number of board states in theopenandclosedlists—this reveals
  the efficiency of the algorithm in locating the solution. The columns marked
  with # contain the average of these totals over all runs.


• We total the number of moves in the solution once found—this reveals the
  efficiency of the found solution paths. The columns marked withscontain
  the average of these totals over all runs. The number in parentheses records
  the number of trials that failed to locate a solution within the given ply depth.
  Table 7-4 contains the aggregate results of 1,000 trials, wherenrandom moves
  were made (n=2 through 14). Table 7-4 shows two statistics: (a) the average
  number of states of the generated search trees, (b) the average number of moves of
  the identified solutions.

Note that asnincreases by one, the size of the search tree grows exponentially for

all blind approaches, but the A*SEARCHtree remains manageable. To be precise,

the growth rates of these blind searches are estimated by the following functions:

DFS2(n)≅ 0.2867*n4.0722

DFS(n)≅ 0.2405*n2.9517

BFS(n)≅ 0.2585*n3.4041

BREADTH-FIRSTSEARCHalways finds the shortest path to the solution, but note

that A*SEARCHis not far behind (because of theGoodEvaluatorheuristic) even

though it explores significantly fewer board states. In separate trials of A*SEARCH

Table 7-4. Comparing search algorithms

n #A* #BFS #DFS(n)

#DFS

(2n) sA* sBFS sDFS(n) sDFS2(n)

2 5.0 4.5 3.0 6.4 2 2 2 2

3 7.0 13.4 7.0 26.8 3 3 3 3

4 9.0 25.6 12.3 66.1 4 4 4 5.0

5 11.1 46.3 21.2 182.5 5 5 5 5.9

6 12.5 77.2 31.7 317.8 6 6 6 9.5 (45)

7 14.9 136.5 57.4 751.4 6.8 6.8 6.92 9.6 (279)

8 17.1 220.5 85.6 1095.2 7.7 7.7 7.9 (40) 13 (209)

9 22.0 367.9 147.2 2621.7 8.8 8.7 8.8 (75) 13.1 (355)

10 25.5 578.8 211.7 3152.9 9.8 9.6 9.8 (236) 16.5 (316)

11 33.1 926.4 296.6 6723.3 10.6 10.4 10.6 (431) 17.1 (369)

12 42.3 1445.7 440.8 5860.5 11.9 11.3 11.6 (350) 20.7 (402)

13 56.6 2351.3 558.9 12483.1 13.2 12.2 12.3 (615) 21.7 (313)

14 60.7 3579.7 900.3 14328.1 14.5 13.0 13.3 (593) 25.1 (259)

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