Iterative Tiefensuche

Grundidee und Bedeutung

Die iterative Tiefensuche (englisch iterative deepening depth-first search, IDDFS) ist ein uninformiertes Suchverfahren zum Finden eines Knotens in einem Graphen. „Uninformiert“ bedeutet, dass die Suche kein zusätzliches Wissen darüber verwendet, wo das Ziel liegt. Das Verfahren verbindet den geringen Speicherbedarf der Tiefensuche mit der Vollständigkeit und unter bestimmten Bedingungen der Optimalität der Breitensuche.

Dazu führt der Algorithmus wiederholt eine beschränkte Tiefensuche durch. Diese funktioniert wie eine normale Tiefensuche, darf den Graphen aber nur bis zu einer festgelegten Tiefe erkunden. Die Grenze wird nach jedem Durchlauf um eins erhöht: Zuerst werden die über einen Pfad der Länge 0 erreichbaren Knoten untersucht, danach die über Pfade der Länge 1 erreichbaren Knoten und anschließend immer tiefere Ebenen. Dadurch kann sich die Suche nicht dauerhaft in einem unendlich langen Pfad verlieren.

Bei jeder neuen Iteration wird der bereits untersuchte Suchbaum erneut aufgebaut. Deshalb ist die Laufzeit höher als bei einer einzelnen normalen Tiefensuche. Da in einem Suchbaum meist der größte Teil der Knoten Blätter sind, wird dieser zusätzliche Aufwand im Artikel jedoch als gering und angesichts der Vorteile als hinnehmbar beschrieben.

Ablauf des Suchverfahrens

Der informelle Ablauf besteht aus drei wiederholten Schritten:

• Zunächst wird der Startknoten bestimmt. • Anschließend wird eine beschränkte Tiefensuche mit der aktuellen Suchtiefe ausgeführt. • Danach wird die Suchtiefe um 1 erhöht und die beschränkte Tiefensuche erneut gestartet.

Formal beginnt die Iterationstiefe bei 0. Solange sie kleiner als unendlich ist, wird die Funktion Beschränkte_Tiefensuche(Knoten, Ziel, IterationsTiefe) aufgerufen. Danach wird die Iterationstiefe um 1 erhöht. Die Suche endet praktisch, sobald das Ziel gefunden wurde; im angegebenen formalen Schema wird die fortlaufende Erhöhung der Tiefengrenze dargestellt.

Iteratives Erzeugen eines Tiefensuchwaldes

Das Artikelbeispiel beschreibt einen iterativen Algorithmus, der den Tiefensuchwald eines Graphen G erzeugt. Ein Tiefensuchwald besteht aus den bei der Tiefensuche entstehenden Bäumen; mehrere Bäume sind nötig, wenn nicht alle Knoten vom ersten Startknoten aus erreichbar sind. Der Algorithmus verwendet Farben sowie Discovery- und Finishing-Times: Weiß kennzeichnet unentdeckte, Grau entdeckte, aber noch nicht abgeschlossene, und Schwarz abgeschlossene Knoten. d[u] bezeichnet die Entdeckzeit eines Knotens u, f[u] seine Abschlusszeit und pi[u] seinen Vorgänger.

Zu Beginn werden alle Knoten weiß gefärbt und ihre Vorgänger auf null gesetzt. Der Zeitzähler time beginnt bei 0, ebenso wird der Stack S initialisiert. Die Suche startet definitionsgemäß beim alphabetisch kleinsten weißen Knoten. Dieser wird grau gefärbt, erhält eine Entdeckzeit und wird auf den Stack gelegt. Ein Stack ist ein Speicher nach dem Prinzip „zuletzt hinein, zuerst heraus“.

Die Methode nextw(u) liefert den alphabetisch kleinsten weißen Nachbarn des Knotens u. Gibt es einen solchen Nachbarn v, wird v grau gefärbt, seine Entdeckzeit gesetzt und u als Vorgänger eingetragen. Besitzt v selbst einen weißen Nachbarn, wird v auf den Stack gelegt; danach wird v zum aktuellen Knoten.

Gibt es keinen weißen Nachbarn mehr, wird der aktuelle Knoten schwarz gefärbt und seine Finishing-Time gesetzt. Anschließend wird ein früherer Knoten vom Stack geholt. Ist dieser noch grau, wird er wieder auf den Stack gelegt, damit von ihm aus weitere weiße Nachbarn untersucht werden können. Auf diese Weise wird das für rekursive Tiefensuche typische Backtracking, also das schrittweise Zurückgehen zu früheren Knoten, mithilfe des Stacks nachgebildet. Wird der Stack leer, beginnt der äußere Durchlauf gegebenenfalls bei einem weiteren weißen Knoten und erzeugt so einen weiteren Baum des Tiefensuchwaldes.

Laufzeit und Speicherbedarf

Da die iterative Tiefensuche intern Tiefensuche verwendet, ist ihr Speicherplatzbedarf ähnlich dem der normalen Tiefensuche. Im Arbeitsspeicher muss höchstens ein vollständiger Ast bis zur jeweils aktuellen Iterationstiefe gespeichert werden.

Nach der Angabe des Artikels beträgt die Laufzeit im schlimmsten Fall O(|V| + |E|). Dabei ist |V| die Anzahl der Knoten und |E| die Anzahl der Kanten des Graphen. Als Begründung wird genannt, dass im schlimmsten Fall alle möglichen Pfade zu allen möglichen Knoten betrachtet werden müssen. Zusätzlich entsteht gegenüber einer einzelnen Tiefensuche Aufwand, weil in jeder Iteration die bereits durchsuchten Teile des Suchbaums erneut aufgebaut werden.

Vollständigkeit und Optimalität

Die iterative Tiefensuche ist vollständig: Wenn eine Lösung existiert, kann sie grundsätzlich gefunden werden. Durch die schrittweise erhöhte Tiefengrenze kann sich das Verfahren weder dauerhaft in einem unendlich langen Pfad noch in Zyklen verlieren.

Optimal bedeutet, dass eine Lösung mit minimalen Pfadkosten gefunden wird. Die iterative Tiefensuche ist laut Artikel optimal, wenn alle Pfadkosten äquivalent sind; dann entspricht die geringste erreichte Tiefe zugleich dem kürzesten Pfad zum Ziel. In der einleitenden Darstellung wird dies auch für monoton steigende Pfadkosten angegeben. Sind die Pfadkosten nicht äquivalent, kann dagegen ein suboptimaler Pfad gewählt werden.