## Definition **Iterative Deepening Search (IDS)** runs successive depth-limited [[Depth-First Search|DFS]] passes with increasing depth limit $\ell = 0, 1, 2, \dots$ until a goal is found. Combines DFS's space efficiency with BFS's completeness and optimality (for uniform costs). ## Algorithm ``` for ℓ = 0, 1, 2, ...: result ← DepthLimitedDFS(initial_state, ℓ) if result is a solution: return result ``` ## Properties - **Complete:** yes (finite branching). - **Optimal:** yes, for uniform action costs (same as BFS). - **Time:** $O(b^d)$. - **Space:** $O(bd)$ — the DFS advantage. ## Why "Wasteful" Isn't Wasteful Naively, redoing earlier levels each iteration sounds expensive. In fact, the cost of the final iteration dominates: $ N_{\text{IDS}} = (d+1) \cdot 1 + d \cdot b + (d-1) \cdot b^2 + \dots + 1 \cdot b^d \approx \frac{b^d \cdot b}{(b-1)^2} $ For $b = 10$, IDS expands ~11% more nodes than BFS in total — a small overhead for the space saving. ## When to Use The default for **uninformed search** in production when: - State space is large. - Solution depth is unknown. - Memory matters. ## Variants - **Iterative Deepening A\*** ([[IDA Star Algorithm]]) replaces depth limit with f-cost limit; the heuristic analog. ## Related - [[Uninformed Search]] - [[Breadth-First Search]] - [[Depth-First Search]] - [[IDA Star Algorithm]]