Iterative Deepening Search
Motivation
Breadth-first search finds the shallowest solution but requires \(O(b^d)\) memory. Depth-first search uses only \(O(bm)\) memory but is not optimal. Iterative deepening search (IDS), also called iterative deepening depth-first search (IDDFS), achieves the best of both: it finds the shallowest solution using only linear memory, by running a depth-limited search at each successive depth limit (Russell and Norvig 2020).
Problem
Given a graph \(G = (V, E)\) with branching factor \(b\), a start vertex \(s\), and a goal predicate \(P\), find a vertex \(g\) satisfying \(P\) that is closest to \(s\) (minimum number of edges from \(s\) to \(g\)). For unit-cost edges this is the minimum-cost solution. The graph may be infinite, but the solution depth \(d\) is assumed finite.
Key Ideas
IDS exploits an asymmetry in tree-shaped state spaces: nodes near the bottom of the tree vastly outnumber nodes near the top. In a tree with branching factor \(b\), the number of nodes at depth \(\ell\) grows as \(b^\ell\), so the leaves of the depth-\(d\) tree already contain a \((1-1/b)\) fraction of all nodes visited. Running a fresh depth-limited search at each depth re-explores the shallow nodes — but their cost is dominated by the deepest layer, so the total work is only a constant factor more than visiting the bottom layer once.
This gives IDS the memory profile of DFS (only the current path is stored, so \(O(bd)\) space) and the optimality of BFS (depths are tried in order, so the first solution found is shallowest). The overhead is a factor of \(b/(b-1)\) in time — exactly the geometric series sum — which is small for any reasonable branching factor.
The trade is worth taking whenever memory is a real constraint. BFS frontiers grow exponentially in \(d\) and hit machine limits long before time does.
Algorithm
IDS repeatedly calls depth-limited search (DLS) with an increasing limit.
for L = 0, 1, 2, ...:
result = DLS(s, L)
if result is a node:
return result
return failureEach call to DLS is a standard DFS that refuses to expand any node beyond depth \(L\).
Walkthrough
Three iterations on a small tree
A binary tree of depth \(2\) with goal node \(F\) at depth \(2\). IDS runs three DLS passes; each panel below shows which nodes are expanded at that depth limit. Visited nodes are filled, unvisited nodes are outlined only, and the goal \(F\) is highlighted in the iteration where it is found.
The total work is \(1 + 3 + 6 = 10\) node visits, compared to \(7\) for a single BFS that finds \(F\) — the constant-factor overhead from re-exploring shallower depths. As \(b\) and \(d\) grow, this overhead is bounded by \(b/(b-1)\), so for branching factor \(b = 2\) the worst-case overhead is a factor of \(2\). Note that \(G\) is never visited even at \(\ell = 2\) because DLS halts as soon as it finds the goal.
Correctness
Completeness. If a solution exists at finite depth \(d\), the iteration with \(L = d\) will find it: DLS at limit \(d\) enumerates every node at depth \(\le d\), so any goal at depth \(d\) is reached.
Optimality. IDS returns a solution at the minimum depth, since it tries all depths in order and halts on the first hit. For unit-cost graphs this is the optimal-cost solution. (proof)
Complexity and Tradeoffs
Time. Although earlier depths are re-explored on each iteration, the total work is dominated by the last iteration. The number of nodes generated is:
\[ N = \sum_{\ell=0}^{d} b^{\,\ell} \cdot (d - \ell + 1) \;=\; O(b^d). \]
The repeated work increases the constant factor by at most \(b/(b-1)\) compared to BFS. (proof)
Space. Each DLS call uses \(O(b\ell)\) memory. The maximum is \(O(bd)\) — linear in the solution depth, compared to \(O(b^d)\) for BFS.
Comparison with BFS.
| BFS | IDS | |
|---|---|---|
| Complete | yes | yes |
| Optimal (unit cost) | yes | yes |
| Time | \(O(b^d)\) | \(O(b^d)\) |
| Space | \(O(b^d)\) | \(O(bd)\) |
IDS strictly dominates BFS in memory use with identical asymptotic time. The constant-factor time overhead is the price of the linear memory.
When to Use It
- Unknown solution depth, memory matters. This is the canonical use case — IDS is the default uninformed search for game-tree and planning problems where the BFS frontier would not fit in memory.
- Find the nearest node satisfying a property \(P\). Run IDS until DLS reports success; the corresponding \(L\) is the minimum depth at which any such node exists.
- Find all minimum-depth nodes satisfying \(P\). Run DLS at the first successful \(L\) to completion and collect every depth-\(L\) node where \(P\) holds, instead of stopping at the first match.
- Find all nodes satisfying \(P\) regardless of depth. Don’t use IDS — a plain DFS with cycle detection is simpler and avoids the repeated work.
- Informed search available. Prefer A* when a good heuristic exists; IDS has no way to use one.