雙向搜尋算法

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

基本介紹

簡介,啟發式函式,圖遍歷,啟發式算法與最短路徑問題,

簡介

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

相關詞條

熱門詞條

聯絡我們