【正文】 經(jīng)典的問題之一。它在廣泛的應(yīng)用于運(yùn)輸、生產(chǎn)、國(guó)防、生物、計(jì)算機(jī)等領(lǐng)域以外，還為離散優(yōu)化中各類算法提供了思想方法平臺(tái)。因而對(duì)尋找出實(shí)際而又有效算法，就具有重要的理論意義，同時(shí)也具有重要的實(shí)際應(yīng)用價(jià)值。這也說明了，首先該問題無法獲得徹底的解決，這在數(shù)學(xué)上已經(jīng)被證明；同時(shí)，次優(yōu)的解決方法已經(jīng)有了比較成熟的發(fā)展。所以在該文章中，將重點(diǎn)放在了已有算法的惡比較和學(xué)習(xí)上。這包括了精確算法和啟發(fā)式算法。對(duì)三種精確算法進(jìn)行了比較；啟發(fā)算法中選擇了遺傳算法進(jìn)行了簡(jiǎn)單的分析。作為啟發(fā)式算法的遺傳算法，有著精確算法所無法比擬的優(yōu)勢(shì)，可處理數(shù)據(jù)量的巨大優(yōu)勢(shì)使得在算法優(yōu)劣性上占據(jù)上風(fēng)。但在學(xué)習(xí)的初期，精確算法更適于理解該問題的數(shù)學(xué)本質(zhì)，為以后更高級(jí)算法，如遺傳算法的數(shù)學(xué)分析做好基礎(chǔ)。由于水平的不足，在論文的寫作中有很多遺憾。但在整個(gè)過程中，也加深了自己對(duì)旅行售貨員這一數(shù)學(xué)問題的理解，對(duì)于數(shù)學(xué)和應(yīng)用的相結(jié)合也有了更多的想法。希望以后可以對(duì)此有更多的研究參 考 文 獻(xiàn)[1] [M].北京:機(jī)械工業(yè)出版社,2005.[2] [M].北京:.[3] 嚴(yán)蔚敏,[M].北京:清華大學(xué)出版社,2005.[4] 蘇麗杰,[J].信息與控制, 2003, 32 (7) ,686691.[5] 王小平,[M].西安:西安交通大學(xué)出版社,2002.[6] [J].,13(6) :677700.[7] 曾建潮,[J].模型識(shí)別與人工智能, 2008(3)685688.[8] 戚玉濤,焦李成,[J].軟件學(xué)報(bào)，2008, 6(6) ,12651273.[9] 介婧,曾建潮,韓崇昭．基于群體多樣性反饋控制的自組織微粒群算法[J].計(jì)算機(jī)研究與發(fā)展，2008，45(3) ,464471.[10] , , , , and . Particle swarm optimizationbased algorithms for TSP and generalized TSP[J]. Information Processing Letters, 2007, (3) :169176.附錄Ａ　旅行售貨員問題的最小耗費(fèi)分枝定界算法template T AdjacencyWDigraph::BBTSP(int v[]) // 旅行售貨員問題的最小耗費(fèi)分枝定界算法 { MinHeap H(1000)。 // 定義一個(gè)最多可容納1000個(gè)活節(jié)點(diǎn)的最小堆T *MinOut = new T [n+1]。 // 計(jì)算MinOut = 離開頂點(diǎn)i的最小耗費(fèi)邊的耗費(fèi) T MinSum = 0。 // 離開頂點(diǎn)i的最小耗費(fèi)邊的數(shù)目 for (int i = 1。 i = n。 i++) { T Min = NoEdge。 for (int j = 1。 j = n。 j++) if (a[j] != NoEdge amp。amp。 (a[j] Min || Min == NoEdge)) Min = a[j]。 if (Min == NoEdge) return NoEdge。 // 此路不通 MinOut = Min。 MinSum += Min。 } MinHeapNode E。 // 把E節(jié)點(diǎn)初始化為樹根 = new int [n]。 for (i = 0。 i n。 i++) = i + 1。 = 0。 // 局部旅行路徑為x [ 1 : 0 ] = 0。 // 其耗費(fèi)為0 = MinSum。 T bestc = NoEdge。 // 目前沒有找到旅行路徑 // 搜索排列樹 while ( n 1) { if ( == n 2) // 不是葉子{// 葉子的父節(jié)點(diǎn) // 通過添加兩條邊來完成旅行 // 檢查新的旅行路徑是不是更好 if (a[[n2]][[n1]] != NoEdge amp。amp。 a[[n1]][1] != NoEdge amp。amp。 ( + a[[n2]][[n1]] + a[[n1]][1] bestc || bestc == NoEdge)) { // 找到更優(yōu)的旅行路徑 bestc = + a[[n2]][[n1]] + a[E。x[n1]][1]。 = bestc。 = bestc。 + + 。 n s e r t ( E ) 。 } else delete [] 。} else {// 產(chǎn)生孩子 for (int i = + 1。 i n。 i++) if (a[[]][E,x] != NoEdge) { // 可行的孩子， 限定了路徑的耗費(fèi) T cc = + a[[]][]。 T rcost = MinOut[[]]。 T b = cc + rcost。 //下限 if (b bestc || bestc == NoEdge) { // 子樹可能有更好的葉子 // 把根保存到最大堆中 MinHeapNode N。 N。x = new int [n]。 for (int j = 0。 j n。 j++) [j] = [j]。 [+1] = 。 = [+1]。 = cc。 = + 1。 = b。 = rcost。 n s e r t ( N ) 。 } } // 結(jié)束可行的孩子 delete [] E。x。} // 對(duì)本節(jié)點(diǎn)的處理結(jié)束 try {H。DeleteMin(E)。} // 取下一個(gè)E節(jié)點(diǎn) catch (OutOfBounds) {break。} // 沒有未處理的節(jié)點(diǎn) } if (bestc == NoEdge) return NoEdge。 // 沒有旅行路徑 // 將最優(yōu)路徑復(fù)制到v[1:n] 中 for (i = 0。 i n。 i++) v[i+1] = 。 while (true) {//釋放最小堆中的所有節(jié)點(diǎn) delete ()。 try {(E)。} catch (OutOfBounds) {break。} } return bestc。 } 附錄Ｂ　旅行售貨員問題的回溯法templateclass Traveling {　friend Type TSP(int * *，int []，Type)?！rivate:　void Backtrack(int i)?！nt n。 //圖G的頂點(diǎn)數(shù) 　* x。 //當(dāng)前解　*bestx。 //當(dāng)前最優(yōu)解　Type * *a。 //圖G的鄰接矩陣　Cc。//當(dāng)前費(fèi)用　Bestc。 //當(dāng)前最優(yōu)值　NoEdge。 //無邊際記　}。templatevode Traveling::Backtrack(int i){　if(I==n){　　if(a[x[n1]][x[n]]! = NoEdge amp。amp?！　[x[n]][1]!= NoEdge amp。amp?！　?cc + a[x[n1]][x[n]]+a[x[n]][1]bestc== NoEdge) ){　　for(int j=1。j=n。j++)　　bestx[j]=x[j]?！　estc =cc + a[x[n1]][x[n]]+ a[x[n]][1]。}　}　else {　　for(int j=I。 j=n。j++)　//是否可進(jìn)入x[j]子樹 　　　if(a[x[i1]][x[j]]! = NoEdge amp。amp。(cc + a[x[i1]][x[i]] bestc||bestc == NoEdge)　　　　//搜索子數(shù)　　　　Swap(x[i]，x[j])。　　cc += a[x[i1]][x[i]]?！　acktrack(I+1)。　　cc = a[x[i1]][x[i]]。　　Swap(x[i]，x[j])。}　　}}templateType TSP(Type * *a，int v[]，int n，Type NoEdge){　Traveling Y。//初始化Y = new int[n+1]。 // 置x為單位排列for(int i=1。i=n。i++)[i] = I。=a。=n。 = NoEdge。 = v。 = 0。 = NoEdge。//搜索x[2:n]的全排列(2)。Delete()。