簡介
雙向搜尋算法是一種圖的遍歷算法，用於在有向圖中搜尋從一個頂點到另一個頂點的最短路徑。算法同時運行兩個搜尋：一個從初始狀態正向搜尋，另一個從目標狀態反向搜尋，當兩者在中間匯合時搜尋停止。在很多情況下該算法更快，假設搜尋一棵分支因子 b的樹，初始節點到目標節點的距離為 d，該算法的正向和反向搜尋複雜度都是 O( b) (大O符號)，兩者相加後遠遠小於普通的單項搜尋算法（複雜度為 O( b)）。
啟發式函式
在A*搜尋算法中，雙向搜尋的啟發式函式可以定義為：正向搜尋為到目標節點的距離，反向搜尋為到初始節點的距離。
Ira Pohl(1971)第一個設計並實現了雙向啟發式搜尋算法。Andrew Goldberg和其他人解釋了雙向搜尋版的戴克斯特拉算法的正確完結條件。
圖遍歷
圖遍歷問題分為四類：
•遍歷完所有的邊而不能有重複，即所謂“一筆畫問題”或“歐拉路徑”；
•遍歷完所有的頂點而沒有重複，即所謂“哈密頓路徑問題”。
•遍歷完所有的邊而可以有重複，即所謂“中國郵遞員問題”；
•遍歷完所有的頂點而可以重複，即所謂“旅行推銷員問題”。
對於第一和第三類問題已經得到了完滿的解決，而第二和第四類問題則只得到了部分解決。
第一類問題就是研究所謂的歐拉圖的性質，而第二類問題則是研究所謂的哈密頓圖的性質。
啟發式算法與最短路徑問題
所謂的最短路徑問題有很多種意思，在這裡 啟發式指的是一個在一個搜尋樹的節點上定義的函式{\displaystyle h(n)}，用於評估從此節點到目標節點最便宜的路徑。啟發式通常用於信息充份的搜尋算法，例如最好優先貪心算法與A*。最好優先貪心算法會為啟發式函式選擇最低代價的節點；A*則會為g(n)+h(n)選擇最低代價的節點，此g(n)是從起始節點到目前節點的路徑的確實代價。如果h(n)是 可接受的（admissible）意即 h(n)未曾付出超過達到目標的代價，則A*一定會找出最佳解。
最能感受到啟發式算法好處的經典問題是n-puzzle。此問題在計算錯誤的拼圖圖形，與計算任兩塊拼圖的曼哈頓距離的總和以及它距離目的有多遠時，使用了本算法。注意，上述兩條件都必須在可接受的範圍內。
