尋路 - 跳轉點搜索 - 打開和關閉列表

我想製作一個高效的尋路算法，因此我進入了跳轉點搜索。我閱讀了關於它的出版物以及在線材料。它很好地解釋了這個過程，但是，我無法找到它應該如何與A *合併的材料。例如，我不確定該算法是否曾嘗試多次將同一個節點添加到打開列表中，因爲該算法應該消除相同長度的對稱路徑。我應該在添加新節點之前每次檢查一次，還是應該在打開的列表中添加每個跳躍點？尋路 - 跳轉點搜索 - 打開和關閉列表

所以簡而言之，我想知道如何處理跳轉點搜索算法中的打開和關閉列表。

來源

2013-08-30 PEC

由於JPS只適用於8連接網格圖，和8個連接網格圖有consistent heuristic（在Chebyshev或Euclidean距離，這取決於你的圖形），你不需要任何節點添加到打開列表不止一次。

來源

2013-08-30 16:11:07

我的問題不是我是否必須這樣做。在A *中，您必須檢查節點是否已經在關閉或打開的列表中。如果你不這樣做，它會多次添加一個節點。我問是否可以在這裏發生。 – PEC

@ user2154375：如果您使用的是不一致的啓發式，您可能必須多次將節點添加到打開的列表中。如果您擁有一致的啓發式，那麼您只需將節點添加到打開的列表中即可。 A \ *和JPS都是如此。 –

就像我說過的，在A *中，你必須檢查節點是否已經在列表中。如果是，則不添加它，但是如果新G值低於前一個值，則計算替代G值並將父項切換到最後一個封閉節點。我問f這在jps中是必要的。換句話說，算法可以從不同位置到達同一個節點嗎？如果是這樣，它可以嘗試多次聲明它是一個跳轉點，因此多次將其添加到打開列表中，這意味着打開/關閉列表檢查是必要的。 – PEC

尋路 - 跳轉點搜索 - 打開和關閉列表

回答

相關問題