SUBJECT MATERIAL, EBOOKS, IMPORTANT QUESTION , ASSIGNMENT QUESTION, OLD QUESTION PAPER

Monday 25 July 2022

Depth-Limited Search in Artificial Intelligence

What is DLS Algorithm (Depth-Limited Search)? DLS is an uninformed search algorithm.  This is similar to DFS but differs only in a few ways... thumbnail 1 summary

What is DLS Algorithm (Depth-Limited Search)?

  • DLS is an uninformed search algorithm. 
  • This is similar to DFS but differs only in a few ways. 
  • The sad failure of DFS is alleviated by supplying a depth-first search with a predetermined depth limit. 
  • It can be considered equivalent to DFS with a predetermined depth limit 'l'. Nodes at depth l are considered to be nodes without any successors.
  • Depth limited search may be thought of as a solution to DFS's infinite path problem; in the Depth limited search algorithm.
  • DFS is run for a finite depth 'l', where 'l' is the depth limit.  
  • Here, nodes at depth are treated as if they have no successors. 

Depth-limited search can be halted in two cases:

  • Standard Failure Value(SFV): The SFV tells that there is no solution to the problem.
  • Cutoff Failure Value(CFV): The Cutoff Failure Value tells that there is no solution within the given depth-limit.

The architecture of Depth-Limited Search algorithm

Uninformed Search Algorithms

  • A Depth First Search starts at the root node and follows each branch to its deepest node. 
  • The problem with DFS is that this could lead to an infinite loop. 
  • By incorporating a specified limit termed as the depth limit, the Depth Limited Search Algorithm eliminates the issue of the DFS algorithm's infinite path problem.
  • In a graph, the depth limit is the point beyond which no nodes are explored.

Algorithm of Depth-Limited Search:

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

  • The start node or node 1 is added to the beginning of the stack.
  • 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.
  • Next, we mark it as visited and check if node 2 is the goal node or not.
  • If node 2 is not found to be the goal node, then we push node 4 on top of the stack.
  • Now we search in the same depth limit and move along depth-wise to check for the goal nodes.
  • 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.
  • Then we push them into the stack and mark them visited.
  • 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.

Advantages of Depth-Limited Search:

  • Depth-limited search is Memory efficient.
  • 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. 
  • Depth-limited search also has a disadvantage of incompleteness.
  • It may not be optimal if the problem has more than one solution.

Performance Measures

  • Completeness: The DLS is a complete algorithm in general except the case when the goal node is the shallowest (Very few) 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.