Iterative deepening search (IDS) runs depth-limited DFS repeatedly with limits 0, 1, 2, … until the goal is found, combining the completeness and optimality of BFS with the small memory of DFS.
Algorithm
IDS(problem):
for limit = 0, 1, 2, ...:
result = DepthLimitedSearch(problem, limit)
if result != cutoff: return result
Example. Find goal G in this tree:
A depth 0
/ \
B C depth 1
/ \ / \
D E F G depth 2
- Limit 0: visit A. Not goal → cutoff.
- Limit 1: visit A, B, C. Not found → cutoff.
- Limit 2: visit A, B, D, E, C, F, G → goal G found at depth 2.
Nodes near the top are generated several times (A three times here), but because most nodes of a tree are at the deepest level, the repeated work is small. The total number of nodes generated is
\[(d)b + (d-1)b^2 + \dots + 1\cdot b^d = O(b^d)\]
For \(b = 10, d = 5\): IDS generates 123,450 nodes versus 111,110 for BFS, only about 11% more.
Properties
- Complete: yes, when \(b\) is finite.
- Optimal: yes, when all step costs are equal (finds the shallowest goal).
- Time: \(O(b^d)\).
- Space: \(O(bd)\), like DFS.
IDS is the preferred uninformed search when the search space is large and the depth of the solution is unknown.