NOTES ON ITERATIVE DEEPENING


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 subexpressons, 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.

        search-tree := initial-node
        loop
          if there are no leaf nodes then return FAIL
          else
            choose a leaf node X according to "strategy"
            if X is a goal node then return X
            else
              expand X
              add the resulting new leaf node(s) to search-tree
        end loop

When a leaf node is expanded, either it has children, in which case it is no longer a leaf node, or it proves to have no children, in which case it is a "dead end" that should never be chosen again.
 
 
 

THE SEARCH TREE


Notice that expanding one node can yield another node that has already been visited.  In general the search algorithm does not "know" this, where "know" means "has available a directly usable explicit representation."

In some domains it is easy to test whether multiple nodes correspond to the same state in the "real world".  In other domains it is impossible.

The general search algorithm explores a search tree, NOT the search space directly.

The depth of a node is the number of nodes on the path from the root to this node.  (Note that the depth of the root is 0 by this defn.)

The fringe of the tree is the set of leaf nodes of the tree.  A leaf node is a node that is NOT the parent of any other node.

The search algorithm needs an efficient representation of the fringe.  We shall use a queue, i.e. a special list where you can remove elements from the front and you can insert new elements into the middle.
 
 

THE GENERAL SEARCH ALGORITHM (AGAIN)

                        input: a well-formulated search problem
               a function "insert" to place new nodes into a queue

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

The well-formulated search problem includes the following functions:
        - initial-node is a node representing the initial state
        - isa-goal? tests whether a state is a goal state
        - expand applies all the operators of the problem to a node
          and returns all the successors of this node

The function "insert" includes a set of nodes in the queue in a specific way.  Different algorithms use different "insert" functions.
 
 

DEPTH-FIRST SEARCH

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.

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 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 it and is very space-efficient: it uses only O(b*M) space.

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

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 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 repeat uselessly all the work done by previous repetitions.

But, this useless repetition is not significant because a branching factor b > 1 implies that

        # nodes at depth k >> # nodes at depth k-1 or less

Iterative deepening simulates BFS with linear space complexity.

For a problem with branching factor b where the first solution is at depth k, the time complexity of iterative deepening is O(b^k), and its space complexity is O(b*k).