Iterative Deepening DFS

Iterative deepening DFS (IDDFS) runs depth-limited DFS with depth 0, then 1, then 2, ..., until it finds a goal.

Algorithm

``` function IDDFS(initial, goal): for depth in 0, 1, 2, ...: result = depth_limited_DFS(initial, goal, depth) if result != cutoff: return result

function depth_limited_DFS(state, goal, depth): if state is goal: return [state] if depth == 0: return cutoff for action in actions(state): next = transition(state, action) result = depth_limited_DFS(next, goal, depth - 1) if result != cutoff: return result return cutoff ```

Properties

• Complete: yes (on finite branching).
• Optimal: yes for uniform step costs (same as BFS).
• Time: $O(b^d)$ — same as BFS in big-O. Each depth $i$ does at most $b^i$ work; total is $\sum_{i=0}^d b^i = O(b^d)$.
• Space: $O(bd)$ — only the current DFS path is in memory.

Why repeated work doesn't hurt asymptotically

The deepest level dominates the total work. Even though IDDFS revisits shallower levels many times, $b^d \gg b^{d-1} + b^{d-2} + \dots$, so the redundant work is at most a small constant factor.

Concretely: at depth $d$ with branching factor 10, IDDFS does roughly 1.11× the work of BFS but uses only $O(d)$ memory instead of $O(10^d)$.

When to prefer IDDFS

• Memory is binding (BFS would OOM).
• You don't know the depth of the solution in advance.
• The tree is reasonably balanced.

If you do know the depth, plain depth-limited DFS at that depth is cheaper. If memory isn't an issue and step costs are uniform, BFS is simpler.

In informed search

The same idea extends to A* as IDA* (iterative deepening A*): repeated DFS with a cost cutoff instead of a depth cutoff. The 15-puzzle and many AI-planning benchmarks use IDA* for exactly this memory reason.