Bestensuche

aus Wikipedia, der freien Enzyklopädie

Zur Navigation springen Zur Suche springen

Bestensuche (engl.best-first search) ist ein Algorithmus zum Durchsuchen einesGraphen, bei dem in jeder Iteration der vielversprechendste Knoten gewählt wird, bewertet nach einer gewissenHeuristik. Damit zählt er zu deninformierten Such-Algorithmen.

Judea Pearl beschrieb die Bestensuche als das Abschätzen der Kosten eines Knotensn nach einer "heuristischen Bewertungsfunktion $f(n)$ , die im Allgemeinen abhängig von der Beschreibung vonn ist, der Beschreibung des Ziels, den vom Algorithmus bis zu diesem Zeitpunkt gesammelten Informationen und vor allem vom Zusatzwissen über dieProblemdomäne selbst."^[1]

Um den vielversprechendsten Folgeknoten zu bestimmen, wird in konkreten Implementierungen oftmals eineVorrangwarteschlange verwendet.

Ein bekanntes Beispiel für die Bestensuche ist derA*-Algorithmus. Zur Wegfindung wird Bestensuche auch oftmals in derkombinatorischen Optimierung eingesetzt.

Pseudo-Code

[Bearbeiten |Quelltext bearbeiten]

OPEN = [Ausgangszustand]while OPEN nicht leerdo 1. Nimm besten Knoten aus OPEN, nenne ihn n. 2. Wenn n der Zielzustand ist, bestimme Pfad zu n (anhand gemerkter Elternknoten) und gib ihn zurück. 3. Expandiere Nachfolger von n. 4. Bewerte jeden Nachfolger mithilfe der Heuristik, füge ihn zu OPEN hinzu, und merke n als Elternknoten.done

Diese Version des Algorithmus ist allerdings nichtvollständig, d. h., der gegebene Pseudo-Code findet nicht zu jeder möglichen Kombination von Start- und Zielknoten einen Weg, auch wenn dieser existiert. Beispielsweise verfängt sich der Algorithmus in einer Endlosschleife, sobald ein betrachteter Knoten keine Nachfolger mehr hat, außer dem Elternknoten selbst. In diesem Fall würde der Elternknoten erneut auf die OPEN-Liste gestellt, und daraufhin erneut betrachtet werden, was in einer endlosen Rekursion resultiert.

Die folgende Version erweitert den Algorithmus um eine zusätzliche CLOSED-Liste, die alle bereits bewerteten Knoten beinhaltet. Da somit kein Knoten zweimal besucht wird, werden hierdurch Endlosschleifen verhindert.

OPEN = [Ausgangszustand]CLOSED = []while OPEN nicht leerdo 1. Nimm besten Knoten aus OPEN, nenne ihn n, füge ihn zu CLOSED hinzu. 2. Wenn n der Zielzustand ist, bestimme Pfad zu n (anhand gemerkter Elternknoten) und gib ihn zurück. 3. Expandiere Nachfolger von n. 4. Für jeden Nachfolger:       a. Wenn nicht bereits in CLOSED, bewerte ihn mithilfe der Heuristik, füge ihn zu OPEN hinzu und merke n als Elternknoten.       b. Sonst: Aktualisiere gemerkten Elternknoten des Nachfolgers, wenn neuer Weg über n kostengünstiger ist als vorheriger.done

^[2]