Iterative Deepening Search
The problem with BFS and DFS
| Strategy | Space | Completeness |
|---|---|---|
| DFS | O(d) | Incomplete for infinite trees |
| BFS | O(bd) | Complete, finds nearest solution |
For a branching factor b = 2 at depth d = 20, BFS stores about 220 ≈ 1,000,000 nodes. DFS stores about 20. But DFS might never find a solution in an infinite tree.
Iterative deepening
Iterative deepening performs repeated depth-first searches with increasing depth bounds:
- Search to depth 1. If no solution, discard results.
- Search to depth 2. If no solution, discard results.
- Search to depth 3. And so on…
Analysis
| Property | Value |
|---|---|
| Space | O(d) - same as DFS |
| Completeness | Yes - same as BFS |
| Optimality | Finds nearest solution first |
| Time overhead | b/(b − 1) relative to BFS (if b > 1) |
The time overhead is a constant factor. For binary trees (b = 2), the overhead is 2/(2−1) = 2: iterative deepening does at most twice the work of BFS. In exchange, it reduces space from exponential (O(bd)) to linear (O(d)).
Why discarding is acceptable
There are bd+1 nodes at level d+1. If b ≥ 2, this number exceeds the total number of nodes at all previous levels combined:
bd+1 > (bd+1 − 1)/(b − 1) (for b ≥ 2)
The majority of the work is always at the deepest level. Recomputation of shallower levels is therefore cheap relative to exploring the new depth. Korf showed the total time is only b/(b−1) times that of BFS.
Limitation
If b ≈ 1 (a nearly linear tree), iterative deepening loses its advantage. The number of nodes grows slowly, so the recomputation overhead becomes significant.