【正文】 n 個城市推銷貨物，從某個城市出發(fā)，沿途經(jīng)過各個城市一次后返回出發(fā)城市，要確定一條行走的路線， 計(jì)算途徑 n個城市的最短距離， 即給定ｎ個城市和兩兩城市之間的距離，確定一條經(jīng)過每個城市并且僅經(jīng)過一次的路線，要求總路徑最短。而且路徑的增加速度非?？烨沂欠蔷€形的。貪心算法容易實(shí)現(xiàn)但是效率不好。 我們從 A 到 B， 然后設(shè)定 A和 B 之間的距離無限大。 29 模擬退火算法 模擬退火算法是一種求解大規(guī)模組合優(yōu)化問題的方法 ， 對于 NP完全組合優(yōu)化問題尤其有效。 根據(jù) Metropolis 準(zhǔn)則 ， 粒子在溫度 T時趨于平衡的概率為 exp( E/(kT)), 其中 E為溫度 T時的內(nèi)能 ， E為其改變量 ， k為 Boltzman 常數(shù)。反之 ， 如果急速降溫 (即淬火 )則不能達(dá)到最低點(diǎn)。如此然后去 C， 再到 D。距離從 A 到 B 是 5 公里 ， A 到 C 是 6 公里 ， A 到 D 是 9 公里 ， B 到 C 是 3公里 , B 到 D 是 7 公里， C 到 D 是 8 公里。 TSP 問題算法的介紹 貪心算法 貪心算法的主要思想是永遠(yuǎn)選擇當(dāng)前最短的路徑。 對于城市數(shù)目為 n的地圖 , 共有 n 種不同的路徑。如果不處理這個負(fù)環(huán)路，程序就會永遠(yuǎn)運(yùn)行下去。 單源點(diǎn)的最短路徑問題是指：給定一個加權(quán)有向圖 G和源點(diǎn) s，對于圖 G中的任意一點(diǎn) v，求從 s 到 v 的最短路徑。 當(dāng)是稀疏圖的情況時，此時 E=V*V/lgV，所以算法的時間復(fù)雜度可為 O（ V^2） 。 其中 Di,j 表示由點(diǎn) i到點(diǎn) j的代價，當(dāng) Di,j 為 ∞ 表示兩點(diǎn)之間沒有任何連接。 若最短路徑經(jīng)過點(diǎn) k，則 Di,j,k = Di,k,k1 + Dk,j,k1； 若最短路徑不經(jīng)過點(diǎn) k，則 Di,j,k = Di,j,k1。時效性較差，時間復(fù)雜度O(V^3)。 確定起點(diǎn)終點(diǎn)的最短路徑問題：即已知起點(diǎn)和終點(diǎn)，求兩結(jié)點(diǎn)之間的最短路徑。 } } } 26 第 3 章 最短路徑 算法的比較 最短路徑 問題是圖論研究中的一個經(jīng)典算法問題，旨在尋找圖（由結(jié)點(diǎn)和路徑組成的）中兩結(jié)點(diǎn)之間的最短路徑。 k [i][j].length。 j data[i].length。 FLOYD test=new FLOYD(data)。 i 。 else { outputPath(spot, i, spot[i][j], onePath, point)。 s++) path[i][j][s] = onePath[s]。 outputPath(spot, i, j, onePath, point)。 for (int j = 0。// 如果存在更短路徑則取更短路徑 spot[v][w] = u。 v row。 ++w) length[v][w] = G[v][w]。 for (int v = 0。 j++) spot[i][j] = 1。// 本身的路徑長度為 0 } for (int i = 0。 i++) // 處理圖兩點(diǎn)之間的路徑 for (int j = 0。// 記錄一條路徑 length = new int[row][row]。// 任意兩點(diǎn)之間的路徑 public FLOYD(int[][] G) { int MAX = 100。 （ 2） For k=1 to n For i=1 to n For j=1 to n If dis[i,j]dis[i,k]+dis[k,j] Then Dis[i,j]=dis[i,k]+dis[k,j]。 從圖的帶權(quán)鄰接矩陣 A=[a(i,j)] nn 開始，遞歸地進(jìn)行 n 次更新，即由矩陣 D(0)=A，按一個公式，構(gòu)造出陣 D(1)；又用同樣地公式由 D(1)構(gòu)造出 D(2)； ?? ；最后又用同樣的公式由 D(n1)構(gòu)造出矩陣 D(n)。 算法描述和算法實(shí)現(xiàn) （ 1） Toposort； （ 2） If Toposort=False Then HALT(Not a DAG)； （ 3） For 拓?fù)湫虻拿總€頂點(diǎn) u do For u的每個鄰接點(diǎn) v do Relax(u,v,w)； （ 4） 算法結(jié)束后：如有環(huán)則輸出錯誤信息；否則 dis[i]為 s到 i的最短距離， pre[i]為前驅(qū)頂點(diǎn)。 default:printf(輸入的操作碼錯誤 \n\n)。 printf(\n\n)。 switch(select){ case 1: if(Creat_Graph1(g))printf(OK)。 printf(please input select number)。 [i].firstarc=p。j=LocateVex(G,n)。r。i++) {cin[i].data。)。 scanf(%d,amp。G){ int i,j,r。i。 finished[padjvex ]=1。 finished[v]=0。} } return flag。 //從編號為 0的頂點(diǎn)開始遍歷 while(flagamp。in。 頭文件 include include include include include int visited[MAXV]。 int dfs_topsort(ALGraph g,int n)。 }ALGraph。 ArcNode *firstarc。 typedef struct ArcNode{ int adjvex。 （ 1）數(shù)據(jù)結(jié)構(gòu)： adj:鄰接表 。這種操作在有關(guān)工程進(jìn)度 /次序規(guī)劃之類問題中有著大量的應(yīng)用。 k=pre[k]。in。j++) if(i!=jamp。dis[j]dis[i]+graph[i][j]) { dis[j]=dis[i]+graph[i][j]。i++) { for(j=0。 pre[i]=1。 int i,j,k。 } //這個是鄰接矩陣 const int MAX = 100。 while(j!=1) { printf(%d ,j)。 } } for(i=0。} p=pnext。in。i++) { dis[i]=MAXVALUE。 int i,j。 typedef struct { int num。amp。如果存在未收斂的頂點(diǎn)，則算法返回 false，表明問題無解；否則算法返回 true，并且從源點(diǎn)可達(dá)的頂點(diǎn) v 的最短距離保存在 d[v]中。對圖 G 運(yùn)行 BellmanFord算法的結(jié)果是一個布爾值，表明圖中是否存在著一個從源點(diǎn) s 可達(dá)的負(fù)權(quán)回路。 printf(To get from %c%c to %c%c takes %d knight moves.\n,line[0],line[1],line[3],line[4],ans)。 =x1,=y1,==0,=Heuristic(k),=+。a39。a39。 = + 1。amp。 } for(int i=0。 if(==x2 amp。 } int Heuristic(const knight amp。//8個移動方向 priority_queueknight que。 } }k。 struct knight{ int x,y,step。 CLOSED=H3C4, B4, A5] （ 6） 估算 O2，取得搜有子節(jié)點(diǎn)，并放入 OPEN 表中； OPEN=[P3, G4, E5, F5, D6]。 （ 2） 估算 A5，取得搜有子節(jié)點(diǎn)，并放入 OPEN 表中； OPEN=[B4, C4, D6]。算法中有一步是根據(jù)估價函數(shù)重排 OPEN 表。 因此， A*算法只 要求產(chǎn)生問題的全部狀態(tài)空間的部分結(jié)點(diǎn)，就可以求解問題了，搜索效率較高。 // 路徑 cout 源點(diǎn)到最后一個頂點(diǎn)的路徑為 : 。 ++j) printf(%8d, c[i][j])。 for(int i=1。 // p 指向 q c[q][p] = len。 for(int i=1。 i=n。 // 各數(shù)組都從下標(biāo) 1 開始 // 輸入結(jié)點(diǎn)數(shù) cin n。 i=1。 tot++。 que[tot] = u。 if(newdist dist[j]) { dist[j] = newdist。 j=n。 dist[j]tmp) { u = j。 // 找出 當(dāng)前未使用的點(diǎn) j 的 dist[j]最小值 for(int j=1。 // 依次將未放入 S 集合的結(jié)點(diǎn)中，取 dist[]最小值的結(jié)點(diǎn)，放入結(jié)合 S 中 // 一旦 S 包含了所有 V中頂點(diǎn)， dist 就記錄了從源點(diǎn)到所有其他頂點(diǎn)之間的最短路徑長度 // 注意是從第二個節(jié)點(diǎn)開始，第一個為源點(diǎn) for(int i=2。 // 初始都未用過該點(diǎn) if(dist[i] == maxint) prev[i] = 0。 // 判斷是否已存入該點(diǎn)到 S 集合中 for(int i=1。 // 記錄當(dāng)前點(diǎn) 的前一個結(jié)點(diǎn) int c[maxnum][maxnum]。 const int maxnum = 100。S={s}； （ 2） For i:=1 to n ①取 VS中的一頂點(diǎn) u使得 dis[u]=min{dis[v]|v∈ VS} ② S=S+{u} ③ For VS 中每個頂點(diǎn) v do Relax ? ?, , ,uu vW v （ 3）算法結(jié)束： dis[i]為 s到 i的最短距離； pre[i]為 i的前驅(qū)節(jié)點(diǎn)。 （ 1）單源最短路徑（從源點(diǎn) s到其它所有頂點(diǎn) v）； （ 2）有向圖和無向圖（無向圖可以看作 ? ?,uv ， ? ?,vu 同屬于邊集 E 的有向圖）； （ 3）所有邊權(quán)非負(fù)（任取 ? ?,i j E? 都有 0ijW? ）。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。當(dāng)時的 Dijkstra 提出這一算法主要解決的問題是從固定的一個點(diǎn)到其他各點(diǎn)的最短路徑問題，后來這個算法就成了眾所周知的 Dijkstra 算法，也成了一代經(jīng)典。 選題經(jīng)過及國內(nèi)外動態(tài) 選題經(jīng)過 二十世紀(jì)中后期，隨著計(jì)算機(jī)的出現(xiàn)和發(fā)展，圖論的研究得到廣泛重視，最短路徑問題是圖論中的一個典范問題，它已經(jīng)被應(yīng)用于眾多領(lǐng)域，如地理信息領(lǐng)域等。用于解決最短路徑問題的算法被稱作最短路徑算法 。 關(guān)鍵詞： 最短路徑算法；最短路徑應(yīng)用；蟻群 算法； 浙江旅行商 II Abstract In this paper, the purpose is to collect the shortest path algorithm about mon for the shortest path problem in some travel problems, management, engineering problems and practical application of life, for enterprise and individual with convenient selection method. At the same time, the students for the mathematical modeling provide some ideas and methods for problem solving, provide favorable resources for the game. At last, by use of ant colony algorithm to solve the zhejiang traveling salesman problem. Through the applicatio