Depth-first Search

Depth-first search is an example of a directed search use to find a sequence of operations that will move a problem solver from the initial state to a goal state of a problem (Nilsson, 1980).  It is an approach that makes the search through the problem space more efficient than simpler methods, such as generate-and-test.  Depth-first search proceeds by following the “mouse scan rule”, searching the problem space in a prespecified order.  Imagine that the problem space is a physical maze, where branches from an intermediate state are open passageways.  With the mouse scan rule (i.e. depth-first search) one always chooses the passageway to the left, and keeps on applying this rule until a dead end is reached.  One then follows the path backwards until one reaches a point that has a passage that has not been explored, and follows it to the end by applying the mouse scan rule.  Eventually, this technique will discover the route to a goal state in the problem space.

The advantage of a directed search technique like depth-first search is that it will not move back and forth between intermediate states that have already been explored, which is possible with methods like generate-and-test.  The disadvantage of a directed search technique like depth-first search is that it does not decide “what to do next” by examining the content of an intermediate problem space, which means that it cannot take advantage of noticing that the current state of the problem is near a solution.

References:

1. Nilsson, N. J. (1980). Principles Of Artificial Intelligence. Los Altos, CA: Morgan Kaufman.

(Added January 2010)