Bestensuche

Bestensuche (engl. Best-first search) ist ein Algorithmus zum Durchsuchen eines Graphen, bei dem in jeder Iteration der vielversprechenste Knoten gewählt wird, bewertet nach einer gewissen Heuristik. Damit zählt er zu den informierten Such-Algorithmen.

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

Um den vielversprechensten Folgeknoten zu bestimmen, wird in konkreten Implementierungen oftmals eine Vorrangwarteschlange verwendet.

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

Inhaltsverzeichnis

Pseudo-Code [2]

OPEN = [Ausgangszustand]
while OPEN nicht leer
do
 1. Nehme besten Knoten aus OPEN, nenne ihn n.
 2. Wenn n der Zielzustand ist, bestimme Pfad zu n (anhand gemerkter Elternknoten) und gebe 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 nicht vollstä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 leer
do
 1. Nehme 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 gebe 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

Siehe auch

Einzelnachweise

  1. Pearl, J. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, 1984. Seite 48.
  2. http://www.macs.hw.ac.uk/~alison/ai3notes/subsubsection2_6_2_3_2.html Best First Search

Weblinks


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Branch-and-Bound — (Verzweigung und Schranke) ist eine im Bereich Operations Research häufig verwendete mathematische Methode, deren Ziel darin besteht, für ein gegebenes ganzzahliges Optimierungsproblem eine beste Lösung zu finden. Branch and Bound führt auf einen …   Deutsch Wikipedia

  • Branch and Bound — (Verzweigung und Schranke) ist eine im Bereich Operations Research häufig verwendete mathematische Methode, deren Ziel darin besteht, für ein gegebenes ganzzahliges Optimierungsproblem eine beste Lösung zu finden. Branch and Bound führt auf einen …   Deutsch Wikipedia

  • Branch and bound — (Verzweigung und Schranke) ist eine im Bereich Operations Research häufig verwendete mathematische Methode, deren Ziel darin besteht, für ein gegebenes ganzzahliges Optimierungsproblem eine beste Lösung zu finden. Branch and Bound führt auf einen …   Deutsch Wikipedia

  • Chart-Parser — Ein Chart Parser, auch Chartparser geschrieben, ist ein Parser für kontextfreie Grammatiken, der sich Teilanalysen (Teilkonstituenten) in einer Tabelle (Chart) merkt. Diese Zwischenspeicherung und Wiederverwendung von Teilanalysen verbessert die… …   Deutsch Wikipedia

  • Chart Parsing — Ein Chartparser ist ein Parser für kontextfreie Grammatiken, der sich Teilanalysen (Teilkonstituenten) in einer Tabelle (Chart) merkt. Diese Zwischenspeicherung und Wiederverwendung von Teilanalysen verbessert die Effizienz erheblich und macht… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”