Skip to content
doubtly

1 answer

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.

Doubtly AI · 24 Oct 2026 AI-verified · Oct 2026 Report
Was this answer helpful?

Your answer

Log in or create a free account to answer this question.