Unterscheidet sich Greedy am besten von der ersten Suche?

Eine terminologische Frage - ist Greedy best-first Suche verschiedene Best-first search?

Den wiki-Seite hat einen separaten Absatz über Gierig BFS aber es ist ein wenig unklar.

Mein Verständnis ist, dass Greedy BFS gerade BFS, wo die "besten Knoten aus OPEN" in der wikipedia-Algorithmus ist eine Heuristik-Funktion berechnet für einen Knoten. Damit die Umsetzung dieser:

OPEN = [initial state]
CLOSED = []
while OPEN is not empty
do
 1. Remove the best node from OPEN, call it n, add it to CLOSED.
 2. If n is the goal state, backtrace path to n (through recorded parents) and return path.
 3. Create n's successors.
 4. For each successor do:
   a. If it is not in CLOSED: evaluate it, add it to OPEN, and record its parent.
   b. Otherwise: change recorded parent if this new path is better than previous one.
done

mit "besten Knoten aus OPEN, das eine heuristische Funktion, die Schätzung, wie nahe sich der Knoten an das Ziel, ist tatsächlich Gierig BFS. Bin ich im Recht?

EDIT: Kommentar auf Anonymouse Antwort:

Also im wesentlichen eine gierige BFS nicht brauchen eine "OFFENE Liste" und sollte als Grundlage für Ihre Entscheidungen nur auf den aktuellen Knoten? Ist dieser Algorithmus GBFS:

1. Set START as CURRENT node
2. Add CURRENT to Path [and optinally, to CLOSED?]
3. If CURRENT is GOAL, exit
4. Evaluate CURRENT's successors
5. Set BEST successor as CURRENT and go to 2.

InformationsquelleAutor der Frage Alex | 2011-12-04

  1. 22

    "Best first" ermöglichen könnte überarbeitung die Entscheidung, in der Erwägung, dass in ein greedy-Algorithmus, sollte die Entscheidung endgültig ist und nicht revidiert.

    Z.B. A*-Suche best-first-Suche, aber er ist nicht geizig.

    Verstehen, dass, allerdings werden diese Begriffe nicht immer mit den gleichen Definitionen. "Gierig" bedeutet in der Regel, dass die Entscheidung noch nie revidiert, schließlich akzeptieren suboptimale Lösungen auf den nutzen von Verbesserungen in der Laufzeit. Allerdings, ich Wette, Sie finden Situationen, in denen "gierige" ist für die Kombination von "best first + Tiefe zuerst" in "versuchen Sie, erweitern Sie den besten nächsten Schritt, bis wir auf eine Sackgasse, kehren Sie dann zum vorherigen Schritt und fahren Sie mit dem nächsten besten" (was ich nennen würde ein "priorisiert" Tiefe zuerst").

    Auch es hängt davon ab, auf welcher Ebene der Abstraktion Sie reden. A* ist nicht gierig in "building a path". Es ist in Ordnung zu halten, eine große Gruppe offener Pfade um. Es ist jedoch gierig in "erweitert den Suchraum" für die wahre kürzesten Weg.

    InformationsquelleAutor der Antwort Anony-Mousse

  2. 1

    BFS ist eine Instanz von Baum Suche und graph search algorithmen, in dem ein Knoten ausgewählt, für den ausbau basiert auf einem Bewertungsfunktion f(n).

    Traditionell, wird der Knoten mit der geringsten Bewertung ausgewählt ist, für den ausbau, weil die Bewertung misst den Abstand zum Ziel.

    BFS verwendet eine priority queue.

    Gierig BFS versucht, erweitern Sie den Knoten, der am nächsten am Ziel, auf dem Boden, diese führen zu den Lösung schnell. So wertet Knoten, die nur mit der heuristische Funktion f(n) = h(n).

    InformationsquelleAutor der Antwort Hina Alvi

  3. 0

    Es ist mein Verständnis, Best-first-Suche ist nur eine Sammelbezeichnung für eine bestimmte Suche Technik, in denen Sie eine heuristische evaluation-Funktion h(n).
    Also A* und Greedy Best-first Suche auch in diese Kategorie fallen.

    Bitte korrigieren Sie mich, wenn ich falsch bin!

    InformationsquelleAutor der Antwort Dominik Antal

Schreibe einen Kommentar