Bestensuche-Algorithmen (Best-First-Search)

Hier wird der Knoten zuerst expandiert, der vermutlich am schnellsten zum Ziel führt. Welcher das jeweils ist verrät die Evaluations-Funktion. Diese ist von Problem zu Problem verschieden und hat zudem nicht unbedingt immer Recht. Wichtig ist nur, daß sie oftmals den richtigen Tip bereithält um so die Suchzeit zu verkürzen.
 Die Implementierung erfolgt wie bei der Breiten- und Tiefensuche mittels einer Queue. Der Unterschied besteht darin, daß vor jeder Expansion die Knoten anhand der Werte der Evaluations-Funktion sortiert werden.
 Beispiele für Best-First-Algorithmen sind Greedy- und A*-Search .

Start

Gierige Suche (Greedy-Search)

Bei diesem Algorithmus wird der Knoten zuerst expandiert, der aufgrund einer Heuristik dem Ziel am nächsten ist. Dabei ist eine Heuristik eine spezielle Form einer Evaluations-Funktion. Mit ihr wird versucht ein mathematisches Abbild der menschlichen Intuition zu schaffen. Um eine gute Heuristik zu einem Problem zu finden, bedarf es viel Phantasie und Erfindungsgabe. Zudem lässt sich eine Heuristik fast nur durch Ausprobieren klassifizieren.
 Dieser Algorithmus wird wie jede Best-First-Suche implementiert, wobei halt als Evaluations-Funktion die Heuristik verwendet wird.
 In seinem Verhalten erinnert der Algorithmus sehr an die Tiefensuche, da auch hier erst in die Tiefe gesucht wird, und nur wenn sich der Weg als Sackgasse erweist, wird an höherer Stelle nach Alternativen gesucht. Die Leistung ist sehr stark von der gewählten Heuristik abhängig.
 Heuristiken werden als 'zulässig' bezeichnet, wenn sie 'optimistisch' sind. Das bedeutet, daß eine zulässige Heuristik die Kosten unterschätzen muß.

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

A*-Suche (A*-Search)

Bei A* wird als Evaluations-Funktion die Summe aus den Kosten bis zum aktuellen Knoten und einer Heuristik genommen. Da man die Heuristik weitesgehend auch mit einer Abschätzung der Kosten bis zum Ziel identifizieren kann, ist die hier benutzte Evaluations-Funktion in etwa so etwas wie die geschätzten Kosten der Lösung, die auf diesem Weg zu finden wäre. Wichtig bei der Heuristik ist hier, daß sie eine sogenannte "optimistische Heuristik" ist. Das bedeutet, daß ihre Abschätzung stets besser ist als der wirkliche Wert. Auf diese Weise kann sichergestellt werden, daß entlang jedes Weges im Grafen die Kosten stets steigen.
 Die Implementierung ist wieder die gleiche, lediglich die Evaluations-Funktion wird ausgetauscht.
 Setzt man die Heuristik gleich null, so erhält man die Uniform-Cost-Search. Von dieser Verwandschaft erbt die A*-Suche ihre Optimalität und Abgeschlossenheit.

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

Java Visualisierung

Start

Iteratives Vertiefen der A*-Suche (Iterative-Deepening-A*-Search : IDA*)

Hier wird die maximale Summe von aktuellen Kosten und dem geschätzten Restwert, also der Heuristik, nach oben hin durch ein Limit begrenzt. Dieses Limit,ähnlich wie bei der iterativen Tiefensuche, wird hochgezählt. Auf diese Weise werden sehr lange Wege vermieden, und es werden weniger Speicher-Ressourcen benötigt.

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

Start

Einfache Speicherbegrenzte A*-Suche (Simplified-Memorybounded-A*-Search : SMA*)

Dies ist eine modifizierte Version von IDA* für den Fall, daß der Speicher zu klein ist. Wird die Speichergrenze erreicht, wird ein Knoten von der Queue geschubst. Natürlich wählt man den, dessen Evaluationsfunktion den höchsten Wert liefert. Um zu vermeiden, daß bei erfolgloser Suche Teilbäume rekonstruiert werden müssen, die aber dann aufgrund ihres hohen Evaluationsfunktionswertes doch nicht weiterverfolgt werden, merkt man sich eben diesen jeweils besten Wert in dem Knoten des Vorfahren. Es befindet sich also in jedem Knoten ein Attribut, in dem sich der günstigste Evaluationsfunktionswert aller vergessenen Kinder gemerkt wird. Anhand dieses Attributes kann dann die Entscheidung getroffen werden, ob die Rekonstruktion des folgenden Astes sinnvoll ist.

Start

Rekursive Bestensuche (Recursive-Best-First-Search : RBFS)

Funktioniert wie SMA* mit der Besonderheit, das alle Evaluationsfunktionswerte der vergessenen Knoten im Vorfahren gemerkt werden.

Start

Alternativen zur baumorientierten Suche

Stellt man sich den Zustandsraum wie eine zweidimensionale Funktion vor, deren Funktionswerte die Evaluationsfunktion bestimmt, kommt die Bergsteige-Suche (Hill-Climbing-Search) zur Anwendung. Bei dieser wird, ausgehend von Zufallswerten immer in Richtung des höchsten Anstieges gegangen. Auf diese Weise landet man entweder auf einem Plateau, einem Bergrücken oder einer Spitze also einem Maximum an. Je nach Graphenform und Anzahl der Zufallswerte hat man gute Chancen neben vielen lokalen Maxima und anderen Sackgassen das absolute Maximum zu finden, man kann sich allerdinx nie ganz sicher sein.
 Eine Variation davon ist der Algorithmus der "Simulierten Abkühlung" (Simulated Annealing). Hierbei wird nicht kontinuierlich bergauf gegangen sondern es werden bedingt Fehler zugelassen. Zuerst wird eine zufällige Richtung gewählt. Wenn sie die Situation verbessert wird der Schritt ausgeführt, ansonsten wird die Schrittweite E vermindert. Die Wahrscheinlichkeit für falsche Schritte T wird dabei kontinuierlich vermindert.

Start