【正文】 ...................... 30 算法應(yīng)用 ....................................................................................................... 31 解決浙江旅行商問題時算法描述 ............................................................ 31 蟻群算法的算法描述 .............................................................................. 31 蟻群算法解決浙江旅行商問題 ................................................................ 34 第 5章 最短路徑算法的展望 .......................................................................................... 36 緒 論 ...................................................................................................................... 38 致 謝 ...................................................................................................................... 39 參考文獻(xiàn) ...................................................................................................................... 40 1 第 1章 緒論 選題的意義及目的 選題的意義 隨著計算機科學(xué)的發(fā)展，人們生產(chǎn)生活經(jīng)濟利潤的提高，最短路徑問題逐漸成為計算機科學(xué)、運籌學(xué)、地理信息科學(xué)等學(xué)科的一個研究熱點。也正因為最短路徑問題在實際生產(chǎn)生活中應(yīng)用廣泛，優(yōu)化該算法和提高算法的求解效率具有重大的現(xiàn)實意義。 最短路徑問題是圖論研究中 的一個經(jīng)典算法問題，旨在尋找圖（由結(jié)點和路徑組成的）中兩結(jié)點之間的最短路徑。算法具體的形式包括：確定起點的最短路徑問題 — 即已知起始結(jié)點，求最短路徑的問題；確定終點的最短路徑問題 — 與確定起點的問題相反，該問題是已知終結(jié)結(jié)點，求最短路徑的問題；在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同于把所有路徑方向反轉(zhuǎn)的確定起點的問題；確定起點終點的最短路徑問題 — 即已知起點和終點，求兩結(jié)點之間的最短路徑；全局最短路徑問題 — 求圖中所有的最短路徑。用于解決最短路徑問題的算法被稱作最短路徑算法 。 選題的目的 本文研究目的在于收集整理關(guān)于最短路徑的普遍算法，為研究最短路徑問題在一些出行問題、管理問題、工程問題及實際生活問題中的應(yīng)用，為企業(yè)和個人提供方便的選擇方法。同時，也為參加數(shù)學(xué)建模的同學(xué)提供一些解題的思路與方法，為比賽提供有利的資源。最后應(yīng)用蟻群算法來解決浙江旅行商問題。 選題經(jīng)過及國內(nèi)外動態(tài) 選題經(jīng)過 二十世紀(jì)中后期，隨著計算機的出現(xiàn)和發(fā)展，圖論的研究得到廣泛重視，最短路徑問題是圖論中的一個典范問題，它已經(jīng)被應(yīng)用于眾多領(lǐng)域，如地理信息領(lǐng)域等?，F(xiàn)實生活中最短路徑的運用非常多， 算法也很多，最短路徑的分析是網(wǎng)絡(luò)分析最基本的功能之一，近年來，隨著網(wǎng)絡(luò)的不斷發(fā)展，網(wǎng)絡(luò)中的最短路徑問題 2 具有重大的理論意義和應(yīng)用價值 。 選題的國內(nèi)外動態(tài) 最短路徑這一重要問題早在 20 世紀(jì)初就已經(jīng)得到人們的高度重視，當(dāng)時也有很多科學(xué)家研究這一問題的求解方法。但直到 1959 年荷蘭計算機科學(xué)家Edsger Wybe Dijkstra 才給出這一問題求解的基本方思想，并給出了算法。當(dāng)時的 Dijkstra 提出這一算法主要解決的問題是從固定的一個點到其他各點的最短路徑問題，后來這個算法就成了眾所周知的 Dijkstra 算法，也成了一代經(jīng)典。 現(xiàn)如今比較流行的最短路徑規(guī)劃算法主要有以下三類：第一類是基于圖論理論的算法；第二類則是基于傳統(tǒng)人工智能理論的算法；第三類則是基于智能控制技術(shù)的算法。特別是近 10 年來，智能控制技術(shù)在路徑規(guī)劃問題中得到廣泛應(yīng)用，人們的研究興趣也逐漸從對前兩類的算法改進(jìn)轉(zhuǎn)到了對第三類算法的進(jìn)一步研究。 3 第 2章 最短路徑算法的介紹 Dijkstra 算法 算法介紹及適用條件和范圍 Dijkstra(迪杰斯特拉 )算法是典型的單源最短路徑算法，用于計算一個 節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。 Dijkstra 算法是很有代表性的最短路徑算法，在很多專業(yè)課程中都作為基本內(nèi)容有詳細(xì)的介紹，如數(shù)據(jù)結(jié)構(gòu)，圖論，運籌學(xué)等等。 Dijkstra 一般的表述通常有兩種方式，一種用永久和臨時標(biāo)號方式，一種是用 OPEN, CLOSE 表的方式，這里均采用永久和臨時標(biāo)號的方式。注意該算法要求圖中不存在負(fù)權(quán)邊 。 （ 1）單源最短路徑（從源點 s到其它所有頂點 v）； （ 2）有向圖和無向圖（無向圖可以看作 ? ?,uv ， ? ?,vu 同屬于邊集 E 的有向圖）； （ 3）所有邊權(quán)非負(fù)（任取 ? ?,i j E? 都有 0ijW? ）。 算法描述和算法實現(xiàn) 如果 v1→ v2→ v3→ v4 是 v1→ v4 的最短路徑，則 v1→ v2→ v3 一定是 v1→ v3 的最短路徑。 v2→ v3→ v4 一定是 v2→ v4 的最短路徑。 （ 1）初 始化： dis[v]=maxint ? ?,v V v s??； dis[s]=0； pre[s]=s。S={s}； （ 2） For i:=1 to n ①取 VS中的一頂點 u使得 dis[u]=min{dis[v]|v∈ VS} ② S=S+{u} ③ For VS 中每個頂點 v do Relax ? ?, , ,uu vW v （ 3）算法結(jié)束： dis[i]為 s到 i的最短距離； pre[i]為 i的前驅(qū)節(jié)點。程序見參考文獻(xiàn) [8]。 4 具體算法分析 下 圖中的有向 圖，應(yīng)用 Dijkstra 算法計算從源頂點 1到其它頂點間最短路徑的過程列在下表中。 include iostream using namespace std。 const int maxnum = 100。 const int maxint = 999999。 // 各數(shù)組都從下標(biāo) 1 開始 int dist[maxnum]。 // 表示當(dāng)前點到源點的最短路徑長度 int prev[maxnum]。 // 記錄當(dāng)前點 的前一個結(jié)點 int c[maxnum][maxnum]。 // 記錄圖的兩點間路徑長度 int n, line。 // 圖的結(jié)點數(shù)和路徑數(shù) // n n nodes // v the source node // dist[ ] the distance from the ith node to the source node // prev[ ] the previous node of the ith node // c[ ][ ] every two nodes39。 distance void Dijkstra(int n, int v, int *dist, int *prev, int c[maxnum][maxnum]) { bool s[maxnum]。 // 判斷是否已存入該點到 S 集合中 for(int i=1。 i=n。 ++i) 1 2 5 3 4 10 50 100 20 10 30 60 5 { dist[i] = c[v][i]。 s[i] = 0。 // 初始都未用過該點 if(dist[i] == maxint) prev[i] = 0。 else prev[i] = v。 } dist[v] = 0。 s[v] = 1。 // 依次將未放入 S 集合的結(jié)點中，取 dist[]最小值的結(jié)點，放入結(jié)合 S 中 // 一旦 S 包含了所有 V中頂點， dist 就記錄了從源點到所有其他頂點之間的最短路徑長度 // 注意是從第二個節(jié)點開始，第一個為源點 for(int i=2。 i=n。 ++i) { int tmp = maxint。 int u = v。 // 找出 當(dāng)前未使用的點 j 的 dist[j]最小值 for(int j=1。 j=n。 ++j) if((!s[j]) amp。amp。 dist[j]tmp) { u = j。 // u 保存當(dāng)前鄰接點中距離最小的點的號碼 tmp = dist[j]。 } s[u] = 1。 // 表示 u 點已存入 S 集合中 // 更新 dist for(int j=1。 j=n。 ++j) if((!s[j]) amp。amp。 c[u][j]maxint) { int newdist = dist[u] + c[u][j]。 if(newdist dist[j]) { dist[j] = newdist。 prev[j] = u。 } } 6 } } // 查找從源點 v 到終點 u 的路徑，并輸出 void searchPath(int *prev,int v, int u) { int que[maxnum]。 int tot = 1。 que[tot] = u。 tot++。 int tmp = prev[u]。 while(tmp != v) { que[tot] = tmp。 tot++。 tmp = prev[tmp]。 } que[tot] = v。 for(int i=tot。 i=1。 i) if(i != 1) cout que[i] 。 else cout que[i] endl。 } int main() { freopen(, r, stdin)。 // 各數(shù)組都從下標(biāo) 1 開始 // 輸入結(jié)點數(shù) cin n。 // 輸入路徑數(shù) cin line。 int p, q, len。 // 輸入 p, q 兩點及其路徑長度 // 初始化 c[][]為 maxint for(int i=1。 i=n。 ++i) for(int j=1。 j=n。 ++j) c[i][j] = maxint。 for(int i=1。 i=line。 ++i) { 7 cin p q len。 if(len c[p][q]) // 有重邊 { c[p][q] = len。 // p 指向 q c[q][p] = len。 // q 指向 p，這樣表示無向圖 } } for(int i=1。 i=n。 ++i) dist[i] = maxint。 for(int i=1。 i=n。 ++i) { for(int j=1。 j=n。 ++j) printf(%8d, c[i][j])。 printf(\n)。 } Dijkstra(n, 1, dist, prev, c)。 // 最短路徑長度 cout 源點到最后一個頂點的最短路徑長度 : dist[n] endl。 // 路徑 cout 源點到最后一個頂點的路徑為 : 。 searchPath(prev, 1, n)。 } 輸入數(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