---
title: "Advantage of depth limit search"
subject: "Artificial Intelligence"
chapter: 3
key: "semester_6/artificial_intelligence:depth-limit-search-advantage"
source: https://www.bctengineer.com/q/semester_6/artificial_intelligence/depth-limit-search-advantage
site: BCT Engineering
---

# Advantage of depth limit search

Artificial Intelligence · Chapter 3: Search Techniques

- Asked in: 2071 Bhadra, 4+4 marks
- Video: [Depth-Limited Search (DLS) Explained | Uninformed Search in AI](https://www.youtube.com/watch?v=jbw6nWFWxDk) — Gate Smashers
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_6/artificial_intelligence/depth-limit-search-advantage
- Whole chapter: https://www.bctengineer.com/md/semester_6/artificial_intelligence/chapter-3

## Question

What is the advantage of depth limit search? Compare it with other search strategies.

## Short answer

Depth-limited search is DFS with a fixed depth limit, so it terminates even in infinite or cyclic spaces and uses only O(b*l) memory. It is complete when the limit is at least the goal depth, though not optimal, and it is the basis of iterative deepening.

## Answer

#### Depth-limited search (DLS)
Depth-limited search is depth-first search with a predetermined depth limit ℓ. Nodes at depth ℓ are treated as if they have no successors.

```text
DLS(node, goal, limit):
  if node is goal: return solution
  if limit == 0:   return cutoff
  for each child of node:
      result = DLS(child, goal, limit-1)
      if result is a solution: return result
  return cutoff (if any child was cut off) else failure
```

#### Advantages
1. **Solves the infinite-path problem of DFS:** DFS can go down an endless branch (or loop in a cyclic graph) and never return. The depth limit forces it to stop and backtrack, so the search always terminates.
2. **Low memory:** like DFS it needs only O(b·ℓ) space, far less than BFS (O(b^d)).
3. **Simple to implement**, and works well when the depth of the solution is known or can be estimated (e.g. in a graph with N nodes the shortest path is at most N − 1; for a route problem the diameter of the map is known).
4. It is the building block of **iterative deepening search**, which tries ℓ = 0, 1, 2, ... and combines the advantages of BFS and DFS.

**Disadvantages:** incomplete if ℓ < d (the goal is deeper than the limit); not optimal if ℓ > d; choosing ℓ is difficult.

#### Comparison with other strategies
(b = branching factor, d = depth of shallowest goal, m = maximum depth, ℓ = depth limit)

| Strategy | Complete | Optimal | Time | Space |
|---|---|---|---|---|
| BFS | Yes | Yes (equal costs) | O(b^d) | O(b^d) |
| Uniform-cost | Yes | Yes | O(b^(1+C*/ε)) | O(b^(1+C*/ε)) |
| DFS | No | No | O(b^m) | O(b·m) |
| **Depth-limited** | Yes if ℓ ≥ d | No | O(b^ℓ) | O(b·ℓ) |
| Iterative deepening | Yes | Yes (equal costs) | O(b^d) | O(b·d) |
| Bidirectional | Yes | Yes (equal costs) | O(b^(d/2)) | O(b^(d/2)) |

Thus DLS is preferred over BFS when memory is limited and a depth bound is known, and it is safer than plain DFS.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What is depth-limited search?
   A. BFS with a bounded queue
   B. DFS with a predetermined depth limit where nodes at the limit are treated as having no successors
   C. A* with a bounded heuristic
   D. Bidirectional search with two limits
   Answer: B. DLS is DFS that stops expanding at depth ℓ. (Key point: Depth-limited search)

2. What main problem of DFS does depth-limited search solve?
   A. Needing too much memory
   B. Going down an endless branch or looping, so it never terminates
   C. Not using a stack
   D. Finding the shallowest goal
   Answer: B. The depth limit forces the search to stop and backtrack, so it always terminates. (Key point: Main advantage)

3. When is depth-limited search incomplete?
   A. When ℓ is larger than d
   B. When ℓ < d, because the goal is deeper than the limit
   C. When the branching factor is 1
   D. When it uses recursion
   Answer: B. If the limit is smaller than the shallowest goal depth, the goal is never reached. (Key point: Disadvantage)

4. Compared with BFS, DLS has which space complexity and relation to iterative deepening?
   A. O(b^ℓ) space; unrelated to iterative deepening
   B. O(b·ℓ) space; it is the building block of iterative deepening
   C. O(b^d) space; it replaces BFS completely
   D. O(b^(d/2)) space; it is bidirectional
   Answer: B. DLS needs only O(b·ℓ) memory like DFS, and iterative deepening repeats it with ℓ = 0, 1, 2, ... (Key point: Comparison)

## Related in Artificial Intelligence

- [Informed vs blind search; DFS vs BFS](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Ainformed-vs-blind-search-dfs-bfs) — Artificial Intelligence, chapter 3
- [Searching: BFS vs DFS comparison](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Ablind-search-dfs-bfs-compare) — Artificial Intelligence, chapter 3, asked 5×

## Related in other subjects

- [Sequential vs binary search](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Asequential-vs-binary-search) — Data Structure and Algorithm, chapter 8
- [MoR of T-beam by limit state](https://www.bctengineer.com/question.md?key=semester_7%2Fdesign_of_rcc_structure%3Amor-of-t-beam-by-limit) — Design of RCC Structure, chapter 4
- [Compare and contrast pollution in a city](https://www.bctengineer.com/question.md?key=semester_5%2Fcommunication_english%3Acompare-contrast-pollution-city-nepal) — Communication English, chapter 1
- [Depth at fourth borehole P (coal seam)](https://www.bctengineer.com/question.md?key=semester_4%2Fengineering_geology_ii%3Abh-depth-at-p-coal-seam) — Engineering Geology II, chapter 6