雙向搜索

雙向搜索算法是一種圖的遍歷算法，用於在有向圖（英語：directed graph）中搜索從一個頂點到另一個頂點的最短路徑。算法同時運行兩個搜索：一個從初始狀態正向搜索，另一個從目標狀態反向搜索，當兩者在中間匯合時搜索停止。在很多情況下該算法更快，假設搜索一棵分支因子b的樹，初始節點到目標節點的距離為d，該算法的正向和反向搜索複雜度都是O(b^d/2) (大O符號)，兩者相加後遠遠小於普通的單項搜索算法（複雜度為O(b^d)）。

在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（英語：Artificial Intelligence: A Modern Approach） 2nd, Prentice Hall, 2002 .

[goldberg-1] Efficient Point-to-Point Shortest Path Algorithms (PDF). [2018-07-04]. （原始內容存檔 (PDF)於2018-06-18）.

[1]