Iterative deepening depth-first search

The iterative deepening search (english iterative deepening depth-first search, IDDFS ) is a term used in computer science. It is a method for searching for a node in a graph. The algorithm combines the desirable properties of depth-first search ( low memory usage ) and breadth-first search (optimality ).

General

The iterative deepening search is like the normal depth-first search an uninformed search. It functions like depth-first search, but avoids by limiting the search depth their disadvantages relative to completeness. In iterative deepening search a limited depth-first search is performed iteratively, and thereby the level up to which the Limited depth-first search explores the graph increases by one at each iteration. In the first step, ie all nodes to which there is a path of length 0, explored using depth-first search. In the next step, then all nodes to which there is a path of length 1, explored by depth-first search and so on. This ensures that iterative deepening search on all graphs is in principle fully, since the search now can not lose more in a seemingly endless path. Thus, the iterative deepening search a combination of depth-and breadth-first search; they do one hand has the same memory consumption as the normal depth-first search (must be in memory a maximum of a complete branch are saved to the current iteration ), but provides at monotonically increasing path cost, as well such as breadth-first search, an optimal solution. Since for each new iteration path already traversed search tree needs to be completely rebuilt, and the runtime is higher than at normal depth-first search. Since in a search tree are each but most of the node leaves this small extra effort against the advantages acceptable.

Algorithm ( informal)

Algorithm (formal)

Iterative depth-first search (node ​​, target ) {    Iteration: = 0    while ( iteration < infinity)    {      Beschränkte_Tiefensuche (node ​​, target, iteration );      Iteration: = iteration 1;    } } Algorithm Example: generating the depth-first search forest ( iterative)

The following iterative algorithm generates the depth-first search forest of a graph G by setting Discovery and finishing Times and coloring the nodes. Inspired by Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, MIT Press, 2001, all nodes are initially colored white. Then the depth-first search starts by definition at the alphabetically smallest node and colors these gray. Thereafter, a stack is used in which the path is already found to be stored at a node without white neighbor. All nodes in the stack are gray. The stack is removed until one of the stored node still has another white neighbors or the stack is empty. Thus, the recursion will own backtracking simulated.

The prefabricated method nextw (u ) provides for a node u ( by definition alphabetically smallest ) white neighbors. If there is no such, it returns NULL or FALSE.

For each v of G {/ / Initialization:    col [v ] = w; Color / / All the nodes white and    pi [v ] = null; / / Set the predecessor to zero } time = 0; S = 0; / / Initialize the stack S   for each u of G {/ / for all white node u     if ( col [u ] == w ) {       time ; / Increase / time counter       col [u ] = g; Color / / current node gray       d [ u] = time; / / Set Entdeckzeit       push ( S, u); / / Current node on stack       while ( S! = 0) { / / As long as stack is occupied         time ; / Increase / time counter         v = nextw (u );         if ( v! = null ) { / / if next white neighbor           col [v ] = g; / / v gray color           d [ v] = time; / / Set Entdeckzeit           pi [v ] = u; / / Set previous           if ( nextw (v )! = null)             push ( S, v);           u = v; / / Current node is v         Else { } / / if v is NULL           col [u ] = s; Color / / current node black           f [ u] = time; / / Set the finishing time           if ( S! = 0)             u = pop ( S); / / new current node from stack           if ( col [u ] == g)             push ( S, u); / / As long as nodes are not black, back on the stack         }       }     }   } nextw (u ) {    for each node of adj [u ] {      if col [node ] == w        return node;      else        return null;    } } properties

Memory consumption

Since everything is done internally on depth-first search, the memory requirement is similar to the normal depth-first search.

Term

Since in the worst case, all possible paths must be considered at all possible nodes, the running time of Iterative depth-first search, where is the number of nodes and the number of edges in the graph.

Completeness

Since Iterative depth-first search can lose neither infinitely long paths even in cycles, the algorithm is complete.

Optimality

Iterative depth-first search is optimal if all path costs are equivalent, since depth-first search is in this case the shortest path to a destination. However, if the path cost is not equivalent, it may happen that a sub-optimal path is chosen as in the breadth-first search.