Depth Limited Search

3. Depth Limited Search:

A depth-limited search algorithm is a new uniform search algorithm. The unbounded tree problem happens to appear in the depth-first search algorithm, and it can be fixed by imposing a boundary or a limit to the depth of search domain, this limit is called depth limit. It makes DFS search strategy more refined and organized into a finite loop. We denote this limit by l. Depth-limited search can be called as an extended and refined version of the DFS algorithm to avoid the infinite loop problem or unbounded tree problem.

Depth-limited search can be terminated with two conditions of failure:

  • • standard failure value: It indicates that problem doesn't have any solution.
  • • Cut-off failure value: It indicates no solution for the problem with in a given limit.

  • • Depth-limited search is memory efficient.
  • • Depth-limited search also has a disadvantage of incompleteness.
  • • It may not be optimal if the problem has more than one solution.
Time Complexity

Time complexity of DLS algorithm is O(bl).

Space Complexity

Space complexity of DLS algorithm is O(bl)


DLS search algorithm is complete if the solution is above the depth-limit.


Depth-limited search can be viewed as a special case of DFS, and it is also not optimal even if l>d

About the Author

Silan Software is one of the India's leading provider of offline & online training for Java, Python, AI (Machine Learning, Deep Learning), Data Science, Software Development & many more emerging Technologies.

We provide Academic Training || Industrial Training || Corporate Training || Internship || Java || Python || AI using Python || Data Science etc