Iterative Deepening Search

search

Definition

Iterative Deepening Search

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

Properties

Completeness

Yes since the limit is increased systematically.

Time Complexity

Let be the branching factor and be the depth of the solution.

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

Space Complexity

Let be the branching factor and be the depth of the solution.

Optimality

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

Example