Iterative deepening depth-first search

The time complexity of IDDFS in a (well-balanced) tree works out to be the same as breadth-first search, i.e. ${\displaystyle O(b^{d})}$,[1]^: 5 where ${\displaystyle b}$ is the branching factor and ${\displaystyle d}$ is the depth of the goal.

In an iterative deepening search, the nodes at depth ${\displaystyle d}$ are expanded once, those at depth ${\displaystyle d-1}$ are expanded twice, and so on up to the root of the search tree, which is expanded ${\displaystyle d+1}$ times.[1]^: 5 So the total number of expansions in an iterative deepening search is

${\displaystyle b^{d}+2b^{d-1}+3b^{d-2}+\cdots +(d-1)b^{2}+db+(d+1)=\sum _{i=0}^{d}(d+1-i)b^{i}}$

where ${\displaystyle b^{d}}$ is the number of expansions at depth ${\displaystyle d}$, ${\displaystyle 2b^{d-1}}$ is the number of expansions at depth ${\displaystyle d-1}$, and so on. Factoring out ${\displaystyle b^{d}}$ gives

${\displaystyle b^{d}(1+2b^{-1}+3b^{-2}+\cdots +(d-1)b^{2-d}+db^{1-d}+(d+1)b^{-d})}$

Now let ${\displaystyle x={\frac {1}{b}}=b^{-1}}$. Then we have

${\displaystyle b^{d}(1+2x+3x^{2}+\cdots +(d-1)x^{d-2}+dx^{d-1}+(d+1)x^{d})}$

This is less than the infinite series

${\displaystyle b^{d}(1+2x+3x^{2}+4x^{3}+\cdots )=b^{d}\left(\sum _{n=1}^{\infty }nx^{n-1}\right)}$

which converges to

${\displaystyle b^{d}(1-x)^{-2}=b^{d}{\frac {1}{(1-x)^{2}}}}$, for ${\displaystyle abs(x)<1}$

That is, we have

${\displaystyle b^{d}(1+2x+3x^{2}+\cdots +(d-1)x^{d-2}+dx^{d-1}+(d+1)x^{d})\leq b^{d}(1-x)^{-2}}$, for ${\displaystyle abs(x)<1}$

Since ${\displaystyle (1-x)^{-2}}$ or ${\displaystyle \left(1-{\frac {1}{b}}\right)^{-2}}$ is a constant independent of ${\displaystyle d}$ (the depth), if ${\displaystyle b>1}$ (i.e., if the branching factor is greater than 1), the running time of the depth-first iterative deepening search is ${\displaystyle O(b^{d})}$.

For ${\displaystyle b=10}$ and ${\displaystyle d=5}$ the number is

${\displaystyle \sum _{i=0}^{5}(5+1-i)10^{i}=6+50+400+3000+20000+100000=123456}$

All together, an iterative deepening search from depth ${\displaystyle 1}$ all the way down to depth ${\displaystyle d}$ expands only about ${\displaystyle 11\%}$ more nodes than a single breadth-first or depth-limited search to depth ${\displaystyle d}$, when ${\displaystyle b=10}$.[5]

The higher the branching factor, the lower the overhead of repeatedly expanded states,[1]^: 6 but even when the branching factor is 2, iterative deepening search only takes about twice as long as a complete breadth-first search. This means that the time complexity of iterative deepening is still ${\displaystyle O(b^{d})}$.

The space complexity of IDDFS is ${\displaystyle O(d)}$,[1]^: 5 where ${\displaystyle d}$ is the depth of the goal.

Since IDDFS, at any point, is engaged in a depth-first search, it need only store a stack of nodes which represents the branch of the tree it is expanding. Since it finds a solution of optimal length, the maximum depth of this stack is ${\displaystyle d}$, and hence the maximum amount of space is ${\displaystyle O(d)}$.

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.[4]

IDDFS has a bidirectional counterpart,[1]^: 6 which alternates two searches: one starting from the source node and moving along the directed arcs, and another one starting from the target node and proceeding along the directed arcs in opposite direction (from the arc's head node to the arc's tail node). The search process first checks that the source node and the target node are same, and if so, returns the trivial path consisting of a single source/target node. Otherwise, the forward search process expands the child nodes of the source node (set ${\displaystyle A}$), the backward search process expands the parent nodes of the target node (set ${\displaystyle B}$), and it is checked whether ${\displaystyle A}$ and ${\displaystyle B}$ intersect. If so, a shortest path is found. Otherwise, the search depth is incremented and the same computation takes place.

One limitation of the algorithm is that the shortest path consisting of an odd number of arcs will not be detected. Suppose we have a shortest path ${\displaystyle \langle s,u,v,t\rangle .}$ When the depth will reach two hops along the arcs, the forward search will proceed to ${\displaystyle v}$ from ${\displaystyle u}$, and the backward search will proceed from ${\displaystyle v}$ to ${\displaystyle u}$. 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:

Bidirectional IDDFS

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.

Additional difficulty of applying bidirectional IDDFS is that if the source and the target nodes are in different strongly connected components, say, ${\displaystyle s\in S,t\in T}$, if there is no arc leaving ${\displaystyle S}$ and entering ${\displaystyle T}$, the search will never terminate.

The running time of bidirectional IDDFS is given by

and the space complexity is given by

where ${\displaystyle n}$ is the number of nodes in the shortest ${\displaystyle s,t}$-path. Since the running time complexity of iterative deepening depth-first search is ${\displaystyle \sum _{k=0}^{n}b^{k}}$, the speedup is roughly

function Build-Path(s, μ, B) is
    π ← Find-Shortest-Path(s, μ) (Recursively compute the path to the relay node)
    remove the last node from π
    return π ${\displaystyle \circ }$ B (Append the backward search stack)

function Depth-Limited-Search-Forward(u, Δ, F) is
    if Δ = 0 then
        F ← F ${\displaystyle \cup }$ {u} (Mark the node)
        return
    foreach child of u do
        Depth-Limited-Search-Forward(child, Δ − 1, F)

function Depth-Limited-Search-Backward(u, Δ, B, F) is
    prepend u to B
    if Δ = 0 then
        if u in F  then
            return u (Reached the marked node, use it as a relay node)
        remove the head node of B
        return null
    foreach parent of u do
        μ ← Depth-Limited-Search-Backward(parent, Δ − 1, B, F)
        if μ ${\displaystyle \neq }$ null then
            return μ
    remove the head node of B
    return null

function Find-Shortest-Path(s, t) is
   if s = t then
       return <s>
   F, B, Δ ← ∅, ∅, 0
   forever do
       Depth-Limited-Search-Forward(s, Δ, F)
       foreach δ = Δ, Δ + 1 do
           μ ← Depth-Limited-Search-Backward(t, δ, B, F)
           if μ ${\displaystyle \neq }$ null then
               return Build-Path(s, μ, B) (Found a relay node)
       F, Δ ← ∅, Δ + 1