Depth-limited search

Depth-limited search
Depth-limited search
Class Search Algorithm
Data structure Graph
Worst case performance O( | V | + | E | )

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.



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 or get stuck in cycles. 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
      2. Call DLS recursively for all vertices of the stack and go back to Step 2


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, the space complexity 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( \vert V \vert + \vert E \vert ) where  \vert V \vert stands for the number of vertices and  \vert E \vert for the number of edges in the explored graph. Note that depth-limited search does not explore the entire graph, but just the part that lies within the specified bound.


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.


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.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Depth-first search — Order in which the nodes are visited Class Search algorithm Data structure Graph Worst case performance …   Wikipedia

  • Iterative deepening depth-first search — Graph and tree search algorithms Alpha beta pruning A* B* Beam Bellman–Ford algorithm Best first Bidirectional …   Wikipedia

  • Search algorithm — In computer science, a search algorithm, broadly speaking, is an algorithm that takes a problem as input and returns a solution to the problem, usually after evaluating a number of possible solutions. Most of the algorithms studied by computer… …   Wikipedia

  • Search for HMAS Sydney and German auxiliary cruiser Kormoran — A search for the wrecks of the Australian warship HMAS Sydney and the German merchant raider Kormoran , that sank each other during World War II, ended successfully in March 2008. On 19 November 1941, the two ships fought a battle in the Indian… …   Wikipedia

  • Search Engine (radio show) — Infobox Podcast title = Search Engine caption = Search Engine s Current Logo host = Jesse Brown url = rss = format = Podcast, Radio genre = Technology Search Engine …   Wikipedia

  • Mobile search — is an evolving branch of information retrieval services that is centered around the convergence of mobile platforms and mobile phones and other mobile devices. Web search engine ability in a mobile form allows users to find mobile content on… …   Wikipedia

  • List of graph theory topics — This is a list of graph theory topics, by Wikipedia page. See glossary of graph theory for basic terminology Contents 1 Examples and types of graphs 2 Graph coloring 3 Paths and cycles 4 …   Wikipedia

  • List of mathematics articles (D) — NOTOC D D distribution D module D D Agostino s K squared test D Alembert Euler condition D Alembert operator D Alembert s formula D Alembert s paradox D Alembert s principle Dagger category Dagger compact category Dagger symmetric monoidal… …   Wikipedia

  • Beschränkte Tiefensuche — (engl. Depth Limited search, DLS) ist in der Informatik ein Verfahren zum Suchen eines Knotens in einem Graphen. Der Algorithmus ist eine Abwandlung der Tiefensuche. Anwendung findet die Beschränkte Tiefensuche im Algorithmus der Iterativen… …   Deutsch Wikipedia

  • DLS — or D.L.S. may refer to: Contents 1 Education 2 Law 3 Politics 4 …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”