Best-First-Suche
Best-First-Suche ist eine Klasse von Suchalgorithmen, die a erforschen a Graph Durch Erweiterung des vielversprechendsten Knotens, der gemäß einer bestimmten Regel ausgewählt wurde.
Judäa Perle beschrieb die beste Suche als Schätzung des Versprechens des Knotens n durch eine "heuristische Bewertungsfunktion was im Allgemeinen von der Beschreibung von abhängen kann n, Die Beschreibung des Ziels, die Informationen, die von der Suche bis zu diesem Punkt und vor allem über zusätzliche Kenntnisse über die Problemdomäne gesammelt wurden. "[1][2]
Einige Autoren haben "Best-First-Suche" verwendet, um sich speziell auf eine Suche mit a zu beziehen Heuristik Dies versucht vorherzusagen, wie nahe das Ende eines Pfades an einer Lösung (oder, das Ziel) liegt, so dass Pfade, die als näher an einer Lösung (oder, das Ziel) beurteilt werden, zuerst verlängert werden. Diese spezifische Suche wird aufgerufen gierig Best-First-Suche[2] oder reine heuristische Suche.[3]
Eine effiziente Auswahl des aktuellen besten Kandidaten für die Erweiterung wird normalerweise mit a implementiert Prioritätswarteschlange.
Das Ein* Suchalgorithmus ist ein Beispiel für einen besten Suchalgorithmus, wie es ist B*. Best-First-Algorithmen werden häufig für den Pfadaufkommen in verwendet Kombinatorische Suche. Weder A* noch B* sind eine gierige Best-First-Suche, da sie den Abstand von Anfang zu den geschätzten Entfernungen zum Ziel enthalten.
Gierige BFS
Verwendung einer Gieriger AlgorithmusErweitern Sie den ersten Nachfolger des Elternteils. Nachdem ein Nachfolger erstellt wurde:[4]
- Wenn die Heuristik des Nachfolgers besser ist als sein Elternteil, steht der Nachfolger vor der Warteschlange (wobei der Elternteil direkt dahinter wieder eingestuft wird) und die Schleife neu startet.
- Andernfalls wird der Nachfolger in die Warteschlange eingefügt (an einem von seinem heuristischen Wert bestimmten Ort). Das Verfahren bewertet die verbleibenden Nachfolger (falls vorhanden) des Elternteils.
Unten ist a Pseudocode Beispiel für diesen Algorithmus, wo Warteschlange stellt eine vorrangige Warteschlange dar, die Knoten basierend auf ihren heuristischen Entfernungen vom Ziel bestellt. Diese Implementierung verfolgt besuchte Knoten und kann daher für verwendet werden ungerichtete Grafiken. Es kann geändert werden, um den Pfad abzurufen.
Verfahren GBS (Start, Ziel) ist: markieren Sie als besuchte Start in die Warteschlange hinzufügen während Warteschlange ist nicht leer tun: current_node ← Scheitelpunkt der Warteschlange mit minem Abstand zum Ziel REMORT Current_Node aus der Warteschlange für jeden Nachbar n von current_node tun: wenn n nicht in hat besucht dann: wenn n ist Ziel: Rückkehr n anders: Mark n als besuchter Fügen Sie die Warteschlange hinzu. Rückkehr Versagen
Siehe auch
Verweise
- ^ Pearl, J. Heuristik: Intelligente Suchstrategien zur Lösung von Computerproblemen. Addison-Wesley, 1984. p. 48.
- ^ a b Russell, Stuart J.; Norvig, Peter (2003), Künstliche Intelligenz: ein moderner Ansatz (2. Aufl.), Upper Saddle River, New Jersey: Prentice Hall, ISBN 0-13-790395-2. S. 94 und 95 (Anmerkung 3).
- ^ Korf, Richard E. (1999). "Suchalgorithmen für künstliche Intelligenz". In Atallah, Mikhail J. (Hrsg.). Handbuch der Algorithmen und der Theorie der Berechnung. CRC Press. ISBN 0849326494.
- ^ https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume28/coles07a-html/node11.html#modifiedBestfs Gierige Best-First-Suche, wenn EHC versagt, Carnegie Mellon
Externe Links
- Wikibooks: Künstliche Intelligenz: Best-First-Suche