O'Reilly logo

Algorithms in a Nutshell by Gary Pollice, Stanley Selkow, George T. Heineman

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Depth-First Search

Depth-First Search ( Figure 7-5) attempts to locate a path to the goal state by making as much forward progress as possible without visiting the same state twice. Because some search trees explore a high number of board states, Depth-First Search is practical only if a maximum search depth is fixed in advance. Depth-First Search maintains a stack of open board states that have yet to be visited and a set of closed board states that have been visited. At each iteration, Depth-First Search pops from the stack an unvisited board state and expands it to compute the set of successor board states given the available valid moves. If the goal state is reached, then the search terminates. Any successor board states that already exist within the closed set are discarded. The remaining unvisited board states are pushed onto the stack of open board states and the search continues.

Depth-First Search fact sheet

Figure 7-5. Depth-First Search fact sheet

Figure 7-6 shows the computed search tree for an initial 8-puzzle board state using a depth limit of 9. Note how a path of eight moves is found to the solution (marked as GOAL) after some exploration to depth 9 in other areas of the tree. In all, 50 board states were processed and 4 remain to be explored (shown in light gray).

Sample Depth-First Search tree for 8-puzzle

Figure 7-6. Sample Depth-First Search ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required