Depth Limited Search

Depth Limited Search is a basic dfs with a cut-off limit that it stops expanding after.

The problem is how to pick a good limit.

Classification

  • Completeness: Yes if the solution is above the cut-off limit, as there are no infinite loops anymore.
  • Time Complexity: $O(b^l)$ (l = the depth limit)
    • It's $1 + b^1 + b^2 + ... + b^{d-1} + b^d$ (sum the number of nodes in each layer, down to the cut-off point.
  • Space Complexity: $O(bl)$ (linear space, like dfs)
  • Optimality: Not optimal, as with dfs it can find a suboptimal solution first