In computer science, iterative deepening search or more specifically iterative deepening depth-first search (IDS or IDDFS) is a state space/graph search strategy in which a depth-limited version of depth-first search is run repeatedly with increasing depth limits until the goal is found. IDDFS is optimal, meaning that it finds the shallowest goal. Since it visits all the nodess in the search tree, the cumulative order in which nodes are first visited is effectively the same as in breadth-first search. However, IDDFS uses much less memory.

Algorithm for directed graphs

The following pseudocode shows IDDFS implemented in terms of a recursive depth-limited DFS (called DLS) for directed graphs. This implementation of IDDFS does not account for already-visited nodes.

function IDDFS(root) is
    for depth from 0 to ∞ do
        found, remaining ← DLS(root, depth)
        if found ≠ null then
            return found
        else if not remaining then
            return null

function DLS(node, depth) is
    if depth = 0 then
        if node is a goal then
            return (node, true)
        else
            return (null, true)    (Not found, but may have children)

    else if depth > 0 then
        any_remaining ← false
        foreach child of node do
            found, remaining ← DLS(child, depth−1)
            if found ≠ null then
                return (found, true)   
            if remaining then
                any_remaining ← true    (At least one node found at depth, let IDDFS deepen)
        return (null, any_remaining)

If the goal node is found by , will return it without looking deeper. Otherwise, if at least one node exists at that level of depth, the remaining flag will let continue.

2-tuples are useful as return value to signal to continue deepening or stop, in case tree depth and goal membership are unknown a priori. Another solution could use sentinel values instead to represent not found or remaining level results.

Properties

IDDFS achieves breadth-first search's completeness (when the branching factor is finite) using depth-first search's space-efficiency. If a solution exists, it will find a solution path with the fewest arcs.

, the cost of repeatedly visiting the states above this depth is always small.

The main advantage of IDDFS in game tree searching is that the earlier searches tend to improve the commonly used heuristics, such as the killer heuristic and alpha–beta pruning, so that a more accurate estimate of the score of various nodes at the final depth search can occur, and the search completes more quickly since it is done in a better order. For example, alpha–beta pruning is most efficient if it searches the best moves first.

increases. When used in an interactive setting, such as in a chess-playing program, this facility allows the program to play at any time with the current best move found in the search it has completed so far. This can be phrased as each depth of the search corecursively producing a better approximation of the solution, though the work done at each step is recursive. This is not possible with a traditional depth-first search, which does not produce intermediate results.

Asymptotic analysis

Time complexity

The time complexity, is the depth of the goal.

Proof

times. So the total number of expansions in an iterative deepening search is

gives

. Then we have

This is less than the infinite series

which converges to

That is, we have

.

Example

the number is

.

The higher the branching factor, the lower the overhead of repeatedly expanded states,.

Space complexity

The space complexity, is the depth of the goal.

Proof

.

In general, iterative deepening is the preferred search method when there is a large search space and the depth of the solution is not known.

Example

For the following graph:

a depth-first search starting at A, assuming that the left edges in the shown graph are chosen before right edges, and assuming the search remembers previously-visited nodes and will not repeat them (since this is a small graph), will visit the nodes in the following order: A, B, D, F, E, C, G. The edges traversed in this search form a Trémaux tree, a structure with important applications in graph theory.

Performing the same search without remembering previously visited nodes results in visiting nodes in the order A, B, D, F, E, A, B, D, F, E, etc. forever, caught in the A, B, D, F, E cycle and never reaching C or G.

Iterative deepening prevents this loop and will reach the following nodes on the following depths, assuming it proceeds left-to-right as above:

• Depth 0: A

• Depth 1: A, B, C, E

(Iterative deepening has now seen C, when a conventional depth-first search did not.)

• Depth 2: A, B, D, F, C, G, E, F

(It still sees C, but that it came later. Also it sees E via a different path, and loops back to F twice.)

• Depth 3: A, B, D, F, E, C, G, E, F, B

For this graph, as more depth is added, the two cycles "ABFE" and "AEFB" will simply get longer before the algorithm gives up and tries another branch.

Related algorithms

Similar to iterative deepening is a search strategy called iterative lengthening search that works with increasing path-cost limits instead of depth-limits. It expands nodes in the order of increasing path cost; therefore the first goal it encounters is the one with the cheapest path cost. But iterative lengthening incurs substantial overhead that makes it less useful than iterative deepening.

Iterative deepening A* is a best-first search that performs iterative deepening based on ""-values similar to the ones computed in the A* algorithm.

Bidirectional IDDFS

IDDFS has a bidirectional counterpart, intersect. If so, a shortest path is found. Otherwise, the search depth is incremented and the same computation takes place.

. Pictorially, the search frontiers will go through each other, and instead a suboptimal path consisting of an even number of arcs will be returned. This is illustrated in the below diagrams:

What comes to space complexity, the algorithm colors the deepest nodes in the forward search process in order to detect existence of the middle node where the two search processes meet.

, the search will never terminate.

Time and space complexities

The running time of bidirectional IDDFS is given by

and the space complexity is given by

, the speedup is roughly

Pseudocode

function Find-Shortest-Path(s, t) is
   if s = t then
       return <s>
   (B, F, Vf, Vb) := (empty stack, ∅, ∅, ∅)
   (Δ, lf, lb) := (0, 0, 0)
   forever do
       (F, Vf) := (∅, ∅)
       Depth-Limited-Search-Forward(s, Δ, F, Vf)
       if |Vf| = lf then
           return nil
       (lf, Vb) := (|Vf|, ∅)
       μ := Depth-Limited-Search-Backward(t, Δ, B, F, Vb)
       if μ\neq nil then
           return Build-Path(s, μ, B, G)
       Vb := ∅
       μ := Depth-Limited-Search-Backward(t, Δ + 1, B, F, Vb)
       if μ\neq nil then
           return Build-Path(s, μ, B, G)
       if |Bb| = lb  then
           return nil
       (lb, Δ) := (|Vb|, Δ + 1)

function Build-Path(s, μ, B) is
    π := Find-Shortest-Path(s, μ) (Recursively compute the path to the relay node)
    Pop(B)
    return π\circ B (Append the stack starting from its top.)

function Depth-Limited-Search-Forward(u, Δ, F, V) is
    if u ∈ V then
        return
    V := V ∪ {u}
    if Δ = 0 then
        F := F ∪ {u} (Mark u as a frontier node.)
        return
    foreach child of u do
        Depth-Limited-Search-Forward(child, Δ − 1, F, V)

function Depth-Limited-Search-Backward(u, Δ, B, F, V) is
    if u ∈ V then
        return nil
    Push(B, u)
    if Δ = 0 then
        if u ∈ F  then
            return u (Reached the marked node, use it as a relay node)
        Pop(B)
        return nil
    V := V ∪ {u}
    foreach parent of u do
        μ := Depth-Limited-Search-Backward(parent, Δ − 1, B, F, V)
        if μ\neq nil then
            return μ
    Pop(B)
    return nil

References