我知道 A* 比 Dijkstra 算法更好，因为它考虑了启发式值，但是从 A* 和跳跃点搜索来看，哪种算法是在有障碍物的环境中找到最短路径的最有效算法？有何不同？
跳跃点搜索是基于图表上的某些条件的改进的 A*。因此，如果满足这些条件（主要是统一成本网格），JPS 严格优于 A*（相同的最优性，最好的情况可以好几个数量级，最坏的情况可能具有相同的复杂性，但具有
稍微差一点的常数），但是如果不满足条件，就不能使用它。
JPS相对于A*的改进基本上是，如果你有一个具有统一成本函数的图（从A到B和从B到C的成本相同，方向相同），你可以在某些方面跳过一些步骤情况下，直接从A到C，而不扩展B中的节点。
JPS 是一种针对 A* 的修剪技术，您可以删除不需要评估的情况，因为您知道它们不是最优的。您知道这一点是因为统一成本网格条件。
从概念上讲，这相当于在非均匀网格上使用 A*，其中相邻节点表示在不遇到障碍的情况下您可以沿该方向走多远，以及执行跳跃的成本。因此，如果您可以在没有遇到障碍物的情况下向右移动 10 个节点，则可以以 10*c 的成本减少（或直接跳转到）单个节点，其中 c 是从一个节点到另一个在右边。
原论文可以找到here. http://users.cecs.anu.edu.au/~dharabor/data/papers/harabor-grastien-aaai11.pdf
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
