Depth-First Iterative Deepening (DFID)

The Simplest Explanation

DFS has linear space but finds bad paths. BFS finds shortest paths but explodes in memory. DFID asks a cheeky question:

What if we just... run DFS many times, each time allowing one more level of depth?

Iteration 1 searches to depth 0. Iteration 2 restarts from scratch, searching to depth 1. Iteration 3 restarts again, depth 2. Each run is plain depth-bounded DFS (linear space!), but the sequence mimics BFS — the goal is found at its shortest depth.

The Algorithm

Each iteration runs depth-bounded DFS: nodes carry triples (node, parent, depth). A child's depth is parent's depth + 1. If depth = bound, don't generate children.

for bound = 0, 1, 2, ... :
    result = DepthBoundedDFS(S, bound)
    if result found a goal: return it
    if node count didn't grow vs previous iteration: report failure

The node-count check handles termination on finite spaces: if two consecutive iterations visit the same number of nodes, no deeper nodes exist.

Interactive Trace

Goal G sits at depth 2. Watch three restarts find it — and count the cost:

Key Observations

1. Restarts are total: iteration 2 re-visits S, A, B, C even though they were seen in iteration 1.
2. The answer is optimal: G pops out at depth 2 — same as BFS would give.
3. Memory stays linear: during any single moment, Open holds at most one path plus siblings — never an entire level.
4. The overhead is real but small: this tree needed 13 visits vs 8 for one full search. In big uniform trees the ratio shrinks toward $\frac{b}{b-1}$.

Does DFID Always Return the Shortest Path?

Subtle point — it depends on pruning.

Because depth-bounded DFS uses the Closed list, it can lock in a longer path: node D might be closed via S→A→C→D first; when iteration 2 later tries S→B→D (shorter!), D is already closed and skipped.

The fix: do NOT use Closed to prune in DFID. Keep parent pairs on Closed purely for path reconstruction, but let Open accept duplicates. Store the whole path inside each node representation — when the goal appears, the path comes free.

For configuration problems (N-Queens, SAT, Map Coloring) paths don't matter, so this subtlety is irrelevant.

The Overhead Analysis

"Re-explore everything every iteration? Wasteful!" — surprisingly, no.

Consider a tree where the final iteration reaches $L$ leaves at depth $d$. Every iteration before it only re-visits internal nodes. Total visits:

$L + I \quad \text{vs} \quad L \text{ for BFS}$

$\frac{\text{DFID work}}{\text{BFS work}} = \frac{b}{b-1}$

In an exponentially growing tree, leaves vastly outnumber internal nodes — so revisiting internals is pocket change. For realistic branching factors, DFID is nearly free insurance against BFS's memory blowup.

Why Blind Search Still Loses

DFS, BFS, DFID all share one fatal flaw: they are oblivious to the goal. DFS explores identically whether the goal is one step right or a million steps left. Against combinatorial explosion — level $d$ holding $b^d$ nodes, the Hydra that grows heads faster than you cut them — blind strategies eventually drown.

The escape: give the algorithm a sense of direction with a heuristic function. That leads to Best-First Search, Branch & Bound, and ultimately A* (Weeks 3–5).