One way in which depth-first search is unattractive is the possibility that we are searching a branch of the tree that has no solution in it and it is of infinite depth. We might try to limit the damage by doing depth-first search to a fixed depth. With such a scheme, we would be doing bounded depth-first search.
The technique of iterative deepening is based on this idea. Iterative deepening is depth-first search to a fixed depth in the tree being searched. If no solution is found up to this depth then the depth to be searched is increased and the whole `bounded' depth-first search begun again.
It works by setting a depth of search -say, depth 1- and doing depth-first search to that depth. If a solution is found then the process stops -otherwise, increase the depth by, say, 1 and repeat until a solution is found. Note that every time we start up a new bounded depth search we start from scratch - i.e. we throw away any results from the prvious search.
We illustrate by looking at iterative deepening starting at depth 1 (see figure 8), failing to find the winning state (node ee), resetting the depth to 2, failing (see figure 9), resetting the depth to 3 and succeeding (figure 10).
Now iterative deepening is a popular method of search. We explain why this is so.
Depth-first search can be implemented to be much cheaper than breadth-first search in terms of memory usage -but it is not guaranteed to find a solution even where one is guaranteed.
On the other hand, breadth-first search can be guaranteed to terminate if there is a winning state to be found and will always find the `quickest' solution (in terms of how many steps need to be taken from the root node). It is, however, a very expensive method in terms of memory usage.
Iterative deepening is liked because it is an effective compromise between the two other methods of search. It is a form of depth-first search with a lower bound on how deep the search can go. Iterative deepening terminates if there is a solution. It can produce the same solution that breadth-first search would produce but does not require the same memory usage (as for breadth-first search).
Note that depth-first search achieves its efficiency by generating the
next node to explore only when this needed
. The breadth-first search
algorithm has to grow all the search paths available until a solution
is found -and this takes up memory.
Iterative deepening achieves its memory saving in the same way that depth-first search does -at the expense of redoing some computations again and again (a time cost rather than a memory one). In the search illustrated, we had to visit node d three times in all!
By the way, for the running example used, all three methods find the solution with iterative deepening doing the most work in terms of nodes expanded. In the worst case, iterative deepening can therefore come off the worst of the three methods. To change things, simply imagine that node n has a subtree of depth 1000 below it. Then iterative deepening lies between the two other methods in terms of the number of nodes expanded. It will, with few exceptions, always expand more nodes than breadth-first search. On the other hand, the greater the branching rate (i.e. nodes have many successors), the better iterative deepening performs in relation to breadth-first search.
