Algorithms in a Nutshell

Comparison

Breadth-First Search is guaranteed to find the solution with the least number of moves from the initial state, although it may evaluate a rather large number of potential move sequences as it operates. Depth-First Search tries to make as much progress as possible each time it searches, and may locate a solution rather quickly, but it also may waste a lot of time on searching parts of the search tree that seem to offer no hope for success.

It is thus worthwhile to compare Depth-First Search, Breadth-First Search, and A*Search directly with one another. Using the 8-puzzle as our sample game, we created an initial state by randomly moving n tiles (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. Once n reached 32, the searches ran out of memory. For each board state, we execute Breadth-First Search, Depth-First Search(n), Depth-First Search(2*n), and A*Search. For each move size n:

• We total the number of board states in the open and closed lists—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 with s contain 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 ...