雙向搜尋算法

雙向搜尋算法是一種圖的遍歷算法，用於在有向圖中搜尋從一個頂點到另一個頂點的最短路徑。

基本介紹

• 中文名：雙向搜尋算法
• 屬性：圖的遍歷算法

簡介

雙向搜尋算法是一種圖的遍歷算法，用於在有向圖中搜尋從一個頂點到另一個頂點的最短路徑。算法同時運行兩個搜尋：一個從初始狀態正向搜尋，另一個從目標狀態反向搜尋，當兩者在中間匯合時搜尋停止。在很多情況下該算法更快，假設搜尋一棵分支因子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。此問題在計算錯誤的拼圖圖形，與計算任兩塊拼圖的曼哈頓距離的總和以及它距離目的有多遠時，使用了本算法。注意，上述兩條件都必須在可接受的範圍內。