EDUCBA

EDUCBA

MENUMENU
  • Free Tutorials
  • Free Courses
  • Certification Courses
  • 360+ Courses All in One Bundle
  • Login

Depth Limited Search

By Priya PedamkarPriya Pedamkar

Home » Data Science » Data Science Tutorials » Data Structures Tutorial » Depth Limited Search

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.

Start Your Free Data Science Course

Hadoop, Data Science, Statistics & others

  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.

Popular Course in this category
All in One Data Science Bundle (360+ Courses, 50+ projects)360+ Online Courses | 1500+ Hours | Verifiable Certificates | Lifetime Access
4.7 (3,220 ratings)
Course Price

View Course

Related Courses
Oracle DBA Database Management System Training (2 Courses)SQL Training Program (7 Courses, 8+ Projects)
  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

All in One Data Science Bundle (360+ Courses, 50+ projects)

360+ Online Courses

50+ projects

1500+ Hours

Verifiable Certificates

Lifetime Access

Learn More

0 Shares
Share
Tweet
Share
Primary Sidebar
Data Structures Tutorial
  • Basics
    • What is Data Structure
    • Heap Data Structure
    • Types of Trees in Data Structure
    • AVL Tree in Data Structure
    • B Tree in Data Structure
    • B+ Tree in Data Structure
    • DFS Algorithm
    • BFS Algorithm
    • Arrays in Data Structure
    • Graph in Data Structure
    • Graph Representation
    • Breadth First Search
    • Depth Limited Search
    • Searching in Data Structure
    • Linear Search in Data Structure
    • Linked List in Data Structure
    • Doubly linked list in Data Structure
    • Circular Linked List in Data Structure
    • Pointers in Data Structure
    • Types of Graph in Data Structure
    • Bubble Sort in Data Structure
    • Quick Sort in Data Structure
    • Merge Sort in Data Structure
    • Selection Sort in Data Structure
    • Insertion Sort in Data Structure
    • Stack in Data Structure
    • Queue in Data Structure
    • Asymptotic Analysis
    • Kruskal’s Algorithm
    • Prim’s Algorithm
    • BFS VS DFS
    • BCNF
    • Data Structure Interview Questions
    • Data Structures & Algorithms Interview

Related Courses

All in One Data Science Course

Oracle DBA Course

SQL Certification Course

Footer
About Us
  • Blog
  • Who is EDUCBA?
  • Sign Up
  • Corporate Training
  • Certificate from Top Institutions
  • Contact Us
  • Verifiable Certificate
  • Reviews
  • Terms and Conditions
  • Privacy Policy
  •  
Apps
  • iPhone & iPad
  • Android
Resources
  • Free Courses
  • Database Management
  • Machine Learning
  • All Tutorials
Certification Courses
  • All Courses
  • Data Science Course - All in One Bundle
  • Machine Learning Course
  • Hadoop Certification Training
  • Cloud Computing Training Course
  • R Programming Course
  • AWS Training Course
  • SAS Training Course

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

EDUCBA Login

Forgot Password?

EDUCBA
Free Data Science Course

Hadoop, Data Science, Statistics & others

*Please provide your correct email id. Login details for this Free course will be emailed to you
Book Your One Instructor : One Learner Free Class

Let’s Get Started

This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy

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

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

Special Offer - All in One Data Science Course Learn More