路徑查找算法：A * Vs跳轉點搜索

Question

我知道A *比Dijkstra的算法更好，因爲它考慮了啓發式值，但是從A *和跳轉點搜索這是找到最短路徑的最有效算法在有障礙的環境中？有什麼區別？

Answer 1

跳點搜索是基於圖上某些條件的改進的A *。因此，如果你滿足這些條件（主要是統一成本電網），JPS嚴格優於A *（相同的最優性，最好的情況可以是更好的數量級，更糟糕的情況可能具有相同的複雜性，但是具有稍差的常數） ，但如果你不符合條件，你就不能使用它。

JPS超過A *的改進基本上是，如果你有一個均勻的成本函數（它的成本從A轉到B和從B到C相同的，以相同的方向）的曲線圖，可以跳過某些步驟在某些情況下直接從A到C而不擴展B中的節點。

JPS是A *上的修剪技術，您可以移除不需要評估的案例，因爲您知道它們將不是最優的。你知道這是因爲統一成本的網格條件。
從概念上講，這相當於在非均勻網格上使用A *，其中相鄰節點表示在沒有遇到障礙的情況下您可以沿該方向行進多遠，並執行跳躍代價。因此，如果您可以在沒有遇到障礙的情況下前往10個節點，則可以以10 * c爲代價減少（或直接跳轉到）單個節點，其中c是從一個節點到另一個在右邊。

原文可以找到here.