算法論文：旅行商問題的求解方法(動態(tài)規(guī)劃法和貪心法)

旅行商問題的求解方法摘要旅行商問題（TSP問題）時是指旅行家要旅行n個城市然后回到出發(fā)城市，要求各個城市經(jīng)歷且僅經(jīng)歷一次，并要求所走的路程最短。該問題又稱為貨郎擔(dān)問題、郵遞員問題、售貨員問題，是圖問題中最廣為人知的問題。本文主要介紹用蠻力法、動態(tài)規(guī)劃法、貪心法和分支限界法求解TSP問題，其中重點討論動態(tài)規(guī)劃法和貪心法，并給出相應(yīng)求解程序。關(guān)鍵字：旅行商問題；動態(tài)規(guī)劃法；貪心法；分支限界法1引言旅行商問題(TSP)是組合優(yōu)化問題中典型的NP-完全問題，是許多領(lǐng)域內(nèi)復(fù)雜工程優(yōu)化問題的抽象形式。研究TSP的求解方法對解決復(fù)雜工程優(yōu)化問題具有重要的參考價值。關(guān)于TSP的完全有效的算法目前尚未找到，這促使人們長期以來不斷地探索并積累了大量的算法。歸納起來，目前主要算法可分成傳統(tǒng)優(yōu)化算法和現(xiàn)代優(yōu)化算法。在傳統(tǒng)優(yōu)化算法中又可分為：最優(yōu)解算法和近似方法。最優(yōu)解算法雖然可以得到精確解，但計算時間無法忍受，因此就產(chǎn)生了各種近似方法，這些近似算法雖然可以較快地求得接近最優(yōu)解的可行解，但其接近最優(yōu)解的程度不能令人滿意。但限于所學(xué)知識和時間限制，本文重點只討論傳統(tǒng)優(yōu)化算法中的動態(tài)規(guī)劃法、貪心法和分支限界法，并對蠻力法做簡單介紹，用以比較。2正文2.1蠻力法2.1.1蠻力法的設(shè)計思想蠻力法所依賴的基本技術(shù)是掃描技術(shù)，即采用一定的策略將待求解問題的所有元素一次處理一次，從而找出問題的解。一次處理所有元素的是蠻力法的關(guān)鍵，為了避免陷入重復(fù)試探，應(yīng)保證處理過的元素不再被處理。在基本的數(shù)據(jù)結(jié)構(gòu)中，一次處理每個元素的方法是遍歷。2.1.2算法討論用蠻力法解決TSP問題，可以找出所有可能的旅行路線，從中選取路徑長度最短的簡單回路。如對于圖1，我們求解過程如下：路徑：1->2->3->4->1；路徑長度：18；路徑：1->2->4->3->1；路徑長度：11；路徑：1->3->2->4->1；路徑長度：23；路徑：1->3->4->2->1；路徑長度：11；路徑：1->4->2->3->1；路徑長度：18；路徑：1->4->3->2->1；路徑長度：18；從中，我們可以知道，路徑（2）和（4）路徑長度最短。我們還應(yīng)注意到，圖1中，有3對不同的路徑，對每對路徑來說，不同只是路徑的方向，因此，可以將這個數(shù)量減半，則可能的解有（n-1）！/2個。這是一個非常大的數(shù)，隨著n的增長，TSP問題的可能解也在迅速增長。如：一個10城市的TSP問題有大約有180,000個可能解。一個20城市的TSP問題有大約有60,000,000,000,000,000個可能解。一個50城市的TSP問題有大約1062個可能解，而一個行星上也只有1021升水。因此，我們可以知道用蠻力法求解TSP問題，只能解決問題規(guī)模很小的實例。

