雙向搜尋
![本頁使用了標題或全文手工轉換](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
圖與樹 搜尋演算法 |
---|
分類 |
相關主題 |
雙向搜尋演算法是一種圖的遍歷演算法,用於在有向圖中搜尋從一個頂點到另一個頂點的最短路徑。演算法同時執行兩個搜尋:一個從初始狀態正向搜尋,另一個從目標狀態反向搜尋,當兩者在中間匯合時搜尋停止。在很多情況下該演算法更快,假設搜尋一棵分支因子b的樹,初始節點到目標節點的距離為d,該演算法的正向和反向搜尋複雜度都是O(bd/2) (大O符號),兩者相加後遠遠小於普通的單項搜尋演算法(複雜度為O(bd))。
在A*搜尋演算法中,雙向搜尋的啟發式函式可以定義為:正向搜尋為到目標節點的距離,反向搜尋為到初始節點的距離。
Ira Pohl (1971)第一個設計並實現了雙向啟發式搜尋演算法。Andrew Goldberg和其他人解釋了雙向搜尋版的戴克斯特拉演算法的正確完結條件。[1]
參考
- ^ Efficient Point-to-Point Shortest Path Algorithms (PDF). [2018-07-04]. (原始內容存檔 (PDF)於2018-06-18).
- de Champeaux, Dennis; Sint, Lenie, An improved bidirectional heuristic search algorithm, ACM期刊, 1977, 24 (2): 177–191, doi:10.1145/322003.322004.
- de Champeaux, Dennis, Bidirectional heuristic search again, ACM期刊, 1983, 30 (1): 22–32, doi:10.1145/322358.322360.
- Pohl, Ira, Bi-directional Search, Meltzer, Bernard; Michie, Donald (編), Machine Intelligence 6, Edinburgh University Press: 127–140, 1971.
- Russell, Stuart J.; Norvig, Peter, 3.4 Uninformed search strategies, Artificial Intelligence: A Modern Approach 2nd, Prentice Hall, 2002.