基本介紹
- 中文名：雙向搜尋
- 外文名：bidirectional search
- 領域：數據結構
- 定義：一種圖的遍歷算法
- 目的：尋找最短路徑
- 有關算法：A星算法
簡介,A*搜尋算法,戴克斯特拉算法,最短路徑,
簡介
搜尋是從初始狀態開始尋找問題的一組可能解，並最終求得滿意解的過程。雙向搜尋，在問題樹中分別從初始狀態和目標結點雙向搜尋，尋找最佳求解路線。在很多情況下該算法更快，假設搜尋一棵分支因子b的樹，初始節點到目標節點的距離為d，該算法的正向和反向搜尋複雜度都是O(
) (大O符號)，兩者相加後遠遠小於普通的單項搜尋算法（複雜度為O(
)）。Ira Pohl (1971)第一個設計並實現了雙向啟發式搜尋算法。Andrew Goldberg和其他人解釋了雙向搜尋版的戴克斯特拉算法的正確完結條件。
單向搜尋，在問題樹中從初始狀態出發向目標單方向搜尋。廣度優先搜尋，按“最早產生的結點優先擴展”的原則來定義估計函式，即對問題樹中的結點按層搜尋。深度優先搜尋，按“最晚產生的結點優先擴展”的原則來定義估計函式，即對問題樹中的結點按一個分枝向下搜尋，如無目標結點則返回並沿另一分枝搜尋，直至找到目標結點為止。最佳優先搜尋，根據估計函式對未擴展的結點全部進行估計，從中選出最佳結點擴展。
A*搜尋算法
A*搜尋算法，俗稱A星算法。這是一種在圖形平面上，有多個節點的路徑，求出最低通過成本的算法。常用於遊戲中的NPC的移動計算，或網路遊戲的BOT的移動計算上。
該算法綜合了Best-First Search和Dijkstra算法的優點：在進行啟發式搜尋提高算法效率的同時，可以保證找到一條最優路徑（基於評估函式）。
在此算法中，如果以 
表示從起點到任意頂點 
的實際距離，
表示任意頂點 到目標頂點的估算距離（根據所採用的評估函式的不同而變化），那么A*算法的估算函式為：
這個公式遵循以下特性：
如果為0，即只計算任意頂點到目標的評估函式，而不計算起點到頂點 的距離，則算法轉化為使用貪心策略的Best-First Search，速度最快，但可能得不出最優解；
算法中需要注意幾點：路徑中只有起始點沒有其他任何點的時候，此時，起始節點和終止節點是同一點，最優路徑為零。將節點定位起始節點用的時候這個點需耍被拿出表外，不能進行重複計算。
戴克斯特拉算法
戴克斯特拉算法（Dijkstra's algorithm）由荷蘭計算機科學家艾茲赫爾·戴克斯特拉在1956年提出。戴克斯特拉算法使用了廣度優先搜尋解決賦權有向圖的單源最短路徑問題。該算法存在很多變體；戴克斯特拉的原始版本找到兩個頂點之間的最短路徑，但是更常見的變體固定了一個頂點作為源節點然後找到該頂點到圖中所有其它節點的最短路徑，產生一個最短路徑樹。該算法常用於路由算法或者作為其他圖算法的一個子模組。舉例來說，如果圖中的頂點表示城市，而邊上的權重表示城市間開車行經的距離，該算法可以用來找到兩個城市之間的最短路徑。
該算法的輸入包含了一個有權重的有向圖 G，以及G中的一個來源頂點 S。我們以 V 表示 G 中所有頂點的集合。每一個圖中的邊，都是兩個頂點所形成的有序元素對。(u, v) 表示從頂點 u 到 v 有路徑相連。我們以 E 表示G中所有邊的集合，而邊的權重則由權重函式 w: E → [0, ∞] 定義。因此，w(u, v) 就是從頂點 u 到頂點 v 的非負權重（weight）。邊的權重可以想像成兩個頂點之間的距離。任兩點間路徑的權重，就是該路徑上所有邊的權重總和。已知 V 中有頂點 s 及 t，Dijkstra 算法可以找到 s 到 t 的最低權重路徑(例如，最短路徑)。這個算法也可以在一個圖中，找到從一個頂點 s 到任何其他頂點的最短路徑。
最初的戴克斯特拉算法不採用最小優先權佇列，時間複雜度是
(其中 
為圖的頂點個數)。通過斐波那契堆實現的戴克斯特拉算法時間複雜度是
(其中 
是邊數) （Fredman & Tarjan 1984）。對於不含負權的有向圖，這是已知的最快的單源最短路徑算法。
最短路徑
用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra算法能得出最短路徑的最優解，但由於它遍歷計算的節點很多，所以效率低。最短路徑問題是圖論研究中的一個經典算法問題，旨在尋找圖（由結點和路徑組成的）中兩結點之間的最短路徑。算法具體的形式包括：
- 確定起點的最短路徑問題 - 即已知起始結點，求最短路徑的問題。適合使用Dijkstra算法。
- 確定終點的最短路徑問題 - 與確定起點的問題相反，該問題是已知終結結點，求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同於把所有路徑方向反轉的確定起點的問題。
- 確定起點終點的最短路徑問題 - 即已知起點和終點，求兩結點之間的最短路徑。
- 全局最短路徑問題 - 求圖中所有的最短路徑。適合使用Floyd-Warshall算法。
