Iterative Deepening
Definition
Iterative deepening repeatedly performs depth-limited depth-first searches with gradually increased depth limits.
With finite branching and a solution at finite depth, the method finds a shallowest solution. With uniform positive step costs, this solution is also cost-minimal. Memory requirements remain low in the examined tree search model.
Simply explained
Like searching a search tree first to depth 1, then 2, then 3, until a solution appears.
Why it matters in practice
Relevant for search and planning problems with unknown solution depth and limited memory.
Example from business
A planner searches for a short sequence of valid process steps and iteratively increases the maximum plan depth.
Limits and pitfalls
- Repeated work is seen as an error; variable costs are ignored; confused with A* or general iteration.
Origin & history
Korf studied Depth-First Iterative Deepening in 1985 in the brute-force tree search model and analyzed memory requirements and optimality under specified conditions.
Use in mid-sized companies
- Possible application: small discrete planning and search problems, especially with limited memory.
Frequently asked questions
Is IDDFS faster than BFS?
Not generally; an important advantage is low memory usage. When does it find a cost-minimal solution? With finite branching, a solution at finite depth, and uniform positive step costs.
Sources
- Depth-First Iterative-Deepening · Korf (1985), Depth-First Iterative-Deepening
- Autorenarbeit · Korf (1985), Autorenarbeit
Source verification: 10./11.10.2026.
Editorially reviewed on: