最短路徑算法的研究畢業設計-資料下載頁

【導讀】管理問題、工程問題及實際生活問題中的應用，為企業和個人提供方便的選擇方法。同時，也為其他的同學提供一些解題的思路與方法，為他們提供有利的資源。用蟻群算法來解決浙江旅行商問題。為初始條件，通過MATLAB程序計算最短路徑，并畫出最短路線圖。

　　

【正文】 ) { if (G[i][j] == 0) 23 G[i][j] = MAX。// 沒有路徑的兩個點之間的路徑為默認最大 if (i == j) G[i][j] = 0。// 本身的路徑長度為 0 } for (int i = 0。 i row。 i++) // 初始化為任意兩點之間沒有路徑 for (int j = 0。 j row。 j++) spot[i][j] = 1。 for (int i = 0。 i row。 i++) // 假設任意兩點之間的沒有路徑 onePath[i] = 1。 for (int v = 0。 v row。 ++v) for (int w = 0。 w row。 ++w) length[v][w] = G[v][w]。 for (int u = 0。 u row。 ++u) for (int v = 0。 v row。 ++v) for (int w = 0。 w row。 ++w) if (length[v][w] length[v][u] + length[u][w]) { length[v][w] = length[v][u] + length[u][w]。// 如果存在更短路徑則取更短路徑 spot[v][w] = u。// 把經過的點加入 } for (int i = 0。 i row。 i++) { // 求出所有的路徑 int[] point = new int[1]。 for (int j = 0。 j row。 j++) { point[0] = 0。 onePath[point[0]++] = i。 outputPath(spot, i, j, onePath, point)。 path[i][j] = new int[point[0]]。 for (int s = 0。 s point[0]。 s++) path[i][j][s] = onePath[s]。 } } } void outputPath(int[][] spot, int i, int j, int[] onePath, int[] point) {// 輸出 i // 到 j 24 // 的路徑的實際代碼， point[]記錄一條路徑的長度 if (i == j) return。 if (spot[i][j] == 1) onePath[point[0]++] = j。 // ( +j+ )。 else { outputPath(spot, i, spot[i][j], onePath, point)。 outputPath(spot, spot[i][j], j, onePath, point)。 } } public static void main(String[] args) { int data[][] = { { 0, 27, 44, 17, 11, 27, 42, 0, 0, 0, 20, 25, 21, 21, 18, 27, 0 },// x1 { 27, 0, 31, 27, 49, 0, 0, 0, 0, 0, 0, 0, 52, 21, 41, 0, 0 },// 1 { 44, 31, 0, 19, 0, 27, 32, 0, 0, 0, 47, 0, 0, 0, 32, 0, 0 },// 2 { 17, 27, 19, 0, 14, 0, 0, 0, 0, 0, 30, 0, 0, 0, 31, 0, 0 },// 3 { 11, 49, 0, 14, 0, 13, 20, 0, 0, 28, 15, 0, 0, 0, 15, 25, 30 },// 4 { 27, 0, 27, 0, 13, 0, 9, 21, 0, 26, 26, 0, 0, 0, 28, 29, 0 },// 5 { 42, 0, 32, 0, 20, 9, 0, 13, 0, 32, 0, 0, 0, 0, 0, 33, 0 },// 6 { 0, 0, 0, 0, 0, 21, 13, 0, 19, 0, 0, 0, 0, 0, 0, 0, 0 },// 7 { 0, 0, 0, 0, 0, 0, 0, 19, 0, 11, 20, 0, 0, 0, 0, 33, 21 },// 8 { 0, 0, 0, 0, 28, 26, 32, 0, 11, 0, 10, 20, 0, 0, 29, 14, 13 },// 9 { 20, 0, 47, 30, 15, 26, 0, 0, 20, 10, 0, 18, 0, 0, 14, 9, 20 },// 10 { 25, 0, 0, 0, 0, 0, 0, 0, 0, 20, 18, 0, 23, 0, 0, 14, 0 },// 11 { 21, 52, 0, 0, 0, 0, 0, 0, 0, 0, 0, 23, 0, 27, 22, 0, 0 },// 25 12 { 21, 21, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 27, 0, 0, 0, 0 },// 13 { 18, 41, 32, 31, 15, 28, 0, 0, 0, 29, 14, 0, 22, 0, 0, 11, 0 },// 14 { 27, 0, 0, 0, 25, 29, 33, 0, 33, 14, 9, 14, 0, 0, 11, 0, 9 },// 15 { 0, 0, 0, 0, 30, 0, 0, 0, 21, 13, 20, 0, 0, 0, 0, 9, 0 } // 16 }。 for (int i = 0。 i 。 i++) for (int j = i。 j 。 j++) if (data[i][j] != data[j][i]) return。 FLOYD test=new FLOYD(data)。 for (int i = 0。 i 。 i++) for (int j = i。 j data[i].length。 j++) { ()。 (From + i + to + j + path is: )。 for (int k = 0。 k [i][j].length。 k++) ([i][j][k] + )。 ()。 (From + i + to + j + length : + [i][j])。 } } } 26 第 3 章 最短路徑 算法的比較 最短路徑 問題是圖論研究中的一個經典算法問題，旨在尋找圖（由結點和路徑組成的）中兩結點之間的最短路徑。 算法具體的形式包括： 確定起點的最短路徑問題：即已知起始結點，求最短路徑的問題。 確定終點的最短路徑問題：與確定起點的問題相反，該問題是已知終結結點，求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同于把所有路徑方向反轉的確定起點的問題。 確定起點終點的最短路徑問題：即已知起點和終點，求兩結點之間的最短路徑。 全局最短路徑問題：求圖中所有的最短路徑。 Floyd 求多源、無負權邊的最短路。用矩陣記錄圖。時效性較差，時間復雜度O(V^3)。 FloydWarshall 算法（ FloydWarshall algorithm）是解決任意兩點間的最短路徑的一種算法，可以正確處理有向圖或負權的最短路徑問題。 FloydWarshall 算法的時間復雜度為 O(N^3)，空間復雜度為 O(N^2)。 FloydWarshall 的原理是動態規劃： 設 Di,j,k 為從 i 到 j的只以 (1..k)集合中的節點為中間節點的最短路徑的長度。 若最短路徑經過點 k，則 Di,j,k = Di,k,k1 + Dk,j,k1； 若最短路徑不經過點 k，則 Di,j,k = Di,j,k1。 因此， Di,j,k = min(Di,k,k1 + Dk,j,k1 , Di,j,k1)。 在實際算法中，為了節約空間，可以直接在原來空間上進行迭代，這樣空間可降至二維。 FloydWarshall 算法的描述如下： for k ← 1 to n do for i ← 1 to n do for j ← 1 to n do if (Di,k + Dk,j Di,j) then 27 Di,j ← Di,k + Dk,j。 其中 Di,j 表示由點 i到點 j的代價，當 Di,j 為 ∞ 表示兩點之間沒有任何連接。 Dijkstra 求單源、無負權的最短路。時效性較好，時間復雜度為 O（ V*V+E）。 源點可達的話， O（ V*lgV+E*lgV） =O（ E*lgV）。 當是稀疏圖的情況時，此時 E=V*V/lgV，所以算法的時間復雜度可為 O（ V^2） 。若是斐波那契堆作優先隊列的話，算法時間復雜度，則為 O（ V*lgV + E）。 BellmanFord 求單源最短路，可以判斷有無負權回路（若有，則不存在最短路），時效 性較好，時間復雜度 O（ VE）。 BellmanFord 算法是求解單源最短路徑問題的一種算法。 單源點的最短路徑問題是指：給定一個加權有向圖 G和源點 s，對于圖 G中的任意一點 v，求從 s 到 v 的最短路徑。 與 Dijkstra 算法不同的是，在 BellmanFord 算法中，邊的權值可以為負數。設想從我們可以從圖中找到一個環路（即從 v出發，經過若干個點之后又回到 v）且這個環路中所有邊的權值之和為負。那么通過這個環路，環路中任意兩點的最短路徑就可以無窮小下去。如果不處理這個負環路，程序就會永遠運行下去。 而BellmanFord 算法具有分辨這種負環路的能力。 28 第 4 章 最短路徑算法的應用 TSP 問題的介紹 TSP 問題，即 旅行商問題，是一種典型的組合最優化問題 ，可描述為某旅行商欲往 n 個城市推銷貨物，從某個城市出發，沿途經過各個城市一次后返回出發城市，要確定一條行走的路線， 計算途徑 n個城市的最短距離， 即給定ｎ個城市和兩兩城市之間的距離，確定一條經過每個城市并且僅經過一次的路線，要求總路徑最短。 TSP 分為 2類，即對稱 TSP 和不對稱 TSP。 對于城市數目為 n的地圖 , 共有 n 種不同的路徑。城市越多 ,可能的路徑也越多。而且路徑的增加速度非常快且是非線形的。當 n 很大時 ， 去嘗試每一種可能的路徑是不可能的 ， 所以需要設計一個有效的算法去尋找最短的路徑。 TSP 問題算法的介紹 貪心算法 貪心算法的主要思想是永遠選擇當前最短的路徑。這是解決 TSP問題的最簡便的算法。貪心算法容易實現但是效率不好。如下圖所示 :有 4 個城市 :A， B， C和 D。距離從 A 到 B 是 5 公里 ， A 到 C 是 6 公里 ， A 到 D 是 9 公里 ， B 到 C 是 3公里 , B 到 D 是 7 公里， C 到 D 是 8 公里。假設我們一開始在 A， 比較 A 到其他點的 路徑長度 ， 找出 A 到 B 是最短的路徑 (5 公里 )。 我們從 A 到 B， 然后設定 A和 B 之間的距離無限大。在 B我們找出 B 到 C(3 公里 )是最短的路徑。如此然后去 C， 再到 D。所以 ， 此算法則總是選擇最短的路徑。 29 模擬退火算法 模擬退火算法是一種求解大規模組合優化問題的方法 ， 對于 NP完全組合優化問題尤其有效。模擬退火算法來源于固體退火原理 ， 將固體加溫至充分高 ， 再讓其緩慢降溫 (即退火 )， 使之達到能量最低點。反之 ， 如果急速降溫 (即淬火 )則不能達到最低點。加溫時 , 固體內部粒子隨溫升變為無序狀 ， 內能增大 ， 而緩慢降溫時 粒子漸趨有序 ， 在每個溫度上都達到平衡態 ， 最后在常溫時達到基態 ，內能減為最小。 根據 Metropolis 準則 ， 粒子在溫度 T時趨于平衡的概率為 exp( E/(kT)), 其中 E為溫度 T時的內能 ， E為其改變量 ， k為 Boltzman 常數。用固體退火模擬組合優化問題 ， 將內能 E模擬為目標函數值 f， 溫度 T 演化成控制參數 t， 即得到解組合優化問題的模擬退火算法 : 由初始解 i和控制參數初值 t開始 ， 對當前解重復產生“新解→計算目標函數差→接受或舍棄”的迭代 ， 并