Limited depth-first search

from Wikipedia, the free encyclopedia

Depth-limited search ( English depth-limited search , DLS ), is in the computer science , a method for searching for a node in a graph . The algorithm is a modification of depth-first search . The limited depth-first search is used in the algorithm of iterative depth-first search .

General

The limited depth-first search, like the normal depth-first search, is an uninformed search . It works exactly like depth-first search, but by limiting the search depth, it avoids its disadvantages in terms of completeness. Here, a certain depth is specified, from which the depth-first search is terminated, and thus in any case terminated. By limiting the depth, the limited depth-first search cannot get lost in infinitely deep paths or in cycles . Thus, depth-first search - if a solution lies within the self-specified depth - can be complete, i.e. find this solution in any case and regardless of the structure of the graph.

Algorithm (informal)

  1. Determine the node where the search should begin and determine the maximum search depth
  2. Check whether the current node is within the maximum search depth
    • If not: do nothing
    • If so:
      1. Expand the node and save all successors in a stack
      2. Call DLS recursively for each of the nodes in the stack and go to step 2

Algorithm (formal) 

DLS(node, goal, depth)
{
  if (node == goal)
    return node;
  stack := expand (node)
  while (stack is not empty)
  {
    node' := pop(stack);
    if (node'.depth() < depth)
      DLS(node', goal, depth);  
  }
}

properties

Storage space consumption

Since depth-first search is used internally , the storage space requirement is equivalent to that of normal depth-first search.

running time

Since depth-first search is used internally, the runtime is equivalent to that of normal depth-first search, and is thus where stands for the number of nodes and the number of edges in the explored graph. It should be noted here that not all nodes and edges of the entire graph are considered, since only those nodes are expanded which lie within the self-specified depth.

completeness

Although constrained depth-first search cannot get lost in infinitely long paths or in cycles, the algorithm is generally not complete. If the maximum search depth is chosen too low, the algorithm will not find a solution that may be further away. However, if you choose the maximum search depth deeper than the depth on which the solution is located, the algorithm is complete.

Optimality

Limited depth-first search is not optimal because it will still follow a path in depth for as long as possible, allowing it to find a destination on that path that is much more expensive than an alternative destination on another path.

See also

literature