Wie funktioniert der Jump Point Search-Algorithmus und warum ist er so effizient?

8

Beim Ausprobieren des folgenden Applets habe ich festgestellt, dass dieser Pfadfindungsalgorithmus namens Sprungpunktsuche ein deutlich schnelleres Ergebnis liefert als A * und Dijkstra.

http://qiao.github.io/PathFinding.js/visual/

A *: 46 Sekunden Geben Sie hier die Bildbeschreibung ein

Dijkstra: 1 Minute 39 Sekunden Geben Sie hier die Bildbeschreibung ein

Sprungpunktsuche: Weniger als 3 Sekunden Geben Sie hier die Bildbeschreibung ein

Unnötig zu sagen, ich bin ziemlich erstaunt über das Ergebnis. Aufgrund der visuellen Darstellung scheint die Sprungpunktsuche viele zufällige (wahrscheinlich sehr intelligente) Vermutungen anzustellen, um den Pfad zu finden (zumindest aus der Blockauswahl), aber ich habe noch keinen Testfall gefunden, bei dem dieser Algorithmus schlechter ausfiel Ergebnisse als A * und Dijkstra.

Wie funktioniert dieser Algorithmus? Wie ist es im Vergleich zu A * und Dijkstra so effizient?

algorithms l46kok
quelle
2
Aus Ihren Screenshots geht hervor, dass A * 7 ms (nicht 46 s), Dijkstra 13 ms (nicht 1 m 39 s) und JPS 2 ms (nicht 3 s) benötigt hat. Woher hast du deine Nummern?
Yannis
Durch manuelles Timing mit einem Timer. Menschliche Fehler deuten möglicherweise darauf hin, dass ich um einige Sekunden oder länger ausgeschaltet bin, aber es dauert auf keinen Fall so lange wie im Applet angegeben. Vielleicht bezieht es sich auf etwas anderes oder es ist ein Fehler.
l46kok
7
Oh mein Gott, hast du das wirklich getan? Die Zeiten, zu denen die Toolberichte korrekt sind: So lange hat es gedauert, bis jeder Algorithmus abgeschlossen war. Die (signifikante) Verzögerung danach dient zur Darstellung der Pfade der Algorithmen. SVG-Animation ist eines der coolsten Dinge in HTML5, aber es ist (immer noch) langsam .
Yannis
@YannisRizos Dang, ich hätte es besser
wissen
1
Es ist langsam, um den Fortschritt des Algorithmus anzuzeigen, nicht weil zB "HTML5 ist langsam" usw.
Steven Lu

Antworten:

5

Die Grundidee ist, dass JPS es ermöglicht, viele Kandidatenpfade frühzeitig wegzuwerfen, wodurch der Rechenaufwand reduziert wird.

In vielen Karten führen mehrere Pfade mit denselben Kosten zu demselben Ziel, z. B. eine Spielkarte mit großen offenen Flächen. JSP ermöglicht das Bereinigen dieser Pfade.

Eine ausführliche Erklärung finden Sie hier .

Wilbert
quelle
1

Mit der neuesten Version des Tools wird JPS für viele Diagrammtypen tatsächlich als langsamer als A * angezeigt, da sie jetzt auch die JPS-Rekursion anzeigen.

JPS-Suche Graue Knoten sind untersuchte Knoten

Dies gilt auch in der realen Welt; Während JPS normalerweise weit weniger Knoten in die Warteschlange stellt, werden normalerweise viel mehr Knoten untersucht . Ob dies zu einer tatsächlichen Beschleunigung führt, hängt von der Grafik ab.

BlueRaja - Danny Pflughoeft
quelle