2.2動態(tài)規(guī)劃法2.2.1動態(tài)規(guī)劃法的設(shè)計思想動態(tài)規(guī)劃法將待求解問題分解成若干個相互重疊的子問題，每個子問題對應(yīng)決策過程的一個階段，一般來說，子問題的重疊關(guān)系表現(xiàn)在對給定問題求解的遞推關(guān)系（也就是動態(tài)規(guī)劃函數(shù)）中，將子問題的解求解一次并填入表中，當(dāng)需要再次求解此子問題時，可以通過查表獲得該子問題的解而不用再次求解，從而避免了大量重復(fù)計算。2.2.2TSP問題的動態(tài)規(guī)劃函數(shù)假設(shè)從頂點i出發(fā)，令表示從頂點i出發(fā)經(jīng)過中各個頂點一次且僅一次，最后回到出發(fā)點i的最短路徑長度，開始時，，于是，TSP問題的動態(tài)規(guī)劃函數(shù)為：

2.2.3算法討論（1）for(i=1;i<N;i++)//初始化第0列d[i][0]=c[i][0];（2）for(j=1;j<-1;j++)for(i=1;i<n;i++)//依次進行第i次迭代if(子集V[j]中不包含i)對V[j]中的每個元素k，計算V[m]==V[j]-k;d[i][j]=min(c[i][k]+d[k][m]);（3）對V[-1]中的每一個元素k，計算V[m]==V[-1]-k;d[0][-1]=min(c[0][k]+d[k][m]);（4）輸出最短路徑長度d[0][-1];2.3.4時間復(fù)雜性3.4優(yōu)點本文程序優(yōu)點，各個子函數(shù)功能分隔很明顯，沒有大量集中在一個函數(shù)里面，而是分成了幾個不同功能的小函數(shù)，這樣程序可閱讀性提高。另外，程序中有詳細注釋，程序中變量取名都是根據(jù)變量的性質(zhì)和所代表的含義命名的，也相應(yīng)提高了程序的可讀性。對于動態(tài)規(guī)劃法，城市個數(shù)可以在算法時間允許的范圍內(nèi)任意，于這點來說，通用性較好；對于貪心法，出發(fā)城市可以任意，城市個數(shù)也可以任意，通用性較好。4建議當(dāng)城市個數(shù)較少時，用動態(tài)規(guī)劃法求出最優(yōu)解；當(dāng)城市個數(shù)較多并且各邊的代價值分布比較均勻時，貪心法可以給出較好的近似解。5參考文獻（1）《計算機算法分析與設(shè)計》第二版，王曉東編著，電子工業(yè)出版社（2）Java語言與面向?qū)ο蟪绦蛟O(shè)計（第2版）印旻、王行言編著，清華大學(xué)出版社（3）求解TSP算法，周康、強小利、同小軍、許進，計算機工程與應(yīng)用6附錄6.1動態(tài)規(guī)劃法6.1.1源代碼packageexp2;importjava.util.Scanner;publicclassTSPDynamic{ String[]V;//頂點生成的子集，這里把每一個子集用一個字符串表示 int[][]c;//頂點間距離 int[][]d;//存放迭代結(jié)果 intN;//城市個數(shù) String[][]path;//用于存放每種選擇下經(jīng)過的城市 staticintIFINITE=99999;//無窮大距離表示城市自己到達自己時，距離無窮大，不作為考慮因素 //構(gòu)造函數(shù) publicTSPDynamic(){ initialC(); initialV1(); } //初始化數(shù)組c[]，即頂點間距離 publicvoidinitialC(){ Scannerin=newScanner(System.in); System.out.println("請輸入城市個數(shù)：（注意根據(jù)實際情況城市個數(shù)不可小于1?。?); N=in.nextInt(); if(N<=1){ System.out.println("不符合要求，請認真核對！"); System.exit(0);//輸入錯誤，結(jié)束！ } System.out.println("請輸入城市相鄰城市間距離（城市從0開始編號，且出發(fā)城市為第0個城市！）："); c=newint[N][N];//為c分配空間 for(inti=0;i<N;i++) for(intj=0;j<N;j++){ c[i][j]=in.nextInt();//輸入時，按城市編號從小到大，如若兩城市間沒有公路相連，則距離為無窮大。本城市與本城市間距離也為無窮大。 } } //初始化頂點生成的子集的對外調(diào)用函數(shù) publicvoidinitialV1(){ V=newString[(int)Math.pow(2,N-1)];//為V分配空間 initialV(0,0); } //具體的初始化頂點生成的子集 //本程序使用遞歸調(diào)用方法初始化V，并按照數(shù)字大小順序排序。。另，子集使用字符型形式存放的 //我們是按照子集中元素個數(shù)從小到大逐個添加的，后面的子集是前面對應(yīng)子集加上一個元素組成的，故用遞歸 publicvoidinitialV(intm,intlen) {//m代表下一個即將初始化的V數(shù)組的元素的下標(biāo)；len是最后一個初始化的元素的長度 if(m>(int)Math.pow(2,N-1)-1)return;//如果全部頂點已初始化完成，則返回。 if(m==0)V[m++]="";//初始化出發(fā)頂點，即V[0] else{ inti=m-1; while(i>=0&&V[i].length()==len)//找與最后一個初始化的V[m-1]子集內(nèi)元素個數(shù)相同的集合，把指針i指向滿足條件的集合 i--; i++;//把指針i指向滿足條件的第一個集合 while(i<m){ intch;//用于表示下一個即將加入子集的數(shù)字 if(i==0)ch=0;//如果i指向V中第一個元素 else{ StringchStr=""+V[i].charAt(V[i].length()-1);//找出V[i]中最后一個數(shù)字 ch=Integer.parseInt(chStr);//轉(zhuǎn)換成整型 } //比ch大而又比N-1(因為這里頂點是從0開始的)小的數(shù)字應(yīng)該加在子集中 while(ch<N-1) V[m++]=V[i]+(++ch); i++;//對已存在的自己逐個掃描添加 } } initialV(m,V[m-1].length());//遞歸調(diào)用 } //判斷自己V[j]中是否存在指定元素，即行號i booleanexclude(inti,intj){ Stringstr=""+i;//把i轉(zhuǎn)換成字符串 if(V[j].contains(str)) //{System.out.println(i+"i"); returnfalse;//如若存在，則返回false elsereturntrue; } //獲得子集V[j]中除指定元素k外的元素，用字符串形式表示 publicStringgetSubString(intk,intj){ if(V[j].length()==1)return"";//如果子集中只有一個元素，則返回空串 else{ if(k==0)returnV[j].substring(1,V[j].length());//如果k是第一個元素，則返回其后面的元素 elseif(k==V[j].length()-1)returnV[j].substring(0,V[j].length()-1);//如果k是最后一個元素，則返回其前面的元素 elsereturn(V[j].substring(0,k)+V[j].substring(k+1,V[j].length()));//返回除k外的元素 } } //找出V[]中與str相同元素的下標(biāo)號,即找出上一個子集 publicintstringEqual(Stringstr){ //if(str.equals(""))return0; inti=0; while(i<V.length){ if(V[i].equals(str)) returni; i++; } return-1;//如若沒找到，則返回錯誤符號-1 } //求最小距離 publicintmin(inti,intj){ intk=0;//用于記錄V[j]中元素個數(shù) StringvStr=""+V[j].charAt(k);//銘記V[j].charAt(k)得到的是字符型，轉(zhuǎn)換成整形后是字母對應(yīng)的ASC碼?。。。? intv=Integer.parseInt(vStr);//把位置k處的字符轉(zhuǎn)換成整形 Stringstr=getSubString(k,j);//獲得V[j]中除位置k處外的字符串 //System.out.println("min"+str+stringEqual(str)+v); if(stringEqual(str)==-1)System.exit(0); intmin=c[i][v]+d[v][stringEqual(str)];//先把最小的距離賦值給從V[j]中第一個頂點出發(fā)的距離 //System.out.println(min);//stringEqual(str)表示返回與上面獲得的字符串相同的V中元素的下標(biāo)，即找上一個子集 path[i][j]=path[v][stringEqual(str)]+i; k++; //尋找最小距離 while(k<V[j].length()){ vStr=""+V[j].charAt(k); v=Integer.parseInt(vStr); str=getSubString(k,j); if(min>c[i][v]+d[v][stringEqual(str)]){ min=c[i][v]+d[v][stringEqual(str)]; path[i][j]=path[v][stringEqual(str)]+i; } k++; } //V[j].substring(beginIndex,endIndex) //System.out.println(path[i][j]); returnmin;//返回最小值 } //處理函數(shù) publicvoiddynamic(){ d=newint[N][(int)Math.pow(2,N-1)];//分配空間 path=newString[N][(int)Math.pow(2,N-1)]; for(inti=1;i<N;i++){//初始化第一列 d[i][0]=c[i][0]; path[i][0]="0"+i;//初始化第一個元素，即為出發(fā)城市頂點 //System.out.print(d[i][0]+""); } //初始化后面的元素 intj=1; for(;j<(int)Math.pow(2,N-1)-1;j++) for(inti=1;i<N;i++){ if(exclude(i,j))//判斷V子集中是否包含當(dāng)前頂點，即V[j]中是否包含i { //System.out.println("done！"+i+""+j); d[i][j]=min(i,j);//尋找最小距離 } } d[0][j]=min(0,j);//初始化組后一列 } //輸出中間結(jié)果，各個數(shù)組，用于調(diào)試程序 publicvoidprint(){ for(inti=0;i<(int)Math.pow(2,N-1);i++) System.out.print(V[i]+""); //for(inti=0;i<c.length;) System.out.println(); for(inti=0;i<N;i++){ for(intj=0;j<N;j++) System.out.print(c[i][j]+""); System.out.println(); } for(inti=0;i<N;i++){ for(intj=0;j<(int)Math.pow(2,N-1);j++) System.out.print(d[i][j]+""); System.out.println(); } } //輸出最短路徑 publicvoidprintShortestPath(){ //輸出所經(jīng)城市 System.out.print("經(jīng)過城市："); Stringstr=path[0][(int)Math.pow(2,N-1)-1]; //System.out.println(str); System.out.print(str.charAt(str.length()-1)); for(inti=str.length()-2;i>=0;i--){ System.out.print("->"+str.charAt(i)); } System.out.println("會有最短路徑"); System.out.println("最短路徑為："+d[0][(int)Math.pow(2,N-1)-1]); } //主函數(shù) publicstaticvoidmain(String[]args){ TSPDynamicTSP=newTSPDynamic(); TSP.dynamic();//求最短路徑 //TSP.print(); TSP.printShortestPath();//輸出最短路徑 } }//測試數(shù)據(jù)/*99999367599999236499999237599999*/6.1.2結(jié)果（1）（2）（3）（4）6.2貪心法6.2.1源代碼packageexp2;importjava.util.Scanner;publicclassTSPGreedNode{ int[]V;//存放旅行所經(jīng)過的城市頂點 int[][]c;//存放每兩座城市間的距離，注意：若路徑不存在或同一城市間距離為無窮大 int[]path;//存放旅行所經(jīng)過的每兩座城市間的距離 intN;//城市個數(shù) intshortestPath;//表示最短路徑 intu0;//出發(fā)城市編號 staticintIFINITE=99999;//無窮大距離表示城市自己到達自己時，距離無窮大，不作為考慮因素 publicTSPGreedNode(){ initialC(); } //得到最短路徑 publicintgetShortestPath(){ for(inti=0;i<N;i++){ shortestPath+=path[i]; } returnshortestPath; } //初始化數(shù)組c[]，即頂點間距離 publicvoidinitialC(){ Scannerin=newScanner(System.in); System.out.println("請輸入城市個數(shù)：（注意根據(jù)實際情況城市個數(shù)不可小于1?。?); N=in.nextInt(); if(N<=1){ System.out.println("不符合要求，請認真核對！"); System.exit(0);//輸入錯誤，結(jié)束！ } System.out.println("請輸入城市相鄰城市間距離（城市從0開始編號，且出發(fā)城市為第0個城市?。?); c=newint[N][N];//為c分配空間 for(inti=0;i<N;i++) for(intj=0;j<N;j++){ c[i][j]=in.nextInt();//輸入時，按城市編號從小到大，如若兩城市間沒有公路相連，則距離為無窮大。本城市與本城市間距離也為無窮大。 } } publicvoidtspGreedNode(){ Scannerin=newScanner(System.in); System.out.println("請輸入出發(fā)城市編號（注意城市從0開始編號，請按照輸入城市間距離即初始化c[][]時順序計算）："); u0=in.nextInt(); V=newint[N+1]; path=newint[N]; intk=0;