Recursive Formulation of Depth-First Search

Stack is implicit
The search is continued by recursive calls.

Procedure DFS(state s)
If s is a solution, print s and halt.
Mark s as visited.
For each successor x of s,
if x has not been visited then call DFS(x).
Return.

Iterative Formulation of Depth-First Search

As each new state is identified, it is pushed onto an OPEN list.
The next state to explore is obtained by popping it off the OPEN list.

1. Put the start state on OPEN.
2. If OPEN is empty, then halt.
3. Let S <- Pop(OPEN).
    Put S on CLOSED.
    If S is a goal state, then print its description
4. Let L be a list of the successors of S.
    Remove from L any members that are on CLOSED.
5. Remove from OPEN and elements that are on L.
    Let OPEN <- L concatenated with OPEN.
6. Go to step 2.

Breadth-First Search

As each new state is identified, it is placed onto the OPEN list at the end.
The next state to explore is obtained by taking off the first element of the OPEN list.

Heuristic Evaluation Functions and Best-First Search

As each new state is identified, we compute h(s), its heuristic cost value. Then we put it into the OPEN list.
The next state to explore is obtained by taking the minimum-value state off the OPEN list.

Uniform-Cost Search

Each move (connection from one state to a successor state) is assumed to have some nonnegative cost. The costs can vary from one move to another.

A state's total cost from the start state is the sum of the costs for the sequence of moves that go from the start state to this state.

As each state is identified, its total cost is computed, and the state isplaced on the OPEN list so as to keep the list sorted in order of increasing cost.

If a state s3 on OPEN is re-identified (found to be a successor of a state s2 different from the state s1 that got it onto OPEN in the first place),its total cost is recomputed, and if the new cost is lower than the old cost, s3 with its new cost is moved towards the front of the list, taking its new place according to its new value.

(This can happen in graph search, but it can't happen in tree search.)

Uniform-cost search is a generalization of breadth-first search that takes these variable costs into consideration.

Breadth-first search is a special case of uniform=cost search in which every move has unit cost.

Iterative Deepening Depth-First Search

In order to gain certain benefits of both depth-first and breadth-first search,
a technique called iterative deepening depth-first search (IDDFS) was developed.

Like Breadth-first search, IDDFS finds any solution by a shortest sequence of moves.
Like DFS it tends to be relatively efficient, having only relatively few states on the stack or on OPEN at any one time.

In IDDFS, we first check the start state to see if it is a solution, then we perform a DFS with a maximum depth (i.e., a depth cutoff) of 1, checking each state reached to find out if it's a solution. If not, we then perform a new DFS from the same start state but with a maximum depth of 2, etc.
As soon as a solution is found, we stop, and the stack contains a shortest sequence of moves to reach the solution from the start state.

IDDFS obviously tends to do a certain amount of redundant searching.
However, under typical conditions, the amount of redundant searching is relatively insignficant.

Here's an argument for this: Let's assume we are searching a tree rather than a graph. If the branching factor in the tree is 5, and the first solution is at the end of the 4th level down, then the number of state visitations in Breadth-first search is 1 + 5 + 25 + 125 + 625 = 781. But the average size of the OPEN list is 781 / 2 = 390.5. If any garbage collection takes place or virtual memory paging is forced by this, the performance penalty will be heavy.

With IDDFS, the number of state visitions is 1 + (1 + 5) + (1 + 5 + 25) + (1 + 5 + 25 + 125) + (1 + 5 + 25 + 125 + 625) = 1 + 6 + 31 + 156 + 781 = 975. However, the size of OPEN never exceeds 17. That is
4 states at level1, 4 states at level 2, 4 states at level 3, and five states at level4.

This limit is d * b + 1, where d is the depth of the solution and b is the maximum branching factor in the tree.

The depth of the solution is proportional to the log of the number of elements in a balanced tree of the same height.

Last modified: October 29, 1998

Steve Tanimoto

tanimoto@cs.washington.edu