text: 雙向搜尋演算法是一種圖的遍歷演算法，用於在中搜索從一個頂點到另一個頂點的最短路徑。演算法同時執行兩個搜尋：一個從初始狀態正向搜尋，另一個從目標狀態反向搜尋，當兩者在中間匯合時搜尋停止。在很多情況下該演算法更快，假設搜尋一棵分支因子"b"的樹，初始節點到目標節點的距離為"d"，該演算法的正向和反向搜尋複雜度都是"O"("b""d"/2) (大O符號)，兩者相加後遠遠小於普通的單項搜尋演算法。在A*搜尋演演算法中，雙向搜尋的啟發式函式可以定義為：正向搜尋為到目標節點的距離，反向搜尋為到初始節點的距離。Ira Pohl 第一個設計並實現了雙向啟發式搜尋演算法。Andrew Goldberg和其他人解釋了雙向搜尋版的戴克斯特拉演算法的正確完結條件。
metadata: erhwenkuo/wikipedia-zhtw
metadata: 雙向搜尋
metadata: https://zh.wikipedia.org/wiki?curid=6208022