路径寻找算法:A*Vs跳转点搜索

Question

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

Answer 1

跳转点搜索是基于图形上某些条件的改进的A *。因此，如果满足这些条件（大多数情况下是统一成本网格），则JPS绝对优于A *（相同的最优性，最佳情况可能会好几个数量级，而最差情况可能是相同的复杂度，但常数会稍差一些），但如果不符合条件，则无法使用。

基本上，JPS相对于A *的改进是，如果您有一个具有统一成本函数的图形（从A到B以及从B到C，朝相同方向的成本相同），则可以跳过某些步骤并直接从A转到C，而无需扩展B中的节点。

JPS是对A *的修剪技术，您删除了不需要评估的案例，因为您知道它们将不是最佳的。您知道这是由于统一成本网格条件。
从概念上讲，这等效于在非均匀网格上使用A *，其中相邻节点表示您可以在不遇到障碍的情况下朝该方向走多远，并且花费了执行的跳转费用。因此，如果您可以在右侧遇到10个节点而不会遇到障碍，则可以将其减少（或直接跳转到）成本为10 * c的单个节点，其中c是从一个节点到节点的（恒定）成本。另一个在右边。

原始文件可以在这里找到。