1. Iterative Deepening Search

Iterative deepening depth-first search (IDS or IDDFS) resolves the core tension between breadth-first search (BFS) and depth-first search (DFS): BFS is optimal and complete but requires \(O(b^d)\) memory; DFS uses \(O(bd)\) memory but is neither complete (in infinite spaces) nor optimal. IDS achieves the best of both worlds — completeness, optimality (for unit step costs), and linear memory — by running a series of depth-limited DFS calls with increasing depth limits ¹².

The algorithm was independently described by Korf (1985) and has since become the standard baseline for uninformed state-space search. Its iterative deepening A* (IDA*) extension applies the same idea to heuristic search.

1.1 Algorithm

1.1.1 Depth-Limited Search (DLS)

DLS is a standard DFS that stops exploring any branch once the depth of the current node reaches limit \(\ell\). It returns FOUND (solution), CUTOFF (limit was hit; solution may exist deeper), or FAILURE (no solution in this search tree).

DLS(node, goal_test, succ, limit):
  if goal_test(node.state):
    return FOUND, node.path
  if limit == 0:
    return CUTOFF, None
  cutoff_occurred = False
  for each (child, cost) in succ(node.state):
    result, path = DLS(child_node(node, child), goal_test, succ, limit - 1)
    if result == CUTOFF:
      cutoff_occurred = True
    elif result != FAILURE:
      return FOUND, path
  if cutoff_occurred:
    return CUTOFF, None
  return FAILURE, None

1.1.2 Iterative Deepening

IDS(start, goal_test, succ):
  for limit = 0, 1, 2, ...:
    result, path = DLS(make_node(start), goal_test, succ, limit)
    if result == FOUND:
      return path
    if result == FAILURE:     // no solution anywhere
      return FAILURE
    // result == CUTOFF → increase limit and retry

1.2 Complexity Analysis

1.2.1 Redundant Node Generation

Nodes at depth \(\leq d-1\) are generated multiple times — once per IDS iteration that reaches them. A node at depth \(k\) is generated in iterations \(\ell = k, k+1, \ldots, d\), i.e. \(d - k + 1\) times.

Total nodes generated:

For large \(b\) the sum is dominated by the last term: \(N(d) \approx b^d \cdot \tfrac{b}{b-1}\) ¹.

Example \(b = 10\), \(d = 5\): BFS generates \(1 + 10 + 100 + 1000 + 10000 + 100000 = 111\,111\) nodes. IDS generates \(6 + 50 + 400 + 3000 + 20000 + 100000 = 123\,456\) nodes — only ~11 % more.

The overhead factor \(b/(b-1)\) approaches 1 as \(b\) grows, so IDS is asymptotically as efficient as BFS.

1.3 Completeness and Optimality

Completeness: For any finite branching factor \(b\) and shallowest goal at depth \(d\), the IDS iteration at \(\ell = d\) will find it, as DLS with limit \(d\) is equivalent to BFS in that DLS explores every node at every depth up to \(d\). \(\square\)

Optimality (unit costs): IDS finds the shallowest goal first (at iteration \(\ell = d\)), which has the fewest edges. With uniform step costs this minimises total path cost. \(\square\)

1.4 IDA* (Extension)

IDA* replaces the depth limit with an \(f\)-cost threshold. Each iteration discards nodes with \(f(n) = g(n) + h(n) > \text{threshold}\); the threshold for the next iteration is the minimum \(f\)-value that was cut off. With an admissible heuristic \(h\), IDA* is optimal and uses only \(O(bd)\) space, making it the algorithm of choice for large puzzle problems (e.g. 15-puzzle, Rubik's cube).

1.5 Practical Notes

• Visited states: Vanilla IDS does not maintain a visited set, so it may re-visit states on the same path (though not across iterations). For graph search, a per-iteration closed list can be added, but it restores \(O(b^d)\) space.
• Cycle detection: A simple optimisation is to avoid the immediate parent on the current path (\(O(d)\) stack check).
• Preferred over BFS/DFS when: memory is limited but optimal solutions are required, and branching factor is large.

1.6 Interactive Demo

The canvas shows IDS on a binary tree of depth 5. Each iteration sweeps through the tree up to the current limit; nodes are coloured by their status (grey = unvisited, gold = searching, blue = done for this iteration, green = goal found). Press Step to advance one DLS node at a time, or Play to animate.