Depth-Limited Search: Bounded Depth-First Search
Learn depth-limited search (DLS) for handling infinite state spaces with a depth bound, and how it relates to iterative deepening.
Depth-Limited Search: Bounded Depth-First Search
Depth-Limited Search (DLS) is a modification of depth-first search that imposes a maximum depth limit on the search. This solves the infinite path problem that would otherwise plague DFS in graphs with cycles or infinite depth.
By cutting off the search at depth L, we guarantee the algorithm terminates even in infinite graphs. The trade-off: solutions deeper than L won’t be found, and we need a way to distinguish “cutoff” from “failure.”
Introduction
Depth-Limited Search (DLS) solves one of depth-first search’s most glaring problems: the risk of infinite recursion on graphs with cycles or infinite depth. By imposing a maximum depth bound L, DLS guarantees termination even when exploring infinite state spaces. The trade-off is significant: solutions deeper than L are missed entirely, and DLS cannot distinguish between “goal not found within depth bound” and “goal doesn’t exist.” To distinguish these cases, DLS returns a special CUTOFF marker that enables higher-level algorithms to decide whether to keep searching.
The CUTOFF concept is deceptively simple but powerful. When DLS reaches its depth limit without finding the goal, it returns CUTOFF rather than failure. This distinction enables Iterative Deepening Depth-First Search (IDDFS)—the algorithm that repeatedly runs DLS with increasing depth limits (0, 1, 2, …) until the goal is found. IDDFS combines DFS’s memory efficiency (O(bd) vs BFS’s O(b^d)) with BFS’s completeness and optimality guarantees. For problems where the solution depth is unknown and memory is constrained, IDDFS is often the best search algorithm available.
DLS and IDDFS form the foundation for more advanced search techniques in AI and graph algorithms. They appear in game tree searching with alpha-beta pruning, pathfinding with resource bounds, bounded-depth exploration in infinite state spaces, and as components of bidirectional search variants. Understanding DLS means understanding where to place depth bounds, how to interpret CUTOFF signals, and how iterative deepening transforms an incomplete algorithm into a complete one—all essential knowledge for anyone working with graph search problems.
The Algorithm
from collections import defaultdict
def depth_limited_search(graph, start, goal, limit):
"""
Depth-Limited Search with explicit stack.
Args:
graph: Adjacency list {node: [neighbors]}
start: Starting node
goal: Target node
limit: Maximum depth to search
Returns:
List of path from start to goal, or None if not found
Returns "CUTOFF" if depth limit reached without finding goal
"""
return dls_recursive(start, goal, limit, [start])
def dls_recursive(node, goal, limit, path):
"""
Recursive implementation with path tracking.
CUTOFF is a special sentinel value indicating depth limit was reached.
"""
if node == goal:
return path
if limit <= 0:
return "CUTOFF"
for neighbor in graph.get(node, []):
if neighbor not in path: # Avoid cycles
result = dls_recursive(neighbor, goal, limit - 1, path + [neighbor])
if result == "CUTOFF":
continue # Keep searching other branches
if result is not None:
return result
return "CUTOFF"
def dls_iterative(graph, start, goal, limit):
"""Iterative DLS using explicit stack."""
stack = [(start, 0, [start])] # (node, depth, path)
while stack:
node, depth, path = stack.pop()
if node == goal:
return path
if depth >= limit:
continue
for neighbor in graph.get(node, []):
if neighbor not in path:
stack.append((neighbor, depth + 1, path + [neighbor]))
return None # Not found and no cutoffIterative Deepening: Combining BFS and DFS
def iterative_deepening_dfs(graph, start, goal, max_depth=None):
"""
Iterative Deepening DFS - combines space efficiency of DFS
with BFS's completeness guarantee.
Repeatedly applies DLS with increasing depth limits until goal found.
"""
for depth in range(max_depth if max_depth else float('inf')):
result = depth_limited_search(graph, start, goal, depth)
if result == "CUTOFF":
continue # Try deeper
return result # Either found goal or hit max_depth
return None
def iterative_deepening_with_visited(graph, start, goal, max_depth=None):
"""
IDDFS with full visited tracking across iterations.
Important: nodes visited at depth d don't need to be visited
again at depth d+1.
"""
for depth in range(max_depth if max_depth else float('inf')):
visited = set()
result = iddfs_helper(graph, start, goal, depth, visited)
if result is not None:
return result
return None
def iddfs_helper(graph, node, goal, limit, visited):
if node == goal:
return [node]
if limit <= 0:
return "CUTOFF"
visited.add(node)
for neighbor in graph.get(node, []):
if neighbor not in visited:
result = iddfs_helper(graph, neighbor, goal, limit - 1, visited)
if result == "CUTOFF":
visited.discard(neighbor) # Allow re-visiting in next iteration
continue
if result is not None:
return [node] + result
visited.discard(node)
return "CUTOFF"When to Use DLS
Use DLS when:
- State space is potentially infinite
- You know the goal depth is within a certain bound
- You need bounded exploration (resource constraints)
- You’re implementing Iterative Deepening
Don’t use DLS when:
- Goal depth is unknown and might exceed your bound
- You need shortest path guarantee (use BFS instead)
- The graph is small enough for BFS
DLS vs Other Search Algorithms
| Aspect | BFS | DFS | DLS | IDDFS |
|---|---|---|---|---|
| Time | O(b^d) | O(b^m) | O(b^L) | O(b^d) |
| Space | O(b^d) | O(bm) | O(bL) | O(bd) |
| Complete | Yes | No | No | Yes |
| Optimal | Yes* | No | No | Yes* |
| Memory | High | Low | Low | Low |
*b = branching factor, d = solution depth, m = max depth, L = depth limit
Trade-off Analysis
When choosing DLS over other search algorithms, consider these key trade-offs:
| Trade-off | DLS | DFS | BFS | IDDFS |
|---|---|---|---|---|
| Completeness | ❌ Not complete if depth unknown | ❌ Can get stuck in infinite paths | ✅ Always complete | ✅ Always complete |
| Optimality | ❌ Not optimal | ❌ Not optimal | ✅ Shortest path | ✅ Shortest path |
| Space Efficiency | ✅ O(bL) | ✅ O(bm) | ❌ O(b^d) | ✅ O(bd) |
| Depth Guarantee | ✅ Bounded exploration | ❌ No bound | ✅ Finds all depths | ✅ Incremental depth |
| Termination | ✅ Always terminates | ❌ May not terminate | ✅ Always terminates | ✅ Always terminates |
| Implementation Complexity | ✅ Simple | ✅ Simple | ❌ Needs queue | ⚠️ Moderate |
* L = depth limit, b = branching factor, d = solution depth, m = max graph depth
Key insight: DLS trades completeness for guaranteed termination and bounded memory. When you know the goal depth, DLS gives you DFS’s memory efficiency with a termination guarantee. When depth is unknown, IDDFS is preferred as it adds completeness while only re-exploring upper levels (a small constant factor overhead).
Cutoff Handling
The key challenge in DLS is distinguishing failures:
# Python doesn't have null markers in functions elegantly
# So we return a sentinel object
CUTOFF = object() # Singleton sentinel
def search_with_proper_cutoff(graph, start, goal, limit):
result = dls_with_sentinel(graph, start, goal, limit)
if result is CUTOFF:
print("Goal not found within depth limit")
return None
elif result is None:
print("Goal not found (graph exhausted)")
return None
else:
return resultApplications
- Game tree searching: Alpha-beta pruning effectively uses DLS with quiescence search
- Pathfinding with depth bounds: When you only need paths up to certain length
- Planning with horizon: In AI planning, often search within planning horizon
- Network exploration: Crawling with depth limits
Production Failure Scenarios
- Setting limit too shallow: Solutions deeper than limit are missed entirely
- Setting limit too deep: Wastes computation exploring unnecessary depths
- Cycle handling: Must track visited nodes within the search to avoid infinite loops
- Path reconstruction: Must track parent pointers or maintain full path
Quick Recap Checklist
- DLS adds depth limit to prevent infinite recursion
- Returns CUTOFF sentinel when limit reached without finding goal
- Solutions deeper than limit are missed
- IDDFS applies DLS repeatedly with increasing limits
- IDDFS combines BFS completeness with DFS space efficiency
- Effective for finding shortest path when depth is unknown
Interview Questions
The cutoff marker is a special value indicating that the search
reached the depth limit without finding the goal. It distinguishes between
"goal not found but we could keep searching" (cutoff) and "no goal exists in
reachable graph" (failure). In implementation, we return a sentinel value
like "CUTOFF" or a special object. The caller must check for
cutoff to continue to deeper iterations in Iterative Deepening.
Iterative Deepening combines the best of both. Like DFS, it uses only O(bd) space. Like BFS, it explores in increasing depth order, guaranteeing the first solution found is the shallowest. Pure DFS can get stuck in deep branches, while BFS needs O(b^d) space. IDDFS pays a small overhead (re-exploring upper levels at each iteration) but gets completeness and optimality with minimal memory. For searching unknown-depth trees, IDDFS is usually the answer.
For a branching factor b and solution depth d, IDDFS explores approximately O(b^d) nodes—the same as BFS. At depth i, we explore b^i nodes, and summing b^0 + b^1 + ... + b^d = (b^(d+1) - 1) / (b - 1) ≈ b^d for large b. So we pay a small constant factor overhead compared to BFS, but get DFS's space efficiency. This makes IDDFS asymptotically optimal in both time and space for unweighted shortest path problems.
Choose plain DLS when you have a specific depth bound in mind and want to search within that exact limit. IDDFS is for when you don't know the depth and want to find the shallowest solution. If you know the goal is at depth ≤ 5 and you just want to know if it exists, DLS(5) is simpler. If you need the shallowest solution without knowing its depth, IDDFS is better. Also, DLS is useful for bounded rational decision-making where deeper solutions are deemed too costly regardless of quality.
DLS handles cycles by maintaining a visited path — tracking all nodes
on the current search path. In the recursive implementation, the path
list is checked before recursing into a neighbor. If the neighbor is already in the
path, the branch is skipped (if neighbor not in path). This prevents
infinite loops without needing a global visited set, which would be incorrect across
different search branches. Without this check, DLS could loop infinitely even with
a depth limit in graphs containing cycles shorter than the limit.
- Path-tracking prevents re-visiting ancestors
- No global visited set needed (unlike BFS)
- Different branches can revisit nodes via different paths
DLS has a space complexity of O(bL) where b is the branching factor and L is the depth limit. In the recursive implementation, the space is O(bL) because the call stack holds at most L frames, each iterating over up to b neighbors. In the iterative implementation using an explicit stack, it also uses O(bL) space.
- DLS: O(bL) — significantly less than BFS's O(b^d)
- BFS: O(b^d) — must store all nodes at the frontier level
- DFS: O(bm) — similar to DLS but m (max depth) may be larger
- This space advantage is the primary reason DLS/IDDFS is chosen over BFS for large graphs
Yes, DLS can be implemented both recursively and iteratively. The recursive approach
is cleaner and naturally tracks the depth limit by passing limit - 1 in each call,
but risks stack overflow for deep limits. The iterative approach uses an explicit
stack of (node, depth, path) tuples, avoiding recursion limits and giving more control over
the search order.
- Recursive: simpler code, natural depth tracking, risk of stack overflow
- Iterative: more complex, explicit stack, no recursion depth issues
- Both produce the same results; choose based on depth limit size and language constraints
A too-shallow limit causes DLS to miss solutions entirely — it returns CUTOFF even though the goal exists at a deeper level. This is the classic false-negative problem. A too-deep limit wastes computation exploring unnecessary depths, degrading performance without bound, though DLS still terminates.
- Too shallow: missed solutions, false negatives (returns CUTOFF)
- Too deep: wasted computation, approaches DFS behavior
- IDDFS solves this by trying all limits incrementally
- Choosing the right L requires domain knowledge or adaptive approaches
Quiescence search extends DLS beyond the normal depth limit when the current game position is "noisy" — e.g., undecided captures in chess. Instead of a hard cutoff at depth L, quiescence search continues until the position becomes "quiet" (no tactical sequences). This applies DLS concepts adaptively: the depth limit isn't a strict number but context-dependent.
- Standard DLS: hard depth cutoff, may miss tactical sequences
- Quiescence search: variable-depth cutoff based on position stability
- Core concept is the same — bounded search — but with an adaptive, content-aware bound
DLS shines in scenarios with known depth bounds or resource constraints:
- Web crawling: Respect robots.txt crawl-depth limits while avoiding infinite spider traps
- Compiler AST analysis: Bounded recursion-depth checks to prevent stack overflows in static analysis
- Game tree search: Alpha-beta pruning with a fixed ply depth, extended by quiescence search
- Database query planning: Bounded join-enumeration depth in query optimizers
- AI planning with horizons: Planning within a fixed horizon where deeper plans are too costly or change too frequently
Depth-First Search has no termination guarantee in graphs with cycles or infinite paths — it can explore forever by following deep branches. Depth-Limited Search guarantees termination at depth L by cutting off exploration beyond the limit. This makes DLS suitable for scenarios where infinite loops are possible, while pure DFS is only safe for trees or graphs with known finite depth. The depth limit acts as a safety bound that prevents the algorithm from getting lost in infinite state spaces.
- DFS: May not terminate in cyclic or infinite graphs
- DLS: Always terminates after exploring all nodes within depth L
- DLS returns "CUTOFF" when limit is reached, distinguishing bounded failure from actual failure
To find all solutions within a depth bound, modify DLS to collect results instead of returning on first match. In the recursive implementation, when node == goal, add the path to a solutions list rather than returning. Continue exploring other branches even after finding a solution. For the iterative version, exhaust the stack before returning. This approach explores the entire bounded space and returns every valid path from start to goal within depth L.
- Collect all paths reaching the goal before returning
- Continue recursing on siblings after finding a solution
- Use a solutions list passed by reference or as a global accumulator
- Return the list (possibly empty for no solutions) instead of a single path
The CUTOFF sentinel is essential because it distinguishes two fundamentally different situations: "goal not reachable within depth L but might exist deeper" (cutoff) vs. "goal not reachable in the entire explored space" (failure). If both returned None, Iterative Deepening couldn't know when to stop — it would assume failure and terminate when it should continue deeper. CUTOFF tells IDDFS to increment the depth limit and try again; None tells it that the graph is exhausted.
- CUTOFF = "search was bounded, try deeper" → IDDFS continues
- None = "search exhausted all reachable nodes, stop" → IDDFS terminates
- This distinction enables IDDFS's completeness guarantee
The overhead is O(b^(d-1)) which is dominated by the deepest level O(b^d). At level i, we explore b^i nodes, and summing 0 to d-1 gives (b^d - 1)/(b - 1), which is less than b^d for b > 1. The re-explored nodes are a small constant fraction of total work. In exchange, IDDFS gets BFS's completeness and optimality with DFS's O(bd) space. For large branching factors, this constant-factor overhead is negligible compared to BFS's exponential space requirement.
- Upper levels re-explored: (b^d - 1)/(b - 1) ≈ b^d / (b - 1)
- Deepest level: b^d nodes
- Total: ~b^d * (1 + 1/(b-1)) ≈ b^d for large b
Yes, bidirectional DLS is powerful: run DLS from start and goal simultaneously, both with depth limits L1 and L2. If they meet in the middle, we have a path. This reduces time complexity to O(b^(d/2)) from O(b^d) if the meet point is near the middle. The challenge is ensuring both searches find a meeting point before hitting their limits, which requires good depth bound estimation. For known depth solutions, bidirectional DLS can be significantly faster.
- Two bounded searches from opposite ends
- Time: O(b^(d/2)) if meet point is balanced
- Space: O(b^(d/2)) combined (each side)
- Requires a goal node to search backward from
Basic DLS doesn't account for edge weights — it counts depth in edges, not cumulative cost. For weighted graphs, iterative deepening on cost bounds (IDA*) replaces depth with path cost: increment the cost limit until the goal is found. This is fundamentally different because a shorter path in edges might have higher cost than a longer path. DLS concepts transfer but the bound metric changes from hop-count to path-cost.
- Unweighted: bound = number of edges from start
- Weighted: bound = cumulative path cost g(n)
- IDA* uses cost-bound instead of depth-bound
- Heuristic h(n) guides which branches to explore first
When a node is at depth = limit, DLS checks if it's the goal, then returns CUTOFF without exploring its children. The node itself is evaluated (to check if it's the goal), but no further recursion occurs. This means solutions exactly at the limit are found — the limit is inclusive for goal checking but exclusive for expansion. The check if limit <= 0 returns CUTOFF before exploring children, but if node == goal is checked before the limit test.
- Goal at depth L is found (checked before limit test)
- Children of nodes at depth L are not explored
- Limit is inclusive for goals, exclusive for expansion
Consider a maze with a known exit depth where the solution path is exactly 50 edges long, but the graph is enormous (millions of nodes). BFS would need to explore all nodes at depths 0 through 50, storing millions of nodes at the frontier — requiring gigabytes of memory. DLS with limit=50 explores only along valid paths, using O(b*50) space regardless of total graph size. If you know the solution depth is bounded, DLS's memory efficiency is decisive.
- Memory: BFS = O(b^50), DLS = O(b*50)
- BFS gets stuck with exponential memory growth
- DLS explores only along solution-bound paths
- Works when depth bound is known and relatively small
Path tracking via the path list enables cycle detection but is O(L) for membership checks with list — each neighbor not in path scans the entire current path. For deep searches with high branching factors, this adds up. Optimization options: use a set for O(1) lookup while maintaining path for reconstruction, or use parent pointer arrays for O(1) path reconstruction without path list overhead. The performance impact is most noticeable for deep limits with large branching factors.
- List membership: O(L) per check
- Set for visited: O(1) but loses path order
- Parent pointers: O(1) reconstruction without storing full path
- Trade-off: complexity vs memory vs reconstruction needs
For time-limited game AI, use DLS with iterative deepening and track the best solution found so far. Start at depth 1 and increment depth as time permits. If time runs out mid-search, return the best completed solution. For alpha-beta pruning, combine with move ordering — explore the best-looking moves first at each depth so earlier cutoffs happen. The adaptive approach: every completed depth gives you a valid move, with deeper iterations potentially finding better solutions.
- IDDFS provides natural anytime algorithm
- Track best move found at each completed depth
- Combine with move ordering for better pruning
- Return best completed result when time expires
- Quiescence search extends beyond fixed depth for tactical stability
Further Reading
To deepen your understanding of DLS and related search algorithms, explore these topics:
- Iterative Deepening A* (IDA*) — Combines IDDFS with heuristic guidance for informed search, using a cost-bound instead of depth-bound. Ideal for puzzles like the 15-puzzle where the state space is large but well-structured.
- Bidirectional Search — Searches forward from start and backward from goal simultaneously, often meeting in the middle for exponential speedup. Can be combined with depth-bounding for memory-efficient variants.
- Heuristic Search (A*) — For weighted graphs, A* uses f(n) = g(n) + h(n) to guide search efficiently toward the goal. DLS concepts appear in depth-bounded A* variants.
- Constraint Satisfaction Problems (CSPs) — Depth-bounded backtracking (a form of DLS) is fundamental to solving CSPs like Sudoku and N-Queens with bounded lookahead.
- Quiescence Search in Game AI — Extends DLS beyond the horizon when the current position is still in flux (e.g., undecided captures in chess), creating an adaptive, content-aware depth limit.
- Monte Carlo Tree Search (MCTS) — Modern game-playing algorithms that use selective depth-limited rollouts guided by an exploration-exploitation trade-off (UCT).
For practical implementations, study how DLS and depth-bounding techniques appear in:
- Web crawlers: Respecting crawl-depth limits from robots.txt while avoiding spider traps
- Database query optimizers: Bounded join-enumeration depth for efficient query planning
- Compiler static analysis: Recursion-depth limits in AST traversal and cycle detection
- Network protocol verification: Bounded model checking with depth limits to verify finite-state systems
Conclusion
Depth-Limited Search adds a depth bound to DFS to prevent infinite recursion, returning a CUTOFF sentinel when the limit is reached without finding the goal. Iterative Deepening DFS combines BFS completeness with DFS space efficiency by running DLS repeatedly at increasing depths until the goal is found. DLS works best when you know solutions exist within a bounded depth; IDDFS is preferable when the depth is unknown and you need the shallowest solution.
Category
Related Posts
Depth-Limited & Bidirectional Search
Explore search algorithm variants: depth-limited search for bounded recursion, and bidirectional search for O(b^d/2) complexity improvement.
Articulation Points & Bridges in Graphs
Find critical vertices and edges whose removal disconnects the graph using DFS-based algorithms.
Bellman-Ford Algorithm: Shortest Paths with Negative Weights
Learn the Bellman-Ford algorithm for single-source shortest paths including negative edge weights and negative cycle detection.