EDUCBA Logo

EDUCBA

MENUMENU
  • Explore
    • EDUCBA Pro
    • PRO Bundles
    • Featured Skills
    • New & Trending
    • Fresh Entries
    • Finance
    • Data Science
    • Programming and Dev
    • Excel
    • Marketing
    • HR
    • PDP
    • VFX and Design
    • Project Management
    • Exam Prep
    • All Courses
  • Blog
  • Enterprise
  • Free Courses
  • Log in
  • Sign Up
Home Data Science Data Science Tutorials Data Structures Tutorial Depth Limited Search
 

Depth Limited Search

Priya Pedamkar
Article byPriya Pedamkar

Depth Limited Search

Introduction to Depth Limited Search

Depth limited search is the new search algorithm for uninformed search. 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 the search domain. We will say that this limit as the depth limit, making the DFS search strategy more refined and organized into a finite loop. We denote this limit by l, and thus this provides the solution to the infinite path problem that originated earlier in the DFS algorithm. Thus, Depth limited search can be called an extended and refined version of the DFS algorithm. In a nutshell, we can say that to avoid the infinite loop status while executing the codes, and depth limited search algorithm is being executed into a finite set of depth called depth limit.

 

 

Algorithm

This algorithm essentially follows a similar set of steps as in the DFS algorithm.

Watch our Demo Courses and Videos

Valuation, Hadoop, Excel, Mobile Apps, Web Development & many more.

  1. The start node or node 1 is added to the beginning of the stack.
  2. Then it is marked as visited, and if node 1 is not the goal node in the search, then we push second node 2 on top of the stack.
  3. Next, we mark it as visited and check if node 2 is the goal node or not.
  4. If node 2 is not found to be the goal node, then we push node 4 on top of the stack.
  5. Now we search in the same depth limit and move along depth-wise to check for the goal nodes.
  6. If Node 4 is also not found to be the goal node and depth limit is found to be reached, then we retrace back to nearest nodes that remain unvisited or unexplored.
  7. Then we push them into the stack and mark them visited.
  8. We continue to perform these steps in iterative ways unless the goal node is reached or until all nodes within depth limit have been explored for the goal.

When we compare the above steps with DFS, we may found that DLS can also be implemented using the queue data structure. In addition to each level of the node needs to be computed to check the finiteness and reach of the goal node from the source node.

Depth-limited search is found to terminate under these two clauses:

  1. When the goal node is found to exist.
  2. When there is no solution within the given depth limit domain.

Example of DLS Process

If we fix the depth limit to 2, DLS can be carried out similarly to the DFS until the goal node is found to exist in the tree’s search domain.

Depth Limited Search

Algorithm of the example

  1. We start with finding and fixing a start node.
  2. Then we search along with the depth using the DFS algorithm.
  3. Then we keep checking if the current node is the goal node or not.

If the answer is no: then we do nothing.

If the answer is yes: then we return.

  1. Now we will check whether the current node is lying under the depth limit specified earlier or not.

If the answer is not: then we do nothing.

If the answer is yes, we will explore the node further and save all of its successors into a stack.

  1. Now we call the function of DLS iteratively or recursively for all the nodes of the stack and go back to step 2.

Thus we have successfully explored all the nodes in the given depth limit and found the goal node if it exists within a specified depth limit.

C program

Code:

#include <stdio.h>
#include <stdlib.h>
/*ADJACENCY MATRIX*/
int source,X,Y,time,visited[20],Z[20][20];
void DFS(int p)
{
int q;
visited[p]=1;
printf(" %d->",p+1);
for(q=0;q<X;q++)
{
if(Z[p][q]==1&&visited[q]==0)
DFS(q);
}
}
int main()
{
int p,q,x1,x2;
printf("\t\t\tGraphs\n");
printf("Enter the required number of edges:");
scanf("%d",&Y);
printf("Enter the required number of vertices:");
scanf("%d",&X);
for(p=0;p<X;p++)
{
for(q=0;q<X;q++)
Z[p][q]=0;
}
/*creating edges : */
for(p=0;p<Y;p++)
{
printf("Enter the format of the edges (format: x1 x2) : ");
scanf("%d%d",&x1,&x2);
Z[x1-1][x2-1]=1;
}
for(p=0;p<X;p++)
{
for(q=0;q<X;q++)
printf(" %d ",Z[p][q]);
printf("\n");
}
printf("Enter the source of the DFS: ");
scanf("%d",&source);
DFS(source-1);
return 0;
}

Output:

Depth Limited Search output

Advantages and Disadvantages of Depth Limited Search

Below are the advantages and disadvantages are below:

Advantages of Depth Limited Search

  • Depth limited search is better than DFS and requires less time and memory space.
  • DFS assures that the solution will be found if it exists infinite time.
  • There are applications of DLS in graph theory particularly similar to the DFS.
  • To combat the disadvantages of DFS, we add a limit to the depth, and our search strategy performs recursively down the search tree.

Disadvantages of Depth Limited Search

  • The depth limit is compulsory for this algorithm to execute.
  • The goal node may not exist in the depth limit set earlier, which will push the user to iterate further adding execution time.
  • The goal node will not be found if it does not exist in the desired limit.

Performance Measures

  • Completeness: The DLS is a complete algorithm in general except the case when the goal node is the shallowest node, and it is beyond the depth limit, i.e. l < d, and in this case, we never reach the goal node.
  • Optimality: The DLS is a non-optimal algorithm since the depth that is chosen can be greater than d (l>d). Thus DLS is not optimal if l > d
  • Time complexity is expressed as: It is similar to the DFS, i.e. O(bl), where 1 is the set depth limit.
  • Space Complexity is expressed as: It is similar to DFSe. O(bl), where 1 is specified depth limit.

Conclusion – Depth Limited Search

DLS algorithm is used when we know the search domain, and there exists a prior knowledge of the problem and its domain while this is not the case for uninformed search strategy. Typically, we have little idea of the goal node’s depth unless one has tried to solve it before and has found the solution.

Recommended Articles

This is a guide to Depth Limited Search. Here we discuss Depth Limited Search Process’s example and the algorithms, advantages, and disadvantages. You may also have a look at the following articles to learn more –

  1. DFS Algorithm
  2. HDFS Architecture
  3. HDFS Commands
  4. Search Algorithms in AI

Primary Sidebar

Footer

Follow us!
  • EDUCBA FacebookEDUCBA TwitterEDUCBA LinkedINEDUCBA Instagram
  • EDUCBA YoutubeEDUCBA CourseraEDUCBA Udemy
APPS
EDUCBA Android AppEDUCBA iOS App
Blog
  • Blog
  • Free Tutorials
  • About us
  • Contact us
  • Log in
Courses
  • Enterprise Solutions
  • Free Courses
  • Explore Programs
  • All Courses
  • All in One Bundles
  • Sign up
Email
  • [email protected]

ISO 10004:2018 & ISO 9001:2015 Certified

© 2025 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
Loading . . .
Quiz
Question:

Answer:

Quiz Result
Total QuestionsCorrect AnswersWrong AnswersPercentage

Explore 1000+ varieties of Mock tests View more

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA
Free Data Science Course

Hadoop, Data Science, Statistics & others

By continuing above step, you agree to our Terms of Use and Privacy Policy.
*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you

EDUCBA Login

Forgot Password?

🚀 Limited Time Offer! - 🎁 ENROLL NOW