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