Depth-limited search

From Free net encyclopedia

Depth-limited search
General Data
Class:	Search algorithm
Data_structure:	Graph (data structure)
Time Complexity:	V\|+\|E\|)</math>
Space Complexity:
Optimal:	no
Complete:	no

In Computer Science Depth-limited search is an algorithm to explore the Vertices of a Graph. It is a modification of Depth-first search and is used for example in the Iterative deepening depth-first search algorithm.

1 General
2 Algorithm (informal)
3 Algorithm (formal)
4 Properties
5 Literature

[edit]

General

Like the normal Depth-first search, Depth-limited search is an uninformed search. It works exactly like Depth-first search, but avoids its drawbacks regarding Completeness by limiting the maximum depth of the search. This is achieved by giving a limit how "deep" the algorithm may go. Even if it could still expand a vertex beyond that depth, it will not do so and thereby it will not follow infinite deep paths or get stuck in cycles. Therefore Depth-limited search will find a solution if it is within the self-opposed depth limit, which guarantees at least completeness on all Graphs.

[edit]

Algorithm (informal)

Determine the vertex where the search should start and assign the maximum search depth
Check if the current vertex is within the maximum search depth
- If not: Do nothing
- If yes:
  1. Expand the vertex and save all of its successors in a Stack
  2. Call DLS recusevely for all vertices of the Stack and go back to Step 2

[edit]

Algorithm (formal)

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

[edit]

Properties

[edit]

Space complexity

Since Depth-limited search internally uses Depth-first search the Space complexity is equivalent to that of normal Depth-first search.

[edit]

Time complexity

Since Depth-limited search internally uses Depth-first-search the Time complexity is equivalent to that of normal Depth-first search, and is therefore O(<math> \vert V \vert + \vert E \vert </math>) where <math> \vert V \vert </math> stands for the number of vertices and <math> \vert E \vert </math> for the number of edges in the explored Graph. One should mention that Depth-limited search does not explore the whole given Graph, but just the part that lays within the given bounds.

[edit]

Completeness

Even though Depth-limited search cannot follow infinitely long paths, or can it get stuck in Cycles, in general the Algorithm is not optimal since it does not find any solution that lays beyond the given search depth. But if you choose the maximum search depth to be greater than the depth of a solution the algorithm gets complete.

[edit]

Optimality

Depth-limited search is not optimal. It still has the problem of depth-first search that it first explores one path to its end and thereby perhaps finding a solution that is more expensive than some solution in another path.

[edit]