A *尋路 - 更新父

Question

我讀過A* Pathfinding for Beginners並查看了C++和其他語言中的幾個源代碼實現。我理解大部分發生的事情，除了我認爲我已經發現的一個可能的問題，並且我發現的教程/實現中沒有一個涵蓋了這一點。

當你到達這一部分：

如果相鄰的廣場已經開行了[...]，如果G值的新路徑 較低，改變的父相鄰的廣場以 選定的廣場。最後，重新計算那個正方形的F和G分數 。

更改正方形的G分數也會改變每個孩子的G分數，對嗎？也就是說，每個已經有這個方格作爲父母的方格，現在也應該得到一個新的G分數。那麼，您不應該在公開列表中找到每個孩子（和孩子的孩子）並重新計算G值嗎？這也會改變F值，所以如果使用排序列表/隊列，這也意味着一堆訴諸。

這是不是一個實際的問題，不值得爲額外的計算額外的CPU，這就是爲什麼我看到的實現只是忽略這個問題（不更新兒童）？

Answer 1

這取決於你的啓發式。

爲了正確，基本的A *算法要求您有一個admissible heuristic，也就是說，永遠不會高估從節點移動到目標的最低成本。然而，使用可容許的啓發式搜索可能並不總能找到沿途中間節點的最短路徑。如果啓發式的情況就是這種情況，那麼稍後可能會找到一條到達已經訪問的節點的較短路徑，並且需要再次展開該節點的子節點。在這種情況下，您不應該使用封閉式列表，因爲如果您不斷找到較短的路線，則需要多次重新訪問節點。但是，如果您使用consistent heuristic（意思是一個節點的估計成本永遠不會超過其鄰居之一的估計成本，再加上從該節點移動到該鄰居的成本），那麼您將只能以最短路徑訪問節點。這意味着您可以使用封閉列表，並且在展開子節點後永遠不會重新訪問節點。

所有一致的啓發式都是可以接受的，但並非所有可接受的啓發式都是一致的。儘管大多數可接受的啓發式方法也是一致的，所以您經常會看到A *的描述和示例代碼，假設啓發式是一致的，即使它沒有明確說明（或者只提到可接受性）。

在您鏈接到的頁面上，該算法使用封閉列表，因此需要一致的啓發式以保證找到最佳路徑。然而，考慮到它處理對角線移動的方式，它使用的啓發式算法（曼哈頓距離）並不一致（或者對此而言是可接受的）。因此，雖然它可能找到最短路徑，但它也可能找到其他路徑，並錯誤地認爲它是最短路徑。比較合適的啓發式（例如歐幾里德距離）既可以接受也可以一致，你肯定不會遇到麻煩。