Breitensuche (Breath-First-Search)

Die Tiefe eines Knotens wird benutzt um festzulegen, welcher Knoten zuerst expandiert wird. Je niederiger die Tiefe, desto eher die Expansion. Das hat zur Folge, daß zuerst der Root(Wurzel)-Knoten expandiert wird, der die Tiefe 0 hat. Danach wird mit den Kindern fortgefahren, die die Tiefe 1 besitzen. So geht es mit deren Kindern weiter und so fort... Zwischen zwei Knoten gleicher Tiefe gibt es keine bestimmte Priorität. Würde man diesen Vorgang graphisch visualisieren, entspräche dies einem Durchlauf von der Wurzel zu den Blättern, bei der erst die volle Breite expandiert wird, bevor eine Ebene tiefer gegangen wird.
 Auf diese Weise, werden Lösungen, mit geringeren Kosten eher gefunden als solche mit höheren. Wird also eine Lösung gefunden, so ist es auch die günstigste. Der Algorithmus ist daher optimal. Zudem wird die Breitensuche in dieser Form, irgendwann jeden erdenklichen Pfad geprüft haben. Somit wird, wenn eine Lösung existiert, diese auch gefunden. Die Breitensuche ist daher auch vollständig.
 Schon für kleinere Probleme stellt sich jedoch heraus, daß dieser Algorithmus oftmals schnell an seine Grenzen stößt. Da am Ende fast alle Knoten expandiert im Speicher stehen und die Anzahl dieser exponentiell wächst, ist der Speicherbedarf immens. Genauso vernichtend ist die Betrachtung der Rechenzeit. Da eine Lösung frühstens gefunden ist, wenn man an einem der Blätter angekommen ist, entstehen nicht tragbare Rechenzeiten.
 Der Grund, warum dieser Algorithmus betrachtet wird liegt zum einen in seiner didaktischen Einfachheit, zum anderen darin, daß er einfach zu implementieren ist. Dazu erzeugt man zwei Queues. Die eine enthält alle noch nicht expandierten Knoten. Am Anfang also den Root-Knoten. In die andere Queue legt man die schon geöffneten Knoten ab. Bei einfachen Problemen kann man diese zweite Queue auch weglassen. Nun wird nichts anderes getan, als von der ersten Queue der erste Knoten genommen und mit der Zielfunktion getestet. Erfüllt er diese nicht, wird er expandiert. Seine auf diese Weise erhaltenen Kinder werden ans Ende derselben Queue geschrieben. Danach wird er ggf. auf die zweite Queue abgelegt. Der Algorithmus ist beendet, wenn entweder die Zielfunktion ein 'True' liefert, oder kein weiterer Knoten zum expandieren auf der Queue liegt. In letzterem Fall gibt es keine Lösung.

Optimalität (Optimality): ja
Vollständigkeit (Completeness): ja
Zeitlicher Aufwand (Time-Complexity): sehr hoch: O(b^d)
Speicherbedarf (Space-Complexity): sehr hoch: O(b^d)

Java Visualisierung

Start

Uniform-Cost-Search

Dieser Algorithmus unterscheidet sich kaum vom vorherigen. Wurde vorher angenommen, daß keine Kostenfunktion existiert, bzw. daß sie durch die Tiefe der Knoten repräsentiert wird, so ist dies jetzt anders. Die Breitensuche wird also an ein Problem mit Kostenfunktion angepasst. Dazu geht man ganz genauso vor. Lediglich anders ist, daß nicht der Knoten mit der geringsten Tiefe expandiert wird, sondern der mit den geringsten Kosten. Umgekeht, kann man auch die Breitensuche als Spezialfall der Uniform-Cost-Search betrachten, bei der die Kostenfunktion der Knotentiefe entspricht.
 Das Verhalten dieses Algorithmusses bzgl. Optimalität, Vollständigkeit, zeitlichen Aufwandes und Speicherbedarfs verhält sich von daher genauso.
 Bei der Implementierung muß darauf geachtet werden, daß bei der auch hier existierenden Queue die Knoten nach ihrer Tiefe sortiert werden müssen, was einen unvermeidlichen Mehraufwand bedeutet.

