Was sind die Unterschiede zwischen dem A * -Algorithmus und dem gierigen Best-First-Suchalgorithmus? Welches soll ich verwenden? Welcher Algorithmus ist der bessere und warum?
Antwort
Beide Algorithmen fallen in die Kategorie „Best-First-Suche“ Algorithmen, bei denen es sich um Algorithmen handelt, die sowohl das bisher bei der Erkundung des Suchraums erworbene Wissen verwenden können, als auch mit $ g (n) $ bezeichnet. und eine heuristische Funktion, bezeichnet mit $ h (n) $ , die den Abstand zum Zielknoten für jeden Knoten schätzt $ n $ im Suchraum (oft als Grafik dargestellt).
Jeder dieser Suchalgorithmen definiert eine „Bewertungsfunktion“ für jeden Knoten $ n $ im Diagramm (oder Suchraum), bezeichnet mit $ f (n) $ . Diese Auswertungsfunktion wird verwendet, um zu bestimmen, welcher Knoten während der Suche zuerst „erweitert“ wird, dh welcher Knoten zuerst aus dem „Rand“ (oder „Grenze“) entfernt wird. oder „Grenze“) , um seine Kinder zu „besuchen“. Im Allgemeinen liegt der Unterschied zwischen den Algorithmen in der Kategorie „Best-First“ in der Definition der Bewertungsfunktion $ f (n) $ .
Im Fall von dem gierigen BFS-Algorithmus lautet die Bewertungsfunktion $ f (n) = h (n) $ , dh der gierige BFS-Algorithmus erweitert zuerst den Knoten, dessen geschätzte Entfernung zum Ziel am kleinsten ist. Gieriges BFS verwendet also nicht das „vergangene Wissen“, d. H. $ g (n) $ . Daher seine Konnotation „gierig“. Im Allgemeinen ist der gierige BST-Algorithmus nicht vollständig , dh es besteht immer das Risiko, einen Pfad einzuschlagen, der dies nicht tut zum Ziel bringen. Im gierigen BFS-Algorithmus werden alle Knoten an der Grenze (oder am Rand oder an der Grenze) im Speicher gehalten, und Knoten, die bereits erweitert wurden, müssen nicht im Speicher gespeichert werden und können daher verworfen werden. Im Allgemeinen ist das gierige BFS auch nicht optimal , dh der gefundene Pfad ist möglicherweise nicht der optimale. Im Allgemeinen beträgt die zeitliche Komplexität $ \ mathcal {O} (b ^ m) $ , wobei $ b $ ist der (maximale) Verzweigungsfaktor und $ m $ ist die maximale Tiefe des Suchbaums. Die Raumkomplexität ist proportional zur Anzahl der Knoten im Rand und zur Länge des gefundenen Pfads.
Im Fall von ist das A. * Algorithmus lautet die Bewertungsfunktion $ f (n) = g (n) + h (n) $ , wobei $ h $ ist eine zulässige heuristische Funktion . Der „Stern“, oft mit einem Sternchen gekennzeichnet, *, bezieht sich auf die Tatsache, dass A * eine zulässige heuristische Funktion verwendet, was im Wesentlichen bedeutet, dass A * optimal , dh es wird immer der optimale Pfad zwischen dem Startknoten und dem Zielknoten gefunden. Ein * ist auch vollständig (es sei denn, es gibt unendlich viele Knoten, die im Suchraum untersucht werden müssen). Die zeitliche Komplexität beträgt $ \ mathcal {O} (b ^ m) $ . A * muss jedoch während der Suche alle Knoten im Speicher behalten, nicht nur die im Randbereich, da A * im Wesentlichen eine „umfassende Suche“ durchführt (die „informiert“ ist, in dem Sinne, dass sie eine heuristische Funktion verwendet ).
Zusammenfassend ist gieriges BFS nicht vollständig, nicht optimal und hat eine zeitliche Komplexität von $ \ mathcal {O} (b ^ m) $ und eine Raumkomplexität, die polynomisch sein kann. A * ist vollständig, optimal und hat eine zeitliche und räumliche Komplexität von $ \ mathcal {O} (b ^ m) $ . Im Allgemeinen verwendet A * also mehr Speicher als gieriges BFS. Ein * wird unpraktisch, wenn der Suchraum sehr groß ist. A * garantiert jedoch auch, dass der gefundene Pfad zwischen dem Startknoten und dem Zielknoten der optimale ist und dass der Algorithmus schließlich beendet wird. Gieriges BFS benötigt dagegen weniger Speicher, bietet jedoch nicht die Optimalitäts- und Vollständigkeitsgarantien von A *. Welcher Algorithmus der „beste“ ist, hängt vom Kontext ab, aber beide sind „beste“ erste Suchvorgänge.
Hinweis: In der Praxis dürfen Sie keinen dieser Algorithmen verwenden: Sie können z. Verwenden Sie stattdessen IDA * .
Kommentare
- Kommentare sind nicht für erweiterte Diskussion; Diese Konversation wurde in den Chat verschoben .
Antwort
Laut dem Buch Künstliche Intelligenz: Ein moderner Ansatz (3. Auflage) von Stuart Russel und Peter Norvig, insbesondere Abschnitt 3.5.1 Gierige Best-First-Suche (S. 92)
Die gierige Best-First-Suche versucht, den Knoten zu erweitern, der dem Ziel am nächsten liegt wird wahrscheinlich schnell zu einer Lösung führen. Daher werden Knoten nur mit der heuristischen Funktion ausgewertet. Das heißt, $ f (n) = h (n) $ .
In diesem Fall Im selben Abschnitt geben die Autoren ein Beispiel, das zeigt, dass die gierige Best-First-Suche weder optimal noch vollständig ist.
In Abschnitt 3.5.2 A * -Suche: Durch Minimierung der geschätzten Gesamtlösungskosten desselben Buches (S. 93) wird
A angegeben * Die Suche bewertet Knoten, indem $ g (n) $ , die Kosten für das Erreichen des Knotens und $ h (n) kombiniert werden. $ , die Kosten, um vom Knoten zum Ziel zu gelangen $$ f (n) = g (n) + h (n). $$
Da $ g (n) $ die Pfadkosten vom Startknoten zum Knoten $ n $ angibt und $ h (n) $ sind die geschätzten Kosten des billigsten Pfads von $ n $ zum Ziel haben wir $ f (n) $ = geschätzte Kosten der billigsten Lösung durch $ n $ .
Wenn wir versuchen, die billigste Lösung zu finden, ist es sinnvoll, zuerst den Knoten mit dem niedrigsten Wert von $ g (n) + h (n) $ zu versuchen. Es stellt sich heraus, dass diese Strategie mehr als nur vernünftig ist: Vorausgesetzt, die heuristische Funktion $ h (n) $ erfüllt bestimmte Bedingungen, ist die A * -Suche sowohl vollständig als auch optimal. Der Algorithmus ist identisch mit der Suche nach einheitlichen Kosten, außer dass A * $ g + h $ anstelle von $ g $
Antwort
Was Sie gesagt haben, ist nicht völlig falsch. Der A * -Algorithmus wird jedoch optimal und vollständig, wenn die heuristische Funktion h zulässig ist, was bedeutet, dass diese Funktion die Kosten für das Erreichen des Ziels niemals überschätzt. In diesem Fall ist der A * -Algorithmus viel besser als der gierige Suchalgorithmus.
Kommentare
- Lieber, können Sie Ihre Antwort ausarbeiten? Tut mir leid, aber ich habe Ihren Standpunkt nicht verstanden.
- @IramShah – TemmanRafk spricht über den Beweis, dass A * sowohl optimal als auch vollständig ist. Um dies zu tun, wird aufgrund der Dreiecksungleichheit gezeigt, dass die Heuristik, die den verbleibenden Abstand zum Ziel schätzt, keine Überschätzung darstellt. Eine ausführlichere Erklärung finden Sie unter en.wikipedia.org/wiki/Admissible_heuri stic