Depth First Search

(Also known as backtracking search.)

This is the second kind of uninformed search. Whereas the breadth first searcher stays as 'close to home' as possible, searching siblings at each level before moving to a deeper level in the search space, the depth first searcher plunges deeply into the space, exploring a child node, then a child node of that child, then a child node of that child, and so on.

Depth Bound

From the above description you can see that the depth first searcher could go on and on, deeper and deeper into the search space. The searcher could get lost. For example, in the 8-puzzle example given before, the goal is at depth 5. But a depth first searcher could go by this node and investigate hundreds of thousands of nodes deeper in the search graph.

Therefore, depth first search comes with a depth bound. If the search reaches a node at the bound depth, it goes no deeper. If the node found is not the goal, the searcher backs up at that point and tries another branch of the graph.

Example of Depth first search with a depth bound.

Consider the same 8-puzzle as before:

Start	Goal
2 8 3 1 6 4 7 5	1 2 3 8 4 7 6 5

Here are some snapshots of the search tree for this puzzle using depth first with a bound of 5.

Observations

Fig 8-3a

• The searcher heads deep into the tree following a line of child nodes.
• The arrows without nodes represent references to sibling nodes at a give level which have not yet been expanded but may be expanded in the future.
• The first plunge into the search space (graph) hits the depth bound without finding the goal node.

Fig 8-3b

• The searcher backs up from the node labeled '5' in fig 8-3a and tries that node's sibling., labeled '6' The sibling is at the depth bound and is not a goal node.
• The searcher backs up and tries the sibling of node '3', namely, node '7'.
• The nodes 3, 4, 5, 6 need never be visited again. Therefore the memory they occupy can be reclaimed. In breadth first search, this memory reclamation cannot happen.

Fig 8-3c

• The searcher once again heads down into the search space, hitting the depth bound at the node labeled '9'. Note again that the arrows with no node on the end represent pointers to unexpanded nodes.

Fig 8-4

• The searcher backs up again, and expands a sibling of the node labeled '9' The memory used by '9' is reclaimed.
• A sibling of node '9' is expanded. It turns out to be the goal. The solution is shown in Fig. 8.4. This figure also shows the nodes stored in memory.

Depth First vs Breadth First Search

Contrast memory usage

The examples show this visually. Click here to view the breadth first tree. The depth first method is clearly superior in this respect.

Drawback of Depth First.

• Depth first with a bound may not solve the problem. Some 8-puzzle problems have solutions as deep as 18 so a bound of 5 will never allow a solution to be found. Breadth first will always solve the problem, if you have enough time and memory.
• Depth first is not guaranteed to find the shortest path to a goal. Breadth first always will.

Iterative Deepening

You can make sure depth first search can find a solution by iterative deepening. In other words, the bound can be increased at run time. if nothing is found at depth 5, the depth can be extended to 6, etc,, etc. Doing this slows the search down but still saves much memory compared to breadth first search.