ALGORITHMS - DEPTH FIRST

Depth-first is an unintelligent algorithm (i.e., no heuristic is used) which starts at an initial state and proceeds as follows:

1. Check if current node is a goal state.
2. If not, expand the node, choose a successor of the node, and repeat.
3.  If a node is a terminal state (but not a goal state), or all successors of a node have been checked, return to that node’s parent and try another successor.  (The failed states need not stay in memory.) 

Click here to see a shockwave demo (demo from http://www-jcsu.jesus.cam.ac.uk/~tdk22/project/depthfirst.html).

Visited Nodes

Current Node

The initial node is checked for a goal state, then expanded.	One of the initial node’s successors is chosen; it is checked, then expanded.	This process repeats until a goal state or a terminal state is reached.

If a terminal state is not a goal, the node is deleted, and the search returns to that node’s parent and tries a different successor.	If a node has no remaining successors, it is deleted itself (just as a node with no successors to begin with), and its parent tries another successor.	This process continues until a goal state is found, or every possibility is tried (i.e., all the successors of the initial node and the initial node itself fail to lead to a goal state).

The primary strength of the depth first search is its efficient use of memory—relatively few nodes need to be kept track of at any given time.  However, the depth first search has a number of important weaknesses: 

Þ    There is no guarantee that the solution this algorithm finds will be the “cheapest,” i.e. the one that requires the least number of steps from the initial state.  For example, in the above scenario, all possibilities using the initial state’s left successor will be considered before any possibilities using the right successor.  A solution starting with the left option and requiring 10, 100, or 1000 steps would be returned, even if the right option solved the problem in 1 step!

Þ    In some cases, a depth first search may get caught in an infinite loop and never find a viable solution.  Take a maze, for instance; even if the search is programmed to never go back the way it came, the search could easily go around in a circle without realizing it is covering the same ground over and over again.  Since a depth-first search evaluates possibilities in an arbitrary—but usually consistent—order (for instance, in navigating a maze, the algorithm might always attempt north, then east, then south, then west), if it arrives at a state it doesn’t realize it’s seen before, it will always make the same choice and keep looping.

Thus, depth first search is ideal when:

Þ    Efficient memory use is important

Þ    Any solution to the problem will do

Þ    There is little chance of infinite looping