NOTES ON ITERATIVE DEEPENING

Revised by Charles Elkan, April 22, 2002

THE SEARCH PROBLEM

We want to use a search algorithm to explore a space of possible solutions to a given problem.

Each possible solution is called a node.  If a node is a solution to the problem, then it is called a goal node.

The search process begins at an initial node (also called the root node).  Some nodes can be used to generate further nodes through an operation called expansion.  If a node has not yet been expanded, it is called a leaf node.

For our problem, each node is an expression represented in abstract syntax form, i.e. as a binary tree.  A node is expanded by taking one of its primitive subexpressions, i.e. 1 or n, and replacing it by all possible subexpressions with a single operator, i.e. 1+1, 1-1, 1*1, 1/1, 1+n, 1-n, etc. We can assume that the initial node is the expression 1.
 

THE BASIC SEARCH ALGORITHM

Here is a search algorithm that includes many others as special cases.

              fringe := make-queue(initial-node)
        loop
          if empty?(fringe) then return FAIL
          else
            X := remove-front(fringe)
            if is-goal?(X) then return X
            else
              fringe := insert(fringe,expand(X))
        end loop

The fringe here is a priority queue.  The function insert puts a set of nodes into the priority queue in a specific way.  Different algorithms use different insert functions.
 

DEPTH-FIRST SEARCH (DFS)

DFS is the general search algorithm where the insert function is "enqueue-at-front".  This means that newly generated nodes are added to the fringe at the beginning, so they are expanded immediately.  In this case, the queue acts like a stack, and it is easy to implement with a list.

DFS goes down a path until it reaches a node that has no children.  Then DFS "backtracks" and expands a sibling of the node that had no children.  If this node has no siblings, then DFS looks for a sibling of the grandparent, and so on.
 

ANALYSIS OF DFS

No matter how deep the current node is, DFS will always go deeper if it has a child.

The major weakness of DFS is that it will fail to terminate if there is an infinite path "to the left of" the path to the first solution.

In other words, for many problems DFS is not complete: A solution exists but DFS cannot find it.

The major advantage of DFS is that it only uses O(bm) space if the branching factor (number of children returned by the expand function) is b and the maximum depth is m.  (Explanation: there are m nodes on the longest path, and for each of these b-1 siblings must be stored.)
 

DEPTH-LIMITED SEARCH

This is the same as DFS except a nodes of depth equal to a fixed maximum (say M) are not expanded.

If a solution exists at depth M or less, then M-limited DFS will find the solution, and the algorithm is very efficient in space: it uses only O(bM) memory.

However, depth-limited DFS is not complete: If a solution exists but only at depth greater than M, then depth-limited DFS will not find the solution.
 

ITERATIVE DEEPENING

Iterative deepening is a very simple, very good, but counter-intuitive idea that was not discovered until the mid 1970s.  Then it was invented by many people simultaneously.  The idea is to perform depth-limited DFS repeatedly, with an increasing depth limit, until a solution is found.

Intuitively, this is a dubious idea because each repetition of depth-limited DFS will duplicate uselessly all the work done by previous repetitions.  But, this useless duplication is not significant because a branching factor b > 1 implies that the number of nodes at depth k  exactly is much greater than the total number of nodes at all depths k-1 and less.

For a problem with branching factor b where the first solution is at depth k, the time complexity of iterative deepening is O(bk), and its space complexity is O(bk).  This means that iterative deepening simulates breadth-first search, but with only linear space complexity.