Iterative Deepening Search

search

Definition

Iterative Deepening Search

Iterative deepening search is an extension of depth-limited search that iteratively increases the limit $\ell$.

Properties

Completeness

Yes since the limit is increased systematically.

Time Complexity

Let $b$ be the branching factor and $d$ be the depth of the solution.

$$(d+1)b^0+d{b}^1+(d-1)b^2+\cdots +b^d=O(b^d)$$

IDS is mildly ($\approx 11\%$) more expensive than BFS. However, BFS with goal test at expansion time is much worse.

Space Complexity

Let $b$ be the branching factor and $d$ be the depth of the solution.

$$O(bd)$$

Optimality

Yes, if the step cost is $=1$. IDS can be modified to explore a uniform-cost tree.

Example