Depth-Limited Search
What you'll learn: How to prevent DFS from getting lost in infinite-depth paths by imposing a maximum depth boundary.
The Core Idea
Depth-First Search can get stuck exploring infinitely deep branches or waste time on very deep paths that are unlikely to contain solutions. Depth-Limited Search (DLS) solves this by adding a hard depth limit l — the search will not explore any node deeper than l levels from the start state.
Think of it like exploring a cave system with a rope of fixed length: you can only venture as far as your rope allows, then you must backtrack and try another tunnel.
How It Works
DLS is identical to DFS, but tracks the current depth during recursion or iteration. When a node at depth l is reached, its successors are not expanded — even if they haven't been explored yet. The algorithm then backtracks to explore other branches within the limit.
Trade-offs
- Guarantees termination even in infinite state spaces (unlike vanilla DFS)
- May fail to find a solution if the limit is too shallow and the goal lies deeper
- Not optimal: returns the first solution found within the limit, which may not be the shallowest
- Completeness: complete only if the solution depth ≤
l
Choosing the Limit
The depth limit must balance exploration and termination. Too shallow, and you miss solutions; too deep, and you lose the termination guarantee. Often used when you have domain knowledge about solution depth or as part of iterative deepening strategies.
Key Takeaway: Depth-Limited Search is DFS with a safety valve — a maximum depth l prevents infinite exploration but risks missing deeper solutions.