我知道A*算法比Dijkstra算法更好，因为它考虑了启发式值，但在有障碍物的环境中，A*算法和Jump Point搜索算法哪个是寻找最短路径最有效的算法？它们之间有什么区别？
1个回答
7
Jump Point Search是基于图形条件的改进A*算法。因此，如果您满足这些条件（大多数情况下是均匀成本网格），JPS比A*严格更好（相同的最优性，最佳情况可以提高数量级，最坏情况可能具有相同的复杂度但常数略差），但如果您不符合条件，则无法使用它。
JPS相对于A*的改进主要在于，如果您有一个具有均匀成本函数的图形（从A到B和从B到C的成本相同，方向相同），则在某些情况下，您可以跳过一些步骤，并直接从A到C而不扩展节点B中的节点。
JPS是A*的修剪技术，您可以删除不需要评估的情况，因为您知道它们将是次优的。由于均匀成本网格条件，您知道这一点。从概念上讲，这相当于在非均匀网格上使用A*，其中相邻节点表示您可以在该方向上走多远而不遇到障碍物，并带有您执行的跳跃成本。因此，如果您可以在右侧走10个节点而不遇到障碍物，则可以将其减少（或直接跳转到）一个成本为10*c的单个节点，其中c是从一个节点到另一个节点的（常数）成本。
JPS相对于A*的改进主要在于，如果您有一个具有均匀成本函数的图形（从A到B和从B到C的成本相同，方向相同），则在某些情况下，您可以跳过一些步骤，并直接从A到C而不扩展节点B中的节点。
JPS是A*的修剪技术，您可以删除不需要评估的情况，因为您知道它们将是次优的。由于均匀成本网格条件，您知道这一点。从概念上讲，这相当于在非均匀网格上使用A*，其中相邻节点表示您可以在该方向上走多远而不遇到障碍物，并带有您执行的跳跃成本。因此，如果您可以在右侧走10个节点而不遇到障碍物，则可以将其减少（或直接跳转到）一个成本为10*c的单个节点，其中c是从一个节点到另一个节点的（常数）成本。
原始论文可以在这里找到。
- Leherenn
1
@Thilan.L 你具体缺少什么？也许我可以更新我的答案以更好地回答你。 - Leherenn
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接