Beschränkte Tiefensuche

Kernidee und Zweck

Die Beschränkte Tiefensuche (englisch depth-limited search, DLS) ist ein Verfahren, um einen Knoten in einem Graphen zu suchen. Sie ist eine Abwandlung der Tiefensuche und wird unter anderem in der iterativen Tiefensuche verwendet.

Wie die normale Tiefensuche ist DLS eine uninformierte Suche. Der entscheidende Unterschied besteht darin, dass eine maximale Suchtiefe vorgegeben wird. Sobald diese Tiefe erreicht ist, bricht die Suche dort ab. Dadurch terminiert der Algorithmus auf jeden Fall und kann sich weder in unendlich tiefen Pfaden noch in Zyklen verlieren.

Liegt eine Lösung innerhalb der vorgegebenen Tiefe, kann die Beschränkte Tiefensuche vollständig sein: Sie findet diese Lösung dann unabhängig vom Aufbau des Graphen.

Ablauf des Algorithmus

Zunächst werden der Startknoten und die maximale Suchtiefe bestimmt. Anschließend wird geprüft, ob der aktuelle Knoten innerhalb dieser Grenze liegt. Liegt er nicht innerhalb der maximalen Suchtiefe, wird an dieser Stelle nichts weiter getan.

Liegt der Knoten innerhalb der Grenze, wird er expandiert, also seine Nachfolger werden ermittelt und in einem Stack gespeichert. Danach wird für die Knoten des Stacks rekursiv erneut DLS aufgerufen. Ein Zielknoten wird gefunden, wenn der aktuelle Knoten dem gesuchten Knoten entspricht.

Formal lässt sich der Ablauf so beschreiben: DLS(node, goal, depth) prüft zuerst, ob node = goal gilt, und gibt in diesem Fall node zurück. Andernfalls wird stack := expand(node) gesetzt. Solange der Stack nicht leer ist, wird ein Knoten node' entnommen. Gilt node'.depth() < depth, wird DLS(node', goal, depth) rekursiv aufgerufen.

Laufzeit und Speicherbedarf

Da die Beschränkte Tiefensuche intern auf der Tiefensuche beruht, entspricht ihr Speicherplatzbedarf dem der normalen Tiefensuche.

Auch die Laufzeit ist äquivalent zur Laufzeit der normalen Tiefensuche. Sie beträgt O(|V| + |E|). Dabei steht |V| für die Anzahl der Knoten und |E| für die Anzahl der Kanten im erkundeten Graphen.

Zu beachten ist, dass nicht unbedingt alle Knoten und Kanten des gesamten Graphen betrachtet werden. Expandiert werden nur Knoten, die innerhalb der selbst vorgegebenen maximalen Tiefe liegen.

Vollständigkeit und Optimalität

Im Allgemeinen ist die Beschränkte Tiefensuche nicht vollständig. Wird die maximale Suchtiefe zu gering gewählt, kann eine Lösung, die weiter entfernt liegt, nicht gefunden werden. Ist die maximale Suchtiefe dagegen tiefer als die Tiefe, auf der die Lösung liegt, ist der Algorithmus vollständig.

DLS ist außerdem nicht optimal. Sie folgt einem Pfad weiterhin so lange wie möglich in die Tiefe. Deshalb kann sie auf diesem Pfad ein Ziel finden, dessen Kosten sehr viel höher sind als die Kosten eines alternativen Ziels auf einem anderen Pfad.