我知道A *比Dijkstra的算法更好，因为它考虑了启发式值，但是从A *和Jump Point搜索这是在有障碍的环境中找到最短路径的最有效算法？有什么区别？
跳转点搜索是基于图表上某些条件的改进A * . 因此，如果你满足这些条件（主要是统一成本网格），JPS严格优于A *（相同的最优性，最佳情况可以是更好的数量级，更糟糕的情况可能是相同的复杂性，但具有稍差的常数），但如果你不符合条件，就不能使用它 .
一些JPS优于A *的改进基本上是，如果你有一个具有统一成本函数的图形（从A到B以及从B到C，在同一方向上的成本相同），你可以跳过一些步骤在不扩展B节点的情况下，直接从A转到C
JPS是一种超过A *的修剪技术，你删除了你不需要评估的案例，因为你知道它们将是次优的 . 你知道这是因为统一成本网格条件 .从概念上讲，这相当于在非均匀网格上使用A *，其中相邻节点表示在不遇到障碍物的情况下可以在该方向上移动多远，并且执行跳跃的成本 . 因此，如果您可以在不遇到障碍物的情况下向右移动10个节点，则可以将此值（或直接跳转到）单个节点降低10 * c，其中c是从一个节点到另一个节点的（常量）成本另一个在右边 .
可以找到原始论文here.
1 回答
跳转点搜索是基于图表上某些条件的改进A * . 因此，如果你满足这些条件（主要是统一成本网格），JPS严格优于A *（相同的最优性，最佳情况可以是更好的数量级，更糟糕的情况可能是相同的复杂性，但具有稍差的常数），但如果你不符合条件，就不能使用它 .
一些JPS优于A *的改进基本上是，如果你有一个具有统一成本函数的图形（从A到B以及从B到C，在同一方向上的成本相同），你可以跳过一些步骤在不扩展B节点的情况下，直接从A转到C
JPS是一种超过A *的修剪技术，你删除了你不需要评估的案例，因为你知道它们将是次优的 . 你知道这是因为统一成本网格条件 .
从概念上讲，这相当于在非均匀网格上使用A *，其中相邻节点表示在不遇到障碍物的情况下可以在该方向上移动多远，并且执行跳跃的成本 . 因此，如果您可以在不遇到障碍物的情况下向右移动10个节点，则可以将此值（或直接跳转到）单个节点降低10 * c，其中c是从一个节点到另一个节点的（常量）成本另一个在右边 .
可以找到原始论文here.