Boost Graph Library A *提供一致啓發式

Question

我讀到過，當將A *應用於問題時，如果啓發式是一致的，那麼您可以進一步優化A *搜索。 Boost圖庫提供了兩種版本的A *算法：astar_search和astar_search_tree。關於兩者之間的區別，文件不是很清楚;它們中的一個是否執行假設一致啓發式的優化搜索？

Answer 1

我通過諮詢Boost郵件列表得到了我正在尋找的答案。我將在這裏爲後代重現答案：

區別在於是否應該努力避免 多次訪問同一個頂點。對於經常通過多條路徑到達頂點的圖，您應該首選astar_search以避免重新訪問該頂點及其後繼者的額外工作。如果是 不太可能相同的頂點出現在多條路徑上，或者檢查頂點價格不夠便宜，以至於不值得避免重複的 工作，則使用astar_search_tree，它不記得它先前訪問過哪個頂點 。試圖找到重複頂點 的缺點是它需要越來越多的內存來存儲查找表 的頂點已經被查看過，並且花費時間搜索並更新此表。該算法的兩個版本都需要允許 啓發式才能正常工作。

Link to the thread

Answer 2

的_tree和非_tree提升圖形算法版本之間的不同之處在於_tree版本假設你的曲線真的是一棵樹，所以它沒有循環，只有一個箭頭節點。