Iterative Tiefensuche - LinkFang.de





Iterative Tiefensuche


Die iterative Tiefensuche (englisch iterative deepening depth-first search, IDDFS) ist ein Verfahren aus der Informatik zum Suchen eines Knotens in einem Graphen. Der Algorithmus kombiniert die wünschenswerten Eigenschaften von Tiefensuche (geringer Speicherverbrauch) und Breitensuche (Optimalität).

Allgemeines

Die iterative Tiefensuche ist wie die normale Tiefensuche eine uninformierte Suche. Sie funktioniert wie die Tiefensuche, vermeidet jedoch durch Begrenzung der Suchtiefe deren Nachteile bezüglich Vollständigkeit. Bei der iterativen Tiefensuche wird iterativ eine beschränkte Tiefensuche durchgeführt, und dabei das Level, bis zu welchem die Beschränkte Tiefensuche den Graphen erkundet, bei jeder Iteration um eins erhöht. Im ersten Schritt werden also alle Knoten, zu denen ein Pfad der Länge 0 führt, mittels Tiefensuche erkundet. Im nächsten Schritt werden dann alle Knoten, zu denen ein Pfad der Länge 1 führt, mittels Tiefensuche erkundet und so weiter. Hierdurch wird erreicht, dass Iterative Tiefensuche prinzipiell auf allen Graphen vollständig ist, da die Suche sich nun nicht mehr in einem endlos langen Pfad verlieren kann. Damit stellt die iterative Tiefensuche eine Kombination der Tiefen- und der Breitensuche dar. Sie hat einerseits den gleichen Speicherplatzverbrauch wie die normale Tiefensuche (im Arbeitsspeicher muss jeweils maximal ein kompletter Ast bis zur momentanen Iterationstiefe gespeichert werden), liefert aber bei monoton steigenden Pfadkosten, ebenso wie die Breitensuche, eine optimale Lösung. Da für jede neue Iteration auch der bereits durchlaufene Suchbaum komplett neu aufgebaut werden muss, ist die Laufzeit höher als bei normaler Tiefensuche. Da in einem Suchbaum aber jeweils der größte Teil der Knoten Blätter sind, ist dieser geringe Mehraufwand gegenüber den Vorteilen hinnehmbar.

Algorithmus (informell)

  1. Bestimme den Knoten, an dem die Suche beginnen soll
  2. Rufe Beschränkte Tiefensuche mit der aktuellen Suchtiefe auf
  3. Erhöhe die Suchtiefe um 1 und gehe zu Schritt 2

Algorithmus (formal)

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

Algorithmusbeispiel: Erzeugen des Tiefensuchwaldes (iterativ)

Der folgende iterative Algorithmus erzeugt den Tiefensuchwald eines Graphen G mittels Setzen von Discovery- und Finishing-Times und Färben der Knoten. In Anlehnung an Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, MIT Press, 2001, werden zunächst alle Knoten weiß gefärbt. Anschließend startet die Tiefensuche per Definition beim alphabetisch kleinsten Knoten und färbt diesen grau. Danach wird ein Stack verwendet, worin der bereits entdeckte Weg bis zu einem Knoten ohne weißen Nachbarn gespeichert wird. Alle Knoten im Stack sind grau. Der Stack wird abgetragen, bis einer der gespeicherten Knoten noch einen weiteren weißen Nachbarn hat oder der Stack leer ist. Damit wird das der Rekursion eigene Backtracking simuliert.

Die vorgefertigte Methode nextw(u) liefert für einen Knoten u den (per Definition alphabetisch kleinsten) weißen Nachbarn. Existiert kein solcher, liefert sie NULL bzw. 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. }

Eigenschaften

Speicherplatzverbrauch

Da intern auf Tiefensuche zurückgegriffen wird, ist der Speicherplatzbedarf ähnlich dem der normalen Tiefensuche.

Laufzeit

Da im schlimmsten Fall alle möglichen Pfade zu allen möglichen Knoten betrachtet werden müssen, beträgt die Laufzeit von Iterativer Tiefensuche [math]\mathcal{O}( \vert V \vert + \vert E \vert )[/math], wobei [math] \vert V \vert [/math] für die Anzahl der Knoten und [math] \vert E \vert [/math] für die Anzahl der Kanten im Graph steht.

Vollständigkeit

Da sich Iterative Tiefensuche weder in unendlich langen Pfaden noch in Zyklen verlieren kann, ist der Algorithmus vollständig.

Optimalität

Iterative Tiefensuche ist optimal, falls alle Pfadkosten äquivalent sind, da Tiefensuche in diesem Fall den kürzesten Pfad zu einem Ziel findet. Sind die Pfadkosten jedoch nicht äquivalent, so kann es wie bei der Breitensuche dazu kommen, dass ein suboptimaler Pfad gewählt wird.

Literatur


Kategorien: Graphsuchalgorithmus

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Iterative Tiefensuche (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.