Algorithms in a Nutshell

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.

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).

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