1. Zuhause
  2. Frage und Antwort
  3. Bidirektional A * (A-Stern) Suche

Bidirektional A * (A-Stern) Suche

2010-09-04 16 views
19

Ich implementiere eine bidirektionale A * -Suche (bidirektional wie in der Suche wird sowohl vom Ursprung als auch vom Ziel gleichzeitig durchgeführt, und wenn diese beiden Suchen zusammentreffen, habe ich meine kürzeste Pfad - zumindest mit ein wenig extra Logik hineingeworfen).Bidirektional A * (A-Stern) Suche

Hat jemand Erfahrung mit einer unidirektionalen A * und bidirektionalen (!) Es - welche Art von Performance-Gewinn kann ich erwarten? Ich hätte damit gerechnet, dass die Suchzeit mehr oder weniger halbiert wird - aber kann ich größere Gewinne sehen? Ich benutze den Algorithmus, um kürzeste Routen auf einem Straßennetz zu bestimmen - wenn das irgendwie relevant ist (ich habe über den "Reach" -Algorithmus von MS gelesen, möchte aber Babyschritte dazu machen, anstatt direkt hineinzuspringen).

Quelle

2010-09-04 Will A

+0

Hinweis - Der Titel der Frage wird in Wortform A * wiederholt, um die Suche zu erleichtern. –

+1

FYI: Hier ist ein Link zum MS-Papier auf Reach for A * (A-Stern): http://www.avglab.com/andrew/pub/alenex06.pdf – shindigo

Antwort

8

Im bestmöglichen Fall es in O (b^(n/2)) anstelle von O (b^n) laufen würde, aber das ist nur, wenn Sie Glück haben :)

(wobei b ist Ihr Verzweigungsfaktor und n ist die Anzahl der Knoten, die ein unidirektionales A * in Betracht ziehen würde)

Es hängt alles davon ab, wie leicht die beiden Suchvorgänge zusammentreffen, wenn sie sich zu einem guten Zeitpunkt auf der Suche früh finden mit viel Suchzeit erledigt, aber wenn sie in sehr unterschiedliche Richtungen verzweigen, können Sie etwas langsamer als einfach A * (wegen der zusätzlichen Buchhaltung)

Quelle

2010-09-04 10:49:23

+1

Dank Michael - einige zusätzliche Forschung hat gezeigt, dass ich Es ist unwahrscheinlich, dass man Glück hat - bidirektionales A * ist angeblich ziemlich umständlich, wenn es darum geht, dass beide Richtungen auf denselben Knoten konvergieren. Ich kann es versuchen oder wahrscheinlicher etwas Zeit investieren, um Reach herauszufinden. –

+0

Bei größeren Zahlen gewinnen Sie klar, wenn Sie bidirektionale Suche durchführen. Microsoft Research Labs verwenden diesen Algorithmus, aber mit einer Menge komplizierterer Verbesserungen. –

1

Sie können w Ameise, um zu versuchen http://sourceforge.net/projects/tway/ ein Benchmarking-Skript, das diese mit Standard astar vergleicht (für NY Datenstadtstraßen scheint es eine 30% ige Zeitvorteil zu geben)

Quelle

2012-09-04 14:20:56 SRC

1

implementiert 3 verschiedene bidirektionale A * Suche algos (siehe cskit) .

  • net.coderodde.cskit.graph.p2psp.general.FastSuboptimalFinder ist die schnellste, aber nicht generell optimal;
  • net.coderodde.cskit.graph.p2psp.general.BHPAFinder ist optimal und ziemlich schnell; Wenn Optimalität eine Voraussetzung ist, würde ich diese verwenden;
  • net.coderodde.cskit.graph.p2psp.general.WhangboFinder nicht besonders gut.

    • Um die Algorithmen in Aktion zu sehen, vom Projektstammtyp (erfordert Maven). Viel Glück!

    (bearbeiten. This library bietet 3 verschiedene bidirektionale A * Algorithmen Alle drei sind optimal.)

    Quelle

    2014-03-16 09:47:32 coderodde

    Verwandte Themen

     Verwandte Themen