我最近在我的一個尋路可視化器上實作了一顆星。我注意到的一個共同點是，雖然它確實回傳了最短路徑，但有時它無法回傳成本最低的路徑。現在我不確定這是否是由于某些實作錯誤，或者這是否不是整個演算法的特征。作為參考，這些分別是 a star 和 dijkstras 演算法的輸出：
那么，為什么會這樣呢？（PS：權重為 10，任何運動方向的正常成本為 1，灰色塊為墻壁）
uj5u.com熱心網友回復：
A* 是最優的。它總是回傳成本最低的路徑。但啟發式值必須是可接受的。
uj5u.com熱心網友回復：
A* 可能不會回傳成本最低的路徑，這是正確的。這是 A* 的一個特點，而不是缺點。要回答你的問題，
為什么會這樣？
A* 具有啟發式功能，允許演算法通過顯著減少搜索區域來犧牲準確性以獲得更高的性能。這也可以在您的影像中看到，其中 Dijkstra 的搜索范圍要廣泛得多。A* 在實時游戲中通常更有用，您不一定需要最低成本的路徑，只要它“足夠好”即可。有關更多示例，請參閱本文。我發現它用簡單的語言非常清楚地解釋了 A*。
至于什么是“足夠好”，您可以使用啟發式函式來定義它。使用不同的函式將導致不同的行為，允許您調整演算法以使其最適合您的需求（取決于您的比賽場地和準確性要求）。您還可以洗掉啟發式，在這種情況下，它變成了簡單的 Dijkstra 演算法。有關啟發式方法的一些示例，請參閱同一站點的這篇文章。
uj5u.com熱心網友回復：
A* 給出正確的結果，前提是啟發式給出了真實成本的下限。每個可能的路徑必須具有高于或等于啟發式提供的值的成本。如果您使用總是給出值 0 的簡單啟發式演算法，則該演算法與 Dijkstra 的演算法相同。
uj5u.com熱心網友回復：
添加Md Asaduzzaman和Henry的正確答案：
如果啟發式函式是可接受的，那么 A* 樹搜索將始終找到成本最低的路徑。
（來源）
可接受的啟發式是樂觀的：啟發式成本應該小于或等于實際成本。
換句話說，如果您的實作沒有回傳最低成本路徑，請考慮將啟發式方法更改為可接受的方法。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/464878.html