Iterative Deepening Search

Iterative Deepening Search combines the best of both bfs (optimality and completeness) and dfs (low memory usage).

Essentially it's a depth limited search, starting with a depth of 1, that is repeatedly run with +1 dept cut-off. This means it visits things in a bfs order, but doesn't store them in memory.

It does mean early nodes are expanded multiple times, but usually

Classification

  • Complete: Yes
  • Time Complexity: O$O(b^d)$
    • $(d+1)b^0 + (d)b^1 + (d-1)b^2 + ... + (2)b^{d-1} + b^d = O(b^d)$
    • Essentially, you visit the first level d+1 times, then the 2nd d, the third, d-1…etc
  • Space Complexity: O(bd)
  • Optimality: Yes, for an unweighted (or all paths = weight) graph