4.7 Depth vs. Breadth Comparison

• You can compare Breadth-First and Depth-First with a Burst Mode Algorithm Race. Either team up with the person sitting next to you, or invoke a second copy of the animation software.

• Click here to start another copy of the software:

• For both instances of the animation software: set the same problem, and display mode. One instance should be set for Depth-First, and the other Breadth-First. Select a problem, and start the animations simultaneously.

• Try the following problem, and then a few problems of your own choice. Try to find some problems that the Depth First Search can solve quickly and some others that the Breadth First Search can solve quickly.

  Start Board 0 2 3 1 4 5 8 7 6

  Goal Board 1 2 3 8 0 4 7 6 5

  Relative Size of Search Space Tree
  

• From any given starting 8-Puzzle game board, there are a very large number of possible game boards that could be produced by following the rules of the puzzle. If we assume that from any possible arrangement of the 8-Puzzle we can get to any other possible arrangement of the 8-Puzzle then we essentially have a permutations problem. How many permutations of the 8-Puzzle board exist ?

• To gain some small appreciation of the relatively small portion of the "entire" search space some algorithms actually explore, have a look at several problems in Burst Mode (Fixed 8-Puzzle Problem) mode. This animation shows the relationship between the underlying search space and the nodes that are actually realized in computer memory.

• Once you've selected this mode, you'll be required to select from a small range of fixed 8-Puzzle problems. A dialog box will appear and present your with the choices. Click the "radio button" along side the problem of your choice. Then click Ok and then Start the animation as normal.