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