In computer science

Computer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

 depth-limited search is an algorithm

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

 to explore the vertices

Vertex (graph theory)

In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...

 of a graph

Graph (mathematics)

In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...

. It is a modification of depth-first search

Depth-first search

Depth-first search is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root and explores as far as possible along each branch before backtracking....

 and is used for example in the iterative deepening depth-first search

Iterative deepening depth-first search

Iterative deepening depth-first search is a state space search strategy in which a depth-limited search is run repeatedly, increasing the depth limit with each iteration until it reaches d, the depth of the shallowest goal state...

 algorithm.

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 imposing a maximum limit on the depth of the search. Even if the search could still expand a vertex beyond that depth, it will not do so and thereby it will not follow infinitely deep paths

Path (graph theory)

In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. A path may be infinite, but a finite path always has a first vertex, called its start vertex, and a last vertex, called its end vertex. Both of them...

 or get stuck in cycles

Path (graph theory)

In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. A path may be infinite, but a finite path always has a first vertex, called its start vertex, and a last vertex, called its end vertex. Both of them...

. Therefore depth-limited search will find a solution if it is within the depth limit, which guarantees at least completeness on all graphs.

Algorithm (informal)

1. Determine the vertex where the search should start and assign the maximum search depth
2. Check if the current vertex is the goal state
   • If not: Do nothing
   • If yes: return
3. 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
        Stack (data structure)
        In computer science, a stack is a last in, first out abstract data type and linear data structure. A stack can have any abstract data type as an element, but is characterized by only three fundamental operations: push, pop and stack top. The push operation adds a new item to the top of the stack,...
        
        
     2. Call DLS recursively for all vertices of the stack and go back to Step 2

Pseudocode

DLS(node, goal, depth) {
if ( depth >= 0 ) {
if ( node goal )
return node

for each child in expand(node)
DLS(child, goal, depth-1)
}
}

Space complexity

Since depth-limited search internally uses depth-first search

Depth-first search

Depth-first search is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root and explores as far as possible along each branch before backtracking....

, the space complexity

Computational complexity theory

Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...

 is equivalent to that of normal depth-first search.

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 O() where stands for the number of vertices and for the number of edges in the explored graph

Graph (mathematics)

In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...

. Note that depth-limited search does not explore the entire graph, but just the part that lies within the specified bound.

Completeness

Even though depth-limited search cannot follow infinitely long paths, nor can it get stuck in cycles, in general the algorithm is not complete since it does not find any solution that lies beyond the given search depth. But if the maximum search depth is chosen to be greater than the depth of a solution the algorithm becomes complete.

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, thereby possibly finding a solution that is more expensive than some solution in another path.