Depth Limited Search Implementation Using Python Programming

Post Views: 2,100

In this tutorial, we will be learning about Depth Limited Search and also will learn how to implement the same using Python programming language. DLS is an extension of Depth-first-search and if you are unaware of what it is, have a look at the tutorial below.

Also Read: How to implement Depth First Search algorithm in Python

Introduction to Depth Limited Search

To make things simple, let’s take the example of mazes shown below. The first maze still seems comparatively solvable in limited steps. But what if we wish to solve the second maze, then when a person manually wishes to go across the maze, the person might get stuck in an infinite loop of paths. Hence, to avoid getting stuck inside the maze, we will set a limit to how deep we wish to go to reach the goal.

That’s the simple concept of depth-limited Search which implies only exploring a certain number of steps away from your starting point before making a decision. In simple terms, we will be following the mentioned approach to solve the problem:

We begin at the entrance of the maze. Instead of choosing a random path, we will pick the path which is right in front of us.
Now, let’s assume that the depth limit is set to THREE. This means that we will only go three steps deep into the maze from this point.
You keep on going further, the moment we reach the THIRD step, we stop and evaluate.
At this point, if we have reached the end, then we terminate. Otherwise, take a different path BUT not beyond the three steps.

This simply explains how the DLS Approach functions.

Code Implementation for the Graph Creation

For the code implementation, let’s first of all create a tree graph on which we will be applying DLS later. We will make use of the graphviz and networkx library as shown in the code snippet below. If you are confused about this implementation, then have a look at the detailed tutorial below:

Also Read: Directed Tree Visualization using Python Programming Language

import networkx as nx
from graphviz import Digraph
from IPython.display import Image

graph = {'A': ['B', 'C'],'B': ['D', 'E', 'F'],'C': ['G', 'H'],'D': ['I', 'J'],
    'E': ['K', 'L'],'F': ['M'],'G': ['N', 'O'],'H': ['P', 'Q'],'I': ['R'],
    'J': ['S', 'T'],'K': ['U'],'L': ['V', 'W'],'M': ['X'],'N': [],'O': [],
    'P': [],'Q': [],'R': [],'S': [],'T': [],'U': [],'V': [],'W': [],'X': [],}

G = nx.DiGraph(graph)
GViz = Digraph(comment='The DLS_Graph')

for n in G.nodes():
    GViz.node(n)
for e in G.edges():
    GViz.edge(e[0], e[1])

GViz.render('DLS_Graph', format='png', cleanup=True)
Image(filename='DLS_Graph.png')

The resulting plot looks like this:

Python Code Implementation for the Depth Limit Search Algorithm

Let’s keep the assumption that the Start node is ‘A’ and the goal state is ‘G’, also the depth limit is set as TWO. The image below shows how the system will travel through the graph using the Depth Limit Search approach.

Before moving on to implementation, I would like you to understand and keep note of the following points:

As we can see, there are two subtrees we can explore to go from the start node to the goal node. When DLS is implemented, the code results in the most optimum path (shortest path) which in our case is Approach 2 (A-> C -> G).
During code implementation, we will assume that the depth of the root node is 1 instead of 0, which will as a result increase the depth limit from 2 to 3.

Let’s now implement the same using the Python program in the upcoming sections. Have a look at the code mentioned below, to make it simpler we will break it down into small bits to make the explanation better.

def depth_limited_search(graph, start, goal, limit):
    explored = set()

    def recursive_dls(node, depth):
        if depth < 0:
            return None
        if node == goal:
            return [node]
        explored.add(node)

        for neighbor in graph[node]:
            if neighbor not in explored:
                path = recursive_dls(neighbor, depth - 1)
                if path is not None:
                    return [node] + path
        return None

    return recursive_dls(start, limit - 1)

Code Explanation

Have a look at the detailed steps to explain the points mentioned below:

We will have a set of explored nodes (initially set to empty). Why Set? Because we don’t wish to have the nodes being explored more than once which might lead to an infinite loop.
We will then recursively call a HELPER function (recursive_dls) which will explore nodes at a certain depth one after another.
Inside the helper function, we will make a few checks:
- If depth becomes negative (Not Possible), that must return None.
- If the node being explored is the goal node, we return the path explored until now in the form of a list.
- In any other situation, we will keep adding the nodes in the explored set.
After the basic checks, we will move on to the next depth, getting the neighboring nodes of the current node. As we have a direct dictionary declared, this is quite simple to capture.
We will check if the neighbor has not been explored yet, and we will recursively explore the node until reaching the depth limit to obtain the path.
If a particular subtree returns a path other than NONE (indicating the goal is found), we will return the final path from the start to the goal node.
If, after exploring all nodes, the goal node is still not found, we will return NONE as the path.

Sample Outputs

The output of the code when executed (code snippet shown below) for the start node as A and end node as G is as follows: [[‘A’, ‘C’, ‘G’]]

print(depth_limited_search(graph, 'A', 'G', 3))

In this case (code snippet below), we put the start node as A but the end node is set as K (which is outside the depth limit of 3), we will get the output as : []

print(depth_limited_search(graph, 'A', 'K', 3))

Hope you were able to learn something new through the tutorial! If you liked this, then have a read at the following tutorials as well.