Iterative depth first search

from Wikipedia, the free encyclopedia

The iterative deepening search ( English iterative deepening depth-first search , IDDFS ) is a procedure of the computer science for searching for a node in a graph . The algorithm combines the desirable properties of depth-first search (low memory consumption) and breadth-first search (optimality).

General

Like normal depth-first search, iterative depth-first search is an uninformed search . It works like depth-first search , but by limiting the search depth , it avoids the disadvantages of completeness. In the iterative depth-first search, a limited depth-first search is carried out iteratively , and the level up to which the limited depth-first search explores the graph is increased by one with each iteration . In the first step, all nodes to which a path of length 0 leads are explored using depth-first search. In the next step, all nodes to which a path of length 1 leads are explored using depth-first search and so on. This means that iterative depth-first search is in principle complete on all graphs, since the search can no longer get lost in an endlessly long path. The iterative depth-first search is a combination of depth-first search and breadth-first search . On the one hand, it has the same storage space consumption as normal depth-first search (a maximum of one complete branch up to the current iteration depth must be stored in the main memory), but also delivers with monotonically increasing path costs like breadth first search, an optimal solution. Since the search tree that has already been run through has to be completely rebuilt for each new iteration, the runtime is longer than with normal depth search. However, since most of the nodes in a search tree are leaves, this little additional effort compared to the advantages is acceptable.

Algorithm (informal)

  1. Determine the node where you want the search to begin
  2. Go to Limited Depth First Search with the current search depth
  3. Increase the search depth by 1 and go to step 2

Algorithm (formal) 

Iterative Tiefensuche (Knoten, Ziel)
{
  IterationsTiefe := 0
  while (IterationsTiefe < unendlich)
  {
    Beschränkte_Tiefensuche (Knoten, Ziel, IterationsTiefe);
    IterationsTiefe := IterationsTiefe + 1;
  }
}

Algorithm example: creating the depth search forest (iterative)

The following iterative algorithm generates the depth-search forest of a graph G by setting discovery and finishing times and coloring the nodes. Based on Cormen , Leiserson , Rivest , Stein , Introduction to Algorithms, MIT Press, 2001, all nodes are initially colored white. Then, by definition, the depth-first search starts at the alphabetically smallest node and colors it gray. Then a stack is used, in which the path that has already been discovered is stored up to a node without white neighbors. All nodes in the stack are gray. The stack is removed until one of the stored nodes has another white neighbor or the stack is empty. This simulates the backtracking inherent to the recursion.

The ready-made method nextw (u) returns the (alphabetically smallest by definition) white neighbor for a node u. If none exists, it returns NULL or FALSE. 

 1 for each v of G {		//Initialisierung: 
 2   col[v] = w;			//Alle Knoten weiß färben und 
 3   pi[v] = null;			//Vorgänger auf null setzen
 4 }
 5 time=0;				
 6 S=0;				//Stack S initialisieren
 7  
 8 for each u of G {		//für alle weißen Knoten u
 9    if (col[u]==w) {		
10      time++;			//Zeitzähler erhöhen
11      col[u] = g;		//Aktuellen Knoten grau färben
12      d[u] = time;		//Entdeckzeit setzen
13      push(S, u);		//Aktuellen Knoten auf Stack
14      while (S!=0) {		//Solange Stack belegt ist
15        time++;			//Zeitzähler erhöhen
16        v = nextw(u);	
17        if (v!=null) {		//wenn nächster weißer Nachbar
18          col[v] = g;		//v grau färben
19          d[v] = time;		//Entdeckzeit setzen
20          pi[v] = u;		//Vorgänger setzen
21          if (nextw(v)!=null) 
22            push(S, v);
23          u=v;			//Aktueller Knoten ist v
24        } else {			//wenn v NULL
25          col[u] = s;		//Aktuellen Knoten schwarz färben
26          f[u] = time;		//Finishing-Time setzen
27          if (S!=0) 
28            u = pop(S);		//neuer aktueller Knoten von Stack
29          if (col[u]==g)
30            push(S,u);		//Solange Knoten noch nicht Schwarz, wieder auf den Stack
31        }
32      }
33    }
34  }

1 nextw(u) {
2   for each node of adj[u] {                                      
3     if col[node]==w 
4       return node;
5     else                          
6       return null;
7   }
8 }

properties

Storage space consumption

Since depth-first search is used internally, the storage space requirement is similar to that of normal depth-first search.

running time

Because in the worst case, all possible paths need to be considered to any node, the duration of Iterative deepening search , with the number of nodes and the number of edges is in the graph.

completeness

Since iterative depth-first search cannot get lost in infinitely long paths or in cycles , the algorithm is complete.

Optimality

Iterative depth-first search is optimal if all path costs are equivalent, since depth-first search finds the shortest path to a goal in this case. However, if the path costs are not equivalent, it can happen, as with breadth-first search, that a suboptimal path is chosen.

literature