Ich versuche, einige Suchkonzepte zu lernen, bin dabei aber in eine Wand gerannt. Kann mir jemand erklären, was der Unterschied zwischen Bergsteigen Suche und bester erster Suche ist? Für mich sehen beide so aus, als würden sie die Knoten mit dem heuristischen Wert erweitern, der dem Ziel am nächsten ist. Wenn mir jemand den Unterschied erklären kann, würde ich es sehr schätzen. Danke!
Sie können den Suchalgorithmus so anzeigen, dass er eine Warteschlange mit den verbleibenden zu durchsuchenden Knoten enthält. Diese Antwort demonstriert dieses Prinzip .
Bei der ersten Suche fügen Sie die untergeordneten Elemente des aktuellen Knotens zur Front der Warteschlange (einem Stapel) hinzu. Bei der Breitensuche fügen Sie die untergeordneten Elemente des aktuellen Knotens zum zurück der Warteschlange hinzu. Denken Sie einen Moment darüber nach, wie dies zu dem richtigen Verhalten für diese Algorithmen führt.
Bei der Hill-Climbing-Suche sortieren Sie [1] die untergeordneten Elemente des aktuellen Knotens , bevor Sie sie zur Warteschlange hinzufügen. Bei der Best-First-Suche fügen Sie die untergeordneten Elemente des aktuellen Knotens in beliebiger Reihenfolge in die Warteschlange ein und sortieren dann [1] die gesamte Warteschlange . Wenn Sie über den Effekt nachdenken, der sich auf die Reihenfolge auswirken könnte, in der die Knoten durchsucht werden, sollten Sie sich eine Vorstellung von dem praktischen Unterschied machen.
Ich fand dieses Konzept zu verwirrt, um es aus rein abstrakten Begriffen zu verstehen, aber wenn man ein paar Beispiele mit einem Bleistift durcharbeitet, wird es einfach.
[1]: Nach einer problemspezifischen Auswertung des Lösungsknotens sortieren, z. B. "Entfernung vom Ziel" bei einer Pfadsuche.
Lass mich Wiki das für dich :
Beim einfachen Bergsteigen, dem ersten näherer Knoten gewählt, während in steilster Aufstieg Bergsteigen alle Nachfolger werden verglichen und die am nächsten zur Lösung ist gewählt.
...
steilster Aufstieg Bergsteigen ist ähnlich wie Best-First Suche, die alles mögliche versucht Erweiterungen des aktuellen Pfades stattdessen von nur einem.
A liitle spät, aber hier geht.
In BFS geht es darum, das Ziel zu finden. Es geht also darum, den besten Knoten (den, von dem wir hoffen, dass er uns zum Ziel führt) unter den möglichen auszuwählen. Wir versuchen weiter auf das Ziel zuzugehen.
Aber beim Bergsteigen geht es um die Maximierung der Zielfunktion. Wir wählen den Knoten, der den höchsten Anstieg bietet. Anders als bei BFS wird auch der 'Wert' des Elternknotens berücksichtigt. Wenn wir nicht höher gehen können, geben wir einfach auf. In diesem Fall erreichen wir möglicherweise nicht einmal das Ziel. Wir könnten auf einem lokalen Maximum sein.
Der Unterschied liegt darin zu verstehen, was mehr betrifft bei der Suche nach dem Zielstatus . .
Stellen Sie die Frage, was unser Ziel ist ... der endgültige Zielzustand ? oder der Beste Pfad zum Erreichen des Zielstatus
Die Beste erste Suche ist ein systematischer Suchalgorithmus, bei dem die Systematik erreicht wird, indem iterativ auf der Grundlage des Herausfindens der bester heuristischer Wert für die benachbarten Knoten für jeden aktuellen Knoten.
Hier berechnet die Bewertungsfunktion (heuristische Funktion) die bestmöglicher Weg zum Erreichen des Zielzustands . Hier konnten wir sehen, dass die Best First-Suche sich mit dem besten PATH beschäftigt, um den Zielzustand zu erreichen.
Allerdings gibt es viele Probleme, bei denen " Pfad zum Ziel " keine Sorge ist. Das einzige, was betroffen ist, ist , um den Endzustand zu erreichen. stark> auf jede mögliche Art und Weise. (Zum Beispiel: 8-Königinnen-Problem ).
Daher werden für diese lokale Suchalgorithmen verwendet.
Lokale Suchalgorithmen arbeiten mit einem einzigen aktuellen Knoten und bewegen sich im Allgemeinen nur zum Nachbarn dieses Knotens.
Hill Climbing-Algorithmus ist ein lokaler Suchalgorithmus . Also hier müssen wir verstehen, die Annäherung an den Zielzustand nicht der beste Weg zu erreichen, wenn Sie über Bergsteigen denken.
(wie in AI-A Modern Approach, SR & amp; PN ) angegeben.
Um die lokale Suche zu verstehen, müssen wir uns die state-space-Landschaft genauer ansehen.
Eine Landschaft hat beide
(i) Ort (definiert durch state ) und
(ii) Elevation (definiert durch den Wert der heuristischen Funktion oder Zielfunktion )
Wir müssen die zwei Arten von Erhebungen verstehen ,
(i) Wenn die Höhe einer Zielfunktion entspricht, ist es das Ziel, den höchsten Gipfel zu finden, dh a Global Maximum .
(Diese Art von Elevation ist also in verschiedenen Szenarien nützlich, die sich nicht mit Kosten befassen und nur die besten Sofortbewegungen suchen)
(ii) Wenn die Höhe den Kosten entspricht , dann besteht das Ziel darin, das niedrigste Tal zu finden, d. h. ein globales Minimum .
( Hier ist das Gemeinsame dh Steepest (immer mit besseren Schätzungen, also ohne Plateau-Problem oder andere). Hill Climbing ist vergleichbar mit Best First Search. Hier ist die Elevation-Funktion die heuristische Funktion , die die besten Mindestkosten liefert und Hill Climbing hier nur den aktuellen Knoten betrifft und für minimalen Wert durch die benachbarten Knoten iteriert und fährt mit der Erweiterung des besten Knotens fort, der Best First Search ähnlich ist )
Hinweis :
Hill Climbing-Algorithmus blickt nicht über die unmittelbaren Nachbarn des aktuellen Status hinaus . Es geht nur um den besten Nachbarknoten, den es zu erweitern gilt. Und das beste Nachbar wird durch die obigen Auswertungsfunktionen entschieden.
Während der beste Algorithmus für die erste Suche vor den unmittelbaren Nachbarn sucht , um den besten Pfad zum Ziel zu finden (mit heuristischer Auswertung) und dann mit dem besten voranzukommen. Der Unterschied liegt also im Ansatz der lokalen Suche und der systematischen Suchalgorithmen.
Verstehen Sie den Unterschied in den Ansätzen, Sie werden erfahren, warum beide anders benannt sind.