【正文】 28 第 4 章 最短路徑算法的應用 TSP 問題的介紹 TSP 問題，即 旅行商問題，是一種典型的組合最優(yōu)化問題 ，可描述為某旅行商欲往 n 個城市推銷貨物，從某個城市出發(fā)，沿途經(jīng)過各個城市一次后返回出發(fā)城市，要確定一條行走的路線， 計算途徑 n個城市的最短距離， 即給定ｎ個城市和兩兩城市之間的距離，確定一條經(jīng)過每個城市并且僅經(jīng)過一次的路線，要求總路徑最短。 BellmanFord 求單源最短路，可以判斷有無負權回路（若有，則不存在最短路），時效 性較好，時間復雜度 O（ VE）。 在實際算法中，為了節(jié)約空間，可以直接在原來空間上進行迭代，這樣空間可降至二維。 Floyd 求多源、無負權邊的最短路。 ()。 i 。 } } 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 s = 0。 i row。 u row。 i row。 j++) { if (G[i][j] == 0) 23 G[i][j] = MAX。// 圖 G 的行數(shù) int[][] spot = new int[row][row]。 22 （ 1） APSP(All Pairs Shortest Paths)； （ 2） 稠密圖效果最佳； （ 3） 邊權可正可負。 Menuselect()。 break。 } void Menuselect(){ int done=1,select,i。cinn。 for(i=0。ArcNode *p。 19 } } int LocateVex(ALGraph G,char m){ int i。flag) { ArcNode *p。 finished[i]=1。flag)。 typedef struct{ AdjList vertices。 17 具體算法設計 define MAXV 30 define OK 1 define ERROR 0 typedef char VertexType。 } return true。dis[j]dis[i]+graph[i][j]) return false。j++) if(i!=jamp。in。 } coutendl。 while(p) { if(plen+dis[i]dis[pnum]) 14 return false。 } dis[s]=0。 } graph。 For 每條邊 (u,v)∈ E do If dis[u]+wdis[v] Then Exit(False) （ 2） C/C++語言 void bellman_ford(int v) { for 1 to n initialize dist[v]。 } BellmanFord 算法 算法介紹及適用條件和范圍 BellmanFord 算法能在更普遍的情況下（存在負權邊）解決單源點最短路徑問題。139。 } } } } int main(){ char line[5]。i++){ =+dirs[i][0],=+dirs[i][1]。 } void Astar(){ //A*算法 knight t,s。 //已訪問標記 (關閉列表 ) int x1,y1,x2,y2,ans。 具體算法分析 在國際象棋的棋盤上，一匹馬共有 8 個可能的跳躍方向，求從起點到目標點之間的最少跳躍次數(shù) 。 9 算法描述和算法實現(xiàn) 算法描述及其實現(xiàn) （ 1） 初始狀態(tài)： OPEN=[A5]。 } 輸入數(shù)據(jù) : 5 7 1 2 10 1 4 30 1 5 100 2 3 50 3 5 10 4 3 20 4 5 60 輸出數(shù)據(jù) : 999999 10 999999 30 100 10 999999 50 999999 999999 999999 50 999999 20 10 30 999999 20 999999 60 8 100 999999 10 60 999999 A* 算法 算法介紹及適用條件和范圍 A*（ AStar）算法是一種靜態(tài)路網(wǎng)中求解最短路徑最有效的方法； 公式表示為 ： f(n)=g(n)+h(n), 其中 f(n) 是從初始點經(jīng)由節(jié)點 n 到目標點的估價函數(shù)， g(n) 是在狀態(tài)空間中從初始節(jié)點到 n 節(jié)點的實際代價， h(n)是從 n 到目標節(jié)點最佳路徑的估計代價 A*算法屬于一種啟發(fā)式搜索。 ++i) { for(int j=1。 ++i) { 7 cin p q len。 int p, q, len。 } que[tot] = v。 } } 6 } } // 查找從源點 v 到終點 u 的路徑，并輸出 void searchPath(int *prev,int v, int u) { int que[maxnum]。 } s[u] = 1。 ++i) { int tmp = maxint。 ++i) 1 2 5 3 4 10 50 100 20 10 30 60 5 { dist[i] = c[v][i]。 // 各數(shù)組都從下標 1 開始 int dist[maxnum]。 v2→ v3→ v4 一定是 v2→ v4 的最短路徑。特別是近 10 年來，智能控制技術在路徑規(guī)劃問題中得到廣泛應用，人們的研究興趣也逐漸從對前兩類的算法改進轉(zhuǎn)到了對第三類算法的進一步研究。同時，也為參加數(shù)學建模的同學提供一些解題的思路與方法，為比賽提供有利的資源。最后應用蟻群算法來解決浙江旅行商問題。也正因為最短路徑問題在實際生產(chǎn)生活中應用廣泛，優(yōu)化該算法和提高算法的求解效率具有重大的現(xiàn)實意義?，F(xiàn)實生活中最短路徑的運用非常多， 算法也很多，最短路徑的分析是網(wǎng)絡分析最基本的功能之一，近年來，隨著網(wǎng)絡的不斷發(fā)展，網(wǎng)絡中的最短路徑問題 2 具有重大的理論意義和應用價值 。 Dijkstra 算法是很有代表性的最短路徑算法，在很多專業(yè)課程中都作為基本內(nèi)容有詳細的介紹，如數(shù)據(jù)結構，圖論，運籌學等等。程序見參考文獻 [8]。 // 記錄圖的兩點間路徑長度 int n, line。 else prev[i] = v。 j=n。 ++j) if((!s[j]) amp。 tot++。 i) if(i != 1) cout que[i] 。 ++i) for(int j=1。 // q 指向 p，這樣表示無向圖 } } for(int i=1。 printf(\n)。 確定估價函數(shù)方法通常是：搜索到該結點的深度 + 距離目標最近的程度。 CLOSED=[A5] （ 3） 估算 B4，取得搜有子節(jié)點，并放入 OPEN 表中； OPEN=[C4, E5, F5, D6]。 int g,h,f。 //最小優(yōu)先級隊列 (開啟列表 ) bool in(const knight amp。amp。 !visited[][]){ = + 23。,y1=line[1]39。 while(!()) ()。若不存在這樣的回路，算法將給出從源點 s 到 圖 G 的任意頂點 v 的最短路徑 d[v]。 dist[k] edge[k][j]+dist[j] 更新當前值 } 具體算法設計 typedef struct oo { int len,num。 link *p。i++) { p=node[i].next。in。 const int MAXVALUE = 1000。 } dis[s]=0。 pre[j]=i。i++) { printf(%d %d\n,i,dis[i])。一般的大型工程，都可劃分為多個工序 /步驟 /子工程，這些工序有的可以獨立進行，但大多數(shù)和其他工序關聯(lián)，即某工序的進行，要等到其他一些工序的完成才能開始，這類問題都可歸結到拓撲排序。 struct ArcNode *nextarc。 int LocateVex(ALGraph G,char m)。 18 int finish