Depth-Limited Search (DLS) — Beginner-Friendly Notes

1. What It Is

DFS with a cutoff depth $l$ — you simply forbid going deeper than $l$. Like DFS, but prevents infinite wandering.

DFS but stop expanding at depth == l

2. Algorithm

function DLS(node, goal, limit):
  if goal_test(node): return success
  if depth(node) == limit: return cutoff  # don't expand deeper
  for child in successors(node): result = DLS(child, goal, limit)

Uses stack like DFS, but depth check.

3. Why It Helps (and its flaw)

• Fixes DFS infinite path problem — won't get stuck in infinite branch.
• New problem: if $l$ < $d$ (goal depth), you miss the solution even though it exists. Too small limit → failure; too large → like DFS again.

Choosing $l$ is the hard part — which leads to Iterative Deepening.

4. Properties

Property	Value
Complete	Yes if $l \ge d$ (goal within limit)
Optimal	No (like DFS, not shallowest)
Time	$O(b^l)$
Space	$O(b \cdot l)$ — linear, like DFS

5. When Used

• When you know max depth (e.g., "chess mate in ≤5 moves").
• As a subroutine inside Iterative Deepening Search (next topic) — that solves the "choose $l$" problem by trying increasing limits.

6. One-Line Summary

DLS is depth-first search bounded by depth $l$, with $O(b \cdot l)$ space and $O(b^l)$ time, complete only when the solution lies within the bound.

7. Quick Self-Check

1. What happens if limit is 2 but goal is at depth 3?
2. Why is DLS still not optimal even when it finds a goal within limit?