algorithm - 寻路算法 : A* Vs Jump Point Search

Question

我知道 A* 比 Dijkstra 算法更好，因为它考虑了启发式值，但是从 A* 和跳点搜索来看，在有障碍的环境中寻找最短路径的最有效算法是什么？有什么区别？

Answer 1

Jump Point Search 是基于图上的某些条件改进的 A*。因此，如果你满足这些条件(主要是统一成本网格)，JPS 严格优于 A*(相同的最优性，最好的情况可以好几个数量级，最坏的情况可能是相同的复杂性，但 稍微差一点的常量)，但如果不满足条件，则不能使用。

JPS 相对于 A* 的改进基本上是，如果你有一个具有统一成本函数的图(从 A 到 B 和从 B 到 C 的成本相同，方向相同)，你可以跳过一些在某些情况下，直接从 A 到 C，而不扩展 B 中的节点。

JPS 是一种基于 A* 的修剪技术，您可以删除不需要评估的案例，因为您知道它们将是次优的。你知道这一点是因为统一成本网格条件。
从概念上讲，这等同于在非均匀网格上使用 A*，其中相邻节点表示您在该方向上可以走多远而不会遇到障碍，以及您执行的跳跃成本。因此，如果您可以在不遇到障碍的情况下向右走 10 个节点，则可以将此(或直接跳转到)成本降低为 10*c 的单个节点，其中 c 是从一个节点到的(恒定)成本另一个在右边。

原论文可见here.