有沒有一種方法來估計A *尋找路徑的進度？

在相當大的圖中找到最短路徑可能需要一段時間。很長一段時間甚至在某些情況下。根據我對the algorithm的瞭解，無法確切知道A *需要訪問多少個節點才能找到最短路徑，但是可能至少有一種方法可以用來估計它。有沒有一種方法來估計A *尋找路徑的進度？

這將給用戶提供至少近似的進度，但我想這很難做到。

2012-08-30 Joey

如果你有一個'完美的估計'（'h *'），你將不需要A * - 最好的首先會產生最佳結果。事實是，你的估計實際上取決於你的啓發式 - 它是更好的（更明智的） - 更好的近似值，而'h *'給出了完美的估計。 – amit

「大圖」是什麼意思？你可以在不到100ms內處理數百萬個節點，就像我用graphhopper完成的那樣。調試你的算法也是可能的：http://karussell.files.wordpress.com/2012/07/astar.gif – Karussell

使用迄今爲止所見的最小的EstimatedDistanceToEnd（即h(x)）將是一個估計值，但不一定是好的。

也許你應該看看你的算法ways of speeding up，或看看使用faster和/或approximate算法？

2012-08-30 17:44:09

我想這是目前的估計（至少目前的進展是在開始時進行大跳躍，然後攤檔90％左右）。但啓發式可能有點偏離，因爲它只考慮歐幾里得距離，而所有路徑的權重是不同的。尋找更好的啓發式方法可能也不容易;） – Joey

回答