Iterative Tiefensuche

Die iterative Tiefensuche ist ein Baumsuchverfahren, welches die Vorteile von Tiefen- und Breitensuche in sich vereint. Bei der Breitensuche wird der Suchbaum Ebene für Ebene durchsucht. Dieses hat den Vorteil, daßder erste gefundene Lösungsknoten auch ein optimaler Lösungsknoten ist, da alle höheren Ebenen des Baumes zuvor ohne Erfolg durchsucht worden sind. Der große Nachteil der Breitensuche liegt jedoch in dem Speicherplatzbedarf, da bei diesem Verfahren alle Knoten einer Ebene des Suchbaumes im Speicher gehalten werden müssen. Die Knotenzahl einer Ebene des Baumes wächst in der Regel exponentiell mit der Suchtiefe.

Bei der Tiefensuche wächst der Speicherplatzbedarf nur linear mit der Suchtiefe. Hier kann jedoch die Suche beliebig in die tieferen Ebenen des Baumes laufen, so daßdabei unnötig viele Knoten betrachtet werden. Dieses kann durch die Einführung einer Tiefenschranke verhindert werden. Diese Schranke sorgt dafür, daßdie Suche an einer Stelle abgebrochen wird, wenn eine bestimmte Tiefe erreicht ist. Die Schwierigkeit liegt dabei jedoch in der Wahl dieser Schranke: Ist sie zu niedrig, so wird kein Lösungsknoten expandiert, wird sie zu großgewählt, so werden unnötig viele Knoten betrachtet. In der iterativen Tiefensuche werden eine Reihe von Tiefensuchen mit wachsender Tiefenschranke durchgeführt, wobei die Schranke nach einer erfolglosen Iteration um einen minimalen Wert erhöht wird. Dadurch wird sichergestellt, daßdie erste gefundene Lösung auch optimal ist.

Zur Steigerung der Effizienz bei der Suche ist es sinnvoll, durch problemspezifische Informationen die Suche auf die ,,günstigeren`` Bereiche des Baumes zu beschränken. Diese heuristischen Informationen kommen in einer Knotenbewertungsfunktion zum Ausdruck und geben die geschätzten Kosten für einen Pfad von einem Knoten im Suchbaum zu einem Lösungsknoten an. Eine typische Knotenbewertungsfunktion, wie sie auch in dem Bestensuch-Algorithmus A* [8] verwendet wird, setzt sich für einen Knoten wie folgt zusammen:

Dabei bezeichnet die heuristische Funktion und beschreibt die minimalen Kosten für einen Pfad von der Wurzel des Suchbaumes zu diesem Knoten . Die Knotenbewertungsfunktion repräsentiert somit die voraussichtlichen Kosten für den günstigsten Pfad von der Wurzel zu einem Lösungsknoten, welcher durch den Knoten verläuft.

Der heuristische iterative Tiefensuchalgorithmus IDA* (Iterative deepening A*) [4] verwendet die beschriebene Bewertungsfunktion, um kostenbeschränkte Tiefensuchen durchzuführen. Im Gegensatz zur reinen iterativen Tiefensuche ist nicht die Tiefe eines Knotens entscheidend dafür, ob dieser Knoten in der aktuellen Iteration noch weiter expandiert wird, sondern der Wert der Bewertungsfunktion. Wird die Kostenschranke zwischen den Iterationen um einen minimalen Wert erhöht und überschätzt die heuristiche Funktion die tatsächlichen Kosten nicht, so ist sichergestellt, daßder Algorithmus IDA* einen optimalen Lösungsknoten, d.h. einen Knoten mit minimalen Kosten, findet, falls dieser existiert. Wächst die Zahl der in einer Iteration betrachteten Knoten exponentiell mit der Iterationszahl, so ist der durch die redundanten Knotenexpansionen in den einzelnen Iterationen entstandene Mehraufwand vernachlässigbar, da der Algorithmus IDA* in diesem Fall asymptotisch den gleichen Zeitaufwand hat wie der optimale Algorithmus A* [4].