雙向搜索

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

A*搜尋演算法中,雙向搜索的啟發式函數可以定義為:正向搜索為到目標節點的距離,反向搜索為到初始節點的距離。

Ira Pohl (1971第一個設計並實現了雙向啟發式搜索算法。Andrew Goldberg和其他人解釋了雙向搜索版的戴克斯特拉算法的正確完結條件。[1]


參考

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