Was ist der Unterschied zwischen Hill-Climbing-Suche und am Besten Zuerst Suchen?

Ich versuche zu lernen, einige suchen Konzepte, sondern lief in eine Wand ein in den Prozess. Kann jemand mir erklären, was der Unterschied zwischen hill-climbing-Suche und am besten zuerst suchen? Zu mir, Sie sehen beide wie den ausbau der Knoten mit der heuristische Wert am nächsten zum Ziel. Wenn jemand erklären kann, der Unterschied für mich, es würde sehr geschätzt werden. Danke!

  • haben Sie versucht, die wiki? Was findest du?
  • Tat ich, aber ich bin immer noch verwirrt an dem Punkt, den ausbau der Knoten mit dem besten heuristischen Wert. mir scheint es beide algorithmen erweitern Sie den Knoten mit dem besten heuristischen Wert
InformationsquelleAutor freddy | 2011-05-27
  1. 11

    Können Sie die Ansicht Suche-Algorithmus mit einer Warteschlange von verbleibenden Knoten zu suchen. Diese Antwort veranschaulicht dieses Prinzip.

    In der Tiefe-zuerst-Suche, fügen Sie der aktuelle Knoten Kinder die vor von der Schlange (einem Stapel). In der Breite-zuerst-Suche, fügen Sie der aktuelle Knoten Kinder die zurück der Warteschlange. Denken Sie einen moment darüber, wie dieses führt, um das richtige Verhalten für diese algorithmen.

    Nun, in der hill-climbing-Suche, Sie sort[1] der aktuelle Knoten Kinder, bevor Sie Sie hinzufügen, um die Warteschlange. In best-first-Suche, die Sie hinzufügen, ist der aktuelle Knoten die Kinder von der Warteschlange in jedem alten Ordnung, dann sort[1] die gesamte Warteschlange. Wenn Sie denken über die Wirkung, die möglicherweise auf die Reihenfolge, in der die Knoten durchsucht werden, sollten Sie sich eine Vorstellung von der praktischen Unterschied.

    Ich fand dieses Konzept zu tangly zu verstehen, aus rein abstrakte Begriffe, aber wenn man Arbeit durch ein paar Beispiele mit einem Bleistift wird es einfach.

    [1]: Sortieren Sie nach einigen problem-spezifische Evaluierung der Lösung des Knotens, beispielsweise "Abstand vom Ziel" in einem Pfad zu finden-Suche.

    InformationsquelleAutor Brendan
  2. 4

    Einer vielleicht kurz zu spät, aber hier geht.

    BFS, es ist über die Suche nach dem Ziel. So ist es über die Kommissionierung die besten Knoten (die eine, die wir hoffen, wird uns an das Ziel) unter den möglichen. Wir halten Sie versuchen, zu gehen auf dem Weg zum Ziel.

    Aber in Hügel klettern, es geht um die Maximierung der Zielfunktion. Wir wählen die Knoten, welche die höchsten Aufstieg. Also im Gegensatz zu den BFS, den 'Wert' der übergeordnete Knoten ebenfalls berücksichtigt. Wenn wir nicht höher gehen wir einfach aufgeben. In diesem Fall können wir nicht einmal das Ziel erreichen. Wir könnte bei einem lokalen maxima.

    InformationsquelleAutor Jayanth Koushik
  3. 2

    Lassen Sie mich Wiki für Sie:

    In einfachen hill-climbing, das erste
    näher Knoten gewählt wird, in der Erwägung, dass in
    steilsten Aufstieg Hügel zu klettern
    Nachfolger werden verglichen und die
    am nächsten an der Lösung gewählt wird.

    ...

    Steilsten Aufstieg
    hill climbing "ist ähnlich zu" best-erste
    Suche, die versucht alle möglichen
    Erweiterungen des aktuellen Pfads statt
    nur einer.

    • was bedeutet es "versucht alle möglichen Erweiterungen der aktuelle Pfad?" geht es nicht nur erweitern Sie den Knoten mit dem besten heuristischen Wert?
    • Best-first-search berechnet den Wert ALLER benachbarten Knoten und iteriert dann mit den besten. Einfaches hill-climbing berechnet den Wert eines jeden benachbarten Knoten wiederum und wiederholt, sobald er eine findet, die besser als der aktuelle Knoten.
    InformationsquelleAutor Tom Shaw
  4. 0

    Den Unterschied liegt im Verständnis was ist mehr sorgen bei der Suche nach den Ziel Staat.

    Die Frage stellen, was ist unsere Ziel...
    die Endziel Zustand?
    oder die Beste Weg, um das Ziel zu erreichen Stand

    Den Best First Search ist eine systematische such-Algorithmus, bei dem systematicity wird erreicht, indem voran iterativ auf der Grundlage der Feststellung, die
    am besten heuristischen Wert     für die benachbarten Knoten für jeden aktuellen Knoten.

    Hier die Bewertungsfunktion ( heuristische Funktion ) berechnet die
    besten Weg, das Ziel zu erreichen Stand    . So konnten wir hier sehen, am Besten Erstmal suchen, ist besorgt über den besten WEG zum erreichen der Ziel-Zustand.

    Allerdings gibt es viele Probleme, wo "Weg zum Ziel" ist keine Sorge, die einzige Sache, die betroffen ist, ist zu erreichen den Endzustand die möglichen Wege oder Pfade.
    (ZB: 8-Damen-problem).

    Daher wird für diese local search algorithmen verwendet werden.

    Lokale-Suche-algorithmen arbeiten mit einer einzelnen aktuellen Knoten und in der Regel bewegen sich nur, um Nachbarn des Knotens.

    Hill Climbing Algorithmus ist ein lokale Suche Algorithmus.
    So müssen wir hier verstehen den Ansatz, die Ziel-Zustand nicht der beste Weg zu erreichen, wenn man über Hügel klettern.

    (Wie bereits in AI-A Modern Approach,SR & PN)

    Grundsätzlich zu verstehen, lokale Suche, müssen wir überlegen, state-space-Landschaft.

    Einen - Landschaft hat sowohl

    (i) Lage (definiert durch die Zustand) und

    (ii) Höhe (definiert durch die Wert der heuristischen Funktion oder Zielfunktion)

    Wir müssen verstehen, die zwei Arten von Erhebungen,

    (i) , Wenn die Höhe entspricht eine Zielfunktion,dann das Ziel ist, zu finden, die höchsten Gipfel d.h. ein Globales Maximum.

    (Also diese Art der Erhebung sind nützlich in verschiedenen Szenarien, die nichts mit der Kosten-und die sind nur noch beschäftigt mit der Suche nach den besten instant bewegt)

    (ii) , Wenn die Höhe entspricht Kosten, dann das Ziel ist, finden Sie die niedrigsten Tal D. H. ein Globales Minimum.

    (Hier ist die gemeinsame Sache d.h. Steilsten(immer verstärkt mit besseren Einschätzungen, d.h. keine plateau-problem oder jeder andere) hill climbing ist ähnlich wie Best-First-Suche. Hier die elevation Funktion ist die heuristische Funktion, die die besten minimalen Kosten. Und Hügel klettern hier nur um aktuellen Knoten und durchläuft die benachbarten Knoten für minimale Wert und Erträgen durch den ausbau von die besten Knoten, die ähnlich wie Best-First-Suche)

    Hinweis:

    Hill Climbing Algorithmus nicht nach vorne schauen über die unmittelbaren Nachbarn des aktuellen Zustands. Es ist nur die beste benachbarten Knoten zu erweitern.Und das beste benachbarten beschlossen, durch die die oben genannten Auswertungen Funktionen.

    In der Erwägung, dass, Best First Search Algorithmus - look-ahead-von den unmittelbaren Nachbarn finden Sie den besten Weg zum Ziel(mit Heuristischer Bewertung) und dann fortfahren mit den besten einen.
    So Unterschied liegt im Ansatz der lokalen Suche und die systematische Suche algorithmen.

    Verstehen, die unterschiedlichen Ansätze, erhalten Sie zu wissen, warum beide benannt sind anders.

    InformationsquelleAutor Reck
Schreibe einen Kommentar