Optimalität (Optimality): ja
Vollständigkeit (Completeness): ja
Zeitlicher Aufwand (Time-Complexity): sehr hoch: O(b^d)
Speicherbedarf (Space-Complexity): sehr hoch: O(b^d)

Java Visualisierung

Start

Tiefensuche (Deep-First-Seach)

Die Tiefensuche kann auf gewisser Ebene als das Gegenstück zur Breitensuche gesehen werden. Es wird eben nicht dem Knoten mit der geringsten sondern, im Gegenteil dazu, dem Knoten mit der größten Tiefe den Vorzug gegeben. Es wird also zuerst so schnell wie möglich ein Weg des Baumes bis zum tiefsten Knoten heruntergelaufen, und erst wenn es nicht mehr weitergeht, wird ein Knoten zurückgesprungen um zu prüfen, ob es von dort aus noch andere Wege 'in die Tiefe' gibt. (Die Reihenfolge ist durch die Euler-Tour realisierbar, wenn man bei linkem Umlauf den jeweils linken Kontakt zum Knoten bewertet.)
 Bei Problemen mit vielen Lösungen ist die Wahrscheinlichkeit auf diese Art schnell zum Ziel zu kommen oft höher als bei der Breitensuche. Jedoch ist dieser Algorithmus nicht optimal. Es wäre nämlich nach Auffinden einer Lösung durchaus möglich, daß noch eine günstigere existiert. Ein Problem dieses Algorithmusses ist, das er nicht Vollständig ist. Das heißt es könnte eine Lösung existieren, die nicht gefunden wird. Dieser Sachverhalt, den man zuerst nicht vermuten würde, rührt daher, daß die Pfade nicht unbedingt eine endliche Tiefe besitzen. In einem solchen Fall würde der Suchalgorithmus in unendliche Tiefen (ab)stürzen.
 Die Implementierung kann analog zur Breitensuche geschehen, mit dem Unterschied, daß die Kinder eines expandierten Knotens nicht ans Ende sondern an den Anfang der Queue geschrieben werden. So wird ihnen der Vorzug gegenüber Knoten mit geringeren Tiefen gegeben. Eleganter ist eine Implementierung mit Hilfe von Rekursion, bei der zuerst alle Kinder besucht werden, bevor der Knoten selbst getestet wird:

besuche(Knoten){
 for(alle Kinder von Knoten){
  besuche(Kind);
 }
 if(Zielfunktion(Knoten)==true){
  //Lösung wurde gefunden
 }
}

Optimalität (Optimality): nein
Vollständigkeit (Completeness): nein
Zeitlicher Aufwand (Time-Complexity): O(b^m) (worst Case)
Speicherbedarf (Space-Complexity): O(b*m)

Java Visualisierung

Start

Begrenzte Tiefensuche (Deep-Limited-Search)

Die Tiefenbegrenzte Suche ist eine Erweiterung der Tiefensuche, bei der ja das Problem auftrat, daß bei unendlich tiefen Wegen, die Suche kein Ende findet. Und das obwohl trotzdem ein endlicher Lösungsweg existieren kann. Um dieses Problem in den Griff zu bekommen, bedient man sich des simplen Tricks die Tiefe zu begrenzen. Normalerweise weiß man jedoch nichts über die Tiefe des Problems, deshalb ist es möglich, daß auch hier keine Lösung gefunden wird, obwohl sie existiert.

Optimalität (Optimality): nein
Vollständigkeit (Completeness): nein
Zeitlicher Aufwand (Time-Complexity): O(b^l)
Speicherbedarf (Space-Complexity): O(b*l)

Java Visualisierung

Start

Iterative Tiefensuche (Iterative Deepening Search)

Dieser Algorithmus versucht die Vorteile von Tiefensuche und Breitensuche zu vereinen. Im wesentlichen funktioniert er wie die eben beschriebene begrenzte Tiefensuche. Allerdinx wird das Limit dabei von 0 an raufgezählt. Man wird also nicht vor das Problem gestellt, überlegen zu müssen welche Tiefenbegrenzung man zu wählen hat. Das Heraufzählen der Tiefe erinnert intuitiv an die Breitensuche. Tatsächlich ist dieser Algorithmus plötzlich optimal und abgeschlossen. Dadurch, daß für jede Tiefenbegrenzung eine Tiefensuche durchgeführt wird, muß eine Lösung gefunden werden, sofern sie existiert. Da sie das erste mal beim Erreichen eines Limits gefunden wird, muß sie zudem die optimale Lösung sein. Bezahlen tut man für diese Vorteile mit vermehrten Baumdurchläufen. Wird eine Lösung in der Tiefe d gefunden, so muß die tiefenbegrenzte Suche vorher schon für die Tiefen von 0 bis d-1 durchgeführt werden. Das sind d Baumduchläufe mehr als bei der einfachen tiefenbegrenzten Suche. Das klingt im ersten Moment furchtbar, ist aber (im für b=2 fast wörtlichen Sinne) halb so schlimm. Denn durch das exponentielle Wachstum des Baumes nimmt der letzte Baum, den bei Weitem größten Suchaufwand in Anspruch. Bei binären Bäumen sind das etwa 50%.

Optimalität (Optimality): ja
Vollständigkeit (Completeness): ja
Zeitlicher Aufwand (Time-Complexity): O(b^d)
Speicherbedarf (Space-Complexity): O(b*d)

Java Visualisierung

Start

Bidirektionale Suche

Die bidirektionale Suche ist eigentlich eine Breitensuche. Die Besonderheit ist die, daß "gleichzeitig" versucht wird vom Ziel ausgehend eine Art rückwärtige Breitensuche anzustreben. Dabei werden jeweils alle möglichen Elternknoten gesucht. Dadurch entsteht ein zweiter ähnlich wachsender Baum. Es wird stetig geprüft ob es irgendwo eine Überschneidung von Knoten beider Bäume gibt. Findet man eine solche läßt sich daraus der Lösungsweg rekonstruieren. Der Aufwand ist um einiges kleiner als bei der herkömmlichen Breitensuche, da beide Bäume, deren Knotenanzahl ja exponentiell mit ihrer momentanen Höhe wächst, ja nur halb so hoch werden müssen. Der Nachteil dieses Verfahrens ist die aufwendige, oder oft auch nicht mögliche Implementierung. Das Hauptproblem ist das Auffinden der möglichen Elternknoten eines Zielzustandes. Dabei muß man sich vor allem vor Augen halten das ein Zielzustand zwar durch die Zielfuntion eindeutig definiert wird, aber die Menge aller Zielzustände kann ein großes Mysterium sein. Man denke sich hierbei Zielfunktionen die beispielsweise einen Wert daraufhin prüfen ob er prim ist.
 Desweiteren ist das Testen, ob zwei Blätter sich schon berührt haben ein nicht zu unterschätzender Aufwand.
Die bidirektionale Suche muß nicht zwangsweise als Breitensuche realisiert werden. Andere Suchverfahren wären ebenfalls denkbar.

Optimalität (Optimality): ja
Vollständigkeit (Completeness): ja
Zeitlicher Aufwand (Time-Complexity): O(b^(d/2))
Speicherbedarf (Space-Complexity): O(b^(d/2))

Start

b: Verzweigungsfaktor (Branching Faktor)
m: Maximale Tiefe
d: Tiefe des nähsten Ziels
l: Tiefenlimit