Warum Dijkstra Algorithmus statt der Besten (Billigsten) Zuerst Suche?

Von dem, was ich bisher gelesen habe. Die Best First Search scheint schneller in Hinblick auf die Suche nach dem kürzesten Weg zum Ziel, weil der Dijkstra-Algorithmus hat zu entspannen, werden alle Knoten, die bei der übertragung der Grafik. Was macht der Dijkstra-Algorithmus besser als Best First Search?

  • Ich bin mir ziemlich sicher, dass die B-in BFS steht für "Breite". Ich bearbeitet die Frage entsprechend.
  • Ich glaube, BFS ist langsamer, in vielen Szenarien. Wenn die Leistung wichtig, es kann die Genauigkeit herabgestuft werden, um zu Gunsten der Leistung.
  • ist es schwer, einen Kommentar zu hinterlassen und lassen Sie mich es richtig?
InformationsquelleAutor Alexander Suraphel | 2012-04-29
  1. 30

    BEARBEITEN: Dein edit klärt Sie daran interessiert sind Best-First-Suche, und nicht BFS.

    Best-First-Suche ist eigentlich ein informierter Algorithmus erweitert, die den vielversprechendsten Knoten zuerst. Sehr ähnlich zu den bekannten A* - Algorithmus (eigentlich Eine* ist eine spezifische best-first-search-Algorithmus).

    Dijkstra ist uninformiert-Algorithmus - es sollte verwendet werden, wenn Sie keine Kenntnisse auf dem Graphen, und nicht schätzen Sie den Abstand von jedem Knoten zum Ziel.

    Beachten Sie, dass A* (was ist ein s best-first-search) zerfällt in Dijkstra ' s Algorithmus, wenn Sie heuristische Funktion h(v) = 0 für jeden v.

    Darüber hinaus Best-First-Suche ist nicht optimal [nicht garantiert den kürzesten Weg zu finden] und auch Ein*, wenn Sie nicht verwenden eine zulässige heuristische Funktion, während der Dijkstra-Algorithmus ist immer optimal, da es nicht relais auf jede Heuristik.

    Abschluss: Best-First-Suche ist bevorzugt über dijkstra, wenn Sie einige Kenntnisse auf dem Graphen, und kann schätzen die Entfernung zum Ziel. Wenn Sie nicht - eine uninformierte Best-First-Suche, die verwendet h(v) = 0 und relais nur auf bereits erkundeten Ecken, zerfällt in Dijkstra ' s Algorithmus.

    Auch, wenn Optimalität ist wichtig - der Dijkstra-Algorithmus immer die Passform, während ein best-first-search-Algorithmus (A* speziell) können nur verwendet werden, wenn eine geeignete Heuristik-Funktion verfügbar ist.

    Original-Antwort - beantworten warum wählte Dijkstra über BFS:

    BFS schlägt fehl, wenn es um gewichtete Graphen.

    Beispiel:

         A
   /  \
  1     5
 /      \
B----1----C

    Hier: w(A,B) = w(B,C) = 1, w(A,C) = 5.

    BFS von Einem zurück A->C als der kürzeste Weg, aber für die gewichtete Graphen, es ist ein Weg der Stärke 5!!! während der kürzeste Weg ist von Gewicht 2: A->B->C.

    Dijkstra-Algorithmus wird nicht machen diesen Fehler, und die kürzesten gewichteten Weg.

    , Wenn Ihr graph unbewertet - ist das BFS sowohl die optimale und vollständige - und sollte in der Regel bevorzugt über dijkstra - weil es einfacher und schneller (zumindest asymptotisch gesehen).

    • Meinst du die Breite der ersten Suche nicht die billigste, zuerst durch das BFS?
    • Ihre ursprüngliche Frage nicht klar war (mir zumindest), ich dachte du meintest das BFS. Blick auf die edit - nicht, dass die Antwort auf Ihre Frage? Ich halte das original für zukünftige Leser, wie gut, vielleicht wird jemand es nützlich finden.
    • seit Ihrer ursprünglichen Antwort war eine Reaktion auf eine "fehlgeleitete" Bearbeiten von @dmeister (wer sollte lernen google, bevor korrigiert wird, andere Leute Fragen) ich denke, es wäre besser gelöscht. es ist nicht an der Frage und nur hilft verewigen die Verwirrung von dmeister-Fehler.
    InformationsquelleAutor amit
  2. 1

    Normalerweise Best First Search algorithmen im Pfad zu finden, auf der Suche nach Pfad zwischen zwei gegebenen Knoten: Quelle und Waschbecken, aber der Dijkstra-Algorithmus findet den Weg zwischen der Quelle und allen anderen Knoten. So kann man nicht vergleichen. Auch Dijkstra selbst ist eine Art Best First Search (variation von*) bedeutet, Sie können nicht sagen, es ist nicht Best First-Suche. Auch normale Beste First-Search-Algorithmen mit Heuristiken und Sie sind keine Garantie über die Richtigkeit, Schließlich im gewichteten Fall normalerweise Ihre Laufzeit hängt davon ab, gewichten, aber der Dijkstra-Algorithmus nur davon abhängen, Grafik Größe.

    InformationsquelleAutor Saeed Amiri
  3. 0

    BFS ist gut für die Suche nach kürzesten Weg von der Quelle zu einem Eckpunkt, bei denen alle Kanten dasselbe Gewicht, D. H. zu finden, mindestens keine der Kanten von der Quelle zu einem Eckpunkt.
    Während Dikjstra gilt für gewichtete Graphen

    InformationsquelleAutor user3741829
Schreibe einen Kommentar