Depth-limited search

Limited depth-first search (English depth -limited search, DLS) is in the computer science a method for searching a node in a graph. The algorithm is a variation of depth first search. Common applications for the Limited depth-first search algorithm in the iterative deepening search.

General

The limited depth-first search is as already the normal depth-first search an uninformed search. It works just like the depth-first search, but avoids by limiting the search depth their disadvantages relative to completeness. Here, a predetermined depth is defined from which cancels the depth-first search, and thus terminated in any case. By limiting the depth of the limited depth-first search can lose neither infinitely deep paths even in cycles. Thus, depth-first search - if a solution within the depth itself is given - completely, so find the solution to any event, regardless of the structure of the graph.

Algorithm (informal)

  • If no: Do nothing
  • If so: Expanding the node and save all successors in a stack
  • Call recursively for each of the nodes in the stack DLS, 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

Memory consumption

Since everything is done internally on depth-first search, the memory space required equivalent to the normal depth-first search.

Term

Since everything is done internally on depth-first search, the term equivalent is of normal depth-first search, and is thus where is the number of nodes and the number of edges in the graph to the explored. It should be noted that not all nodes and edges of the entire graph to be considered, because only those nodes are expanded, which lie within the depth of self- prescribed.

Completeness

Although Limited depth-first search can lose neither infinite nor long paths in cycles, the algorithm is generally not complete. If one chooses the maximum search depth is too low, the algorithm does not find a solution possibly further afield. However, If you choose the maximum search depth deeper than the depth at which the solution is, the algorithm is complete.

Optimality

Limited depth-first search is not optimal, because it still follows a path as long as possible in the depth, so they can find a target on this path, which is much more expensive than an alternative destination on a different path.

120649
de