免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 回復 發帖

演算法概論

其實我在這裏可以簡單地介紹一下一些最短路徑尋找方法的演算法。

1. 最簡單的:廣度優先搜尋 Breadth First Search
對於所有未尋訪而當前節點可到達的節點,即搜尋他,並把它加進隊列內。
這是假設了在 G(V,E) 中每個 Edge 的長度為一。

2. Dijkstra's Algorithm
對於所有未到達而可到達的節點,把它加進優先隊列 (priority queue) 內,依照 edge 的長度由短至長搜尋之。
這裏假設在 G(V,E) 中每個 Edge 的長度不是負數。

3. Bellman Ford Algorithm
對於每一個節點,先假設它們之間的長度是無限 (通常在電腦編程時會設成 2147483647/2 )
然後執行 V-1 次:對於每個 Edge (u,v) ,如果距離[u] < 距離[v] + 由 u 到 v 的 Edge 的長度,則把距離[u]設成距離[v] + 由 u 到 v 的 Edge 的長度。

4. Foyld-Warshall Algorithm
這個演算法可以找出*所有*節點的最短路徑。

首先把 d[i][j] 設成由 i 至 j 之間的 edge 長度。

For k ← 1 To N Do
   For i ← 1 To N Do
      For j ← 1 To N Do
         d[i][j] = Min(d[i][j], d[i][k] + d[k][j])

5. A* 搜尋法
以一估計函數 h(x) 判斷跟目標相差多遠。使用一 priority queue ,使用 h(x) + 該步的代價排序,使用類似 BFS 的方法作搜尋。


另外還有一些演算法你可以去找找:
IDA* 搜尋法
MA*
SA*
雙向式 BFS

加油!
返回列表