Pfadsuche Algorithmen: A * Vs Jump Point Suche

Question

Ich weiß, dass A * ist besser als Dijkstra-Algorithmus, weil es heuristische Werte berücksichtigt, aber von A * und Jump Point Suche, die den effizientesten Algorithmus für die Suche nach dem kürzesten Weg ist in einer Umgebung mit Hindernissen? und was sind die Unterschiede?

Answer 1

Die Jump Point-Suche ist ein verbessertes A * basierend auf einigen Bedingungen in der Grafik. Wenn Sie also diese Bedingungen erfüllen (meist Kostengitternetz), ist JPS strikt besser als A * (gleiche Optimalität, beste Fälle können größenordnungsmäßig besser sein und schlimmer ist wahrscheinlich die gleiche Komplexität, aber mit eine etwas schlechtere Konstante) , aber wenn Sie die Bedingungen nicht erfüllen, können Sie es nicht verwenden.

Die Verbesserungen von JPS gegenüber A * ist grundsätzlich, wenn Sie ein Diagramm mit einer einheitlichen Kostenfunktion haben (es kostet dasselbe von A nach B und von B nach C, in die gleiche Richtung), können Sie überspringen einige Schritte in einigen Fällen und direkt von A nach C gehen, ohne Knoten in B zu erweitern.

JPS ist eine Beschneidungstechnik über A *, Sie entfernen Fälle, die Sie nicht bewerten müssen, weil Sie wissen, dass sie suboptimal sind . Sie wissen das wegen der gleichmäßigen Kosten-Netz-Bedingung.
Vom Konzept her entspricht dies der Verwendung von A * über ein ungleichmäßiges Gitter, wobei benachbarte Knoten darstellen, wie weit man in diese Richtung gehen kann, ohne auf ein Hindernis zu stoßen, mit den Kosten des durchgeführten Sprungs. Wenn Sie also 10 Knoten auf der rechten Seite gehen können, ohne auf ein Hindernis zu stoßen, können Sie dies auf einen einzelnen Knoten mit einem Aufwand von 10 * c reduzieren (oder direkt zu ihm springen), wobei c die (konstanten) Kosten von einem Knoten zu ein anderer auf der rechten Seite.

Das ursprüngliche Papier kann here.