 Depthlimited search

Depthlimited search Class Search Algorithm Data structure Graph Worst case performance O(  V  +  E  ) Graph and tree
search algorithmsAlphabeta pruning
A*
B*
Beam
Bellman–Ford algorithm
Bestfirst
Bidirectional
Breadthfirst
D*
Depthfirst
Depthlimited
Dijkstra's algorithm
Floyd–Warshall algorithm
Hill climbing
Iterative deepening depthfirst Johnson's algorithm
Lexicographic breadthfirst
Uniformcost
moreRelated topics Dynamic programming
Search gamesIn computer science depthlimited search is an algorithm to explore the vertices of a graph. It is a modification of depthfirst search and is used for example in the iterative deepening depthfirst search algorithm.
Contents
General
Like the normal depthfirst search, depthlimited search is an uninformed search. It works exactly like depthfirst 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 or get stuck in cycles. Therefore depthlimited search will find a solution if it is within the depth limit, which guarantees at least completeness on all graphs.
Algorithm (informal)
 Determine the vertex where the search should start and assign the maximum search depth
 Check if the current vertex is the goal state
 If not: Do nothing
 If yes: return
 Check if the current vertex is within the maximum search depth
 If not: Do nothing
 If yes:
 Expand the vertex and save all of its successors in a stack
 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, depth1) } }
Properties
Space complexity
Since depthlimited search internally uses depthfirst search, the space complexity is equivalent to that of normal depthfirst search.
Time complexity
Since depthlimited search internally uses depthfirstsearch, the time complexity is equivalent to that of normal depthfirst search, and is O() where stands for the number of vertices and for the number of edges in the explored graph. Note that depthlimited search does not explore the entire graph, but just the part that lies within the specified bound.
Completeness
Even though depthlimited 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
Depthlimited search is not optimal. It still has the problem of depthfirst 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.
Literature
 Russell, Stuart J.; Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2nd ed.), Upper Saddle River, New Jersey: Prentice Hall, ISBN 0137903952, http://aima.cs.berkeley.edu/
Categories: Graph algorithms
 Search algorithms
Wikimedia Foundation. 2010.