1、-. z.旅行商問(wèn)題的求解方法摘要旅行商問(wèn)題TSP問(wèn)題時(shí)是指旅行家要旅行n個(gè)城市然后回到出發(fā)城市，要求各個(gè)城市經(jīng)歷且僅經(jīng)歷一次，并要求所走的路程最短。該問(wèn)題又稱(chēng)為貨郎擔(dān)問(wèn)題、郵遞員問(wèn)題、售貨員問(wèn)題，是圖問(wèn)題中最廣為人知的問(wèn)題。本文主要介紹用蠻力法、動(dòng)態(tài)規(guī)劃法、貪心法和分支限界法求解TSP問(wèn)題，其中重點(diǎn)討論動(dòng)態(tài)規(guī)劃法和貪心法，并給出相應(yīng)求解程序。關(guān)鍵字：旅行商問(wèn)題；動(dòng)態(tài)規(guī)劃法；貪心法；分支限界法1引言旅行商問(wèn)題(TSP)是組合優(yōu)化問(wèn)題中典型的NP-完全問(wèn)題，是許多領(lǐng)域內(nèi)復(fù)雜工程優(yōu)化問(wèn)題的抽象形式。研究TSP的求解方法對(duì)解決復(fù)雜工程優(yōu)化問(wèn)題具有重要的參考價(jià)值。關(guān)于TSP的完全有效的算法目前尚未找到

2、，這促使人們長(zhǎng)期以來(lái)不斷地探索并積累了大量的算法。歸納起來(lái)，目前主要算法可分成傳統(tǒng)優(yōu)化算法和現(xiàn)代優(yōu)化算法。在傳統(tǒng)優(yōu)化算法中又可分為：最優(yōu)解算法和近似方法。最優(yōu)解算法雖然可以得到準(zhǔn)確解，但計(jì)算時(shí)間無(wú)法忍受，因此就產(chǎn)生了各種近似方法，這些近似算法雖然可以較快地求得接近最優(yōu)解的可行解，但其接近最優(yōu)解的程度不能令人滿意。但限于所學(xué)知識(shí)和時(shí)間限制，本文重點(diǎn)只討論傳統(tǒng)優(yōu)化算法中的動(dòng)態(tài)規(guī)劃法、貪心法和分支限界法，并對(duì)蠻力法做簡(jiǎn)單介紹，用以比擬。2正文2.1蠻力法蠻力法的設(shè)計(jì)思想蠻力法所依賴的根本技術(shù)是掃描技術(shù)，即采用一定的策略將待求解問(wèn)題的所有元素一次處理一次，從而找出問(wèn)題的解。一次處理所有元素的是蠻力法的

3、關(guān)鍵，為了防止陷入重復(fù)試探，應(yīng)保證處理過(guò)的元素不再被處理。在根本的數(shù)據(jù)構(gòu)造中，一次處理每個(gè)元素的方法是遍歷。算法討論用蠻力法解決TSP問(wèn)題，可以找出所有可能的旅行路線，從中選取路徑長(zhǎng)度最短的簡(jiǎn)單回路。如對(duì)于圖1，我們求解過(guò)程如下：路徑：1-2-3-4-1；路徑長(zhǎng)度：18；路徑：1-2-4-3-1；路徑長(zhǎng)度：11；路徑：1-3-2-4-1；路徑長(zhǎng)度：23；路徑：1-3-4-2-1；路徑長(zhǎng)度：11；路徑：1-4-2-3-1；路徑長(zhǎng)度：18；路徑：1-4-3-2-1；路徑長(zhǎng)度：18；從中，我們可以知道，路徑2和4路徑長(zhǎng)度最短。我們還應(yīng)注意到，圖1中，有3對(duì)不同的路徑，對(duì)每對(duì)路徑來(lái)說(shuō)，不同只是路徑的方

4、向，因此，可以將這個(gè)數(shù)量減半，則可能的解有n-1！/2個(gè)。這是一個(gè)非常大的數(shù)，隨著n的增長(zhǎng)，TSP問(wèn)題的可能解也在迅速增長(zhǎng)。如：一個(gè)10城市的TSP問(wèn)題有大約有180,000個(gè)可能解。一個(gè)20城市的TSP問(wèn)題有大約有60,000,000,000,000,000個(gè)可能解。 一個(gè)50城市的TSP問(wèn)題有大約1062個(gè)可能解，而一個(gè)行星上也只有1021升水。因此，我們可以知道用蠻力法求解TSP問(wèn)題，只能解決問(wèn)題規(guī)模很小的實(shí)例。2.2動(dòng)態(tài)規(guī)劃法動(dòng)態(tài)規(guī)劃法的設(shè)計(jì)思想動(dòng)態(tài)規(guī)劃法將待求解問(wèn)題分解成假設(shè)干個(gè)相互重疊的子問(wèn)題，每個(gè)子問(wèn)題對(duì)應(yīng)決策過(guò)程的一個(gè)階段，一般來(lái)說(shuō)，子問(wèn)題的重疊關(guān)系表現(xiàn)在對(duì)給定問(wèn)題求解的遞推關(guān)

5、系也就是動(dòng)態(tài)規(guī)劃函數(shù)中，將子問(wèn)題的解求解一次并填入表中，當(dāng)需要再次求解此子問(wèn)題時(shí)，可以通過(guò)查表獲得該子問(wèn)題的解而不用再次求解，從而防止了大量重復(fù)計(jì)算。TSP問(wèn)題的動(dòng)態(tài)規(guī)劃函數(shù)假設(shè)從頂點(diǎn)i出發(fā)，令表示從頂點(diǎn)i出發(fā)經(jīng)過(guò)中各個(gè)頂點(diǎn)一次且僅一次，最后回到出發(fā)點(diǎn)i的最短路徑長(zhǎng)度，開(kāi)場(chǎng)時(shí)，于是，TSP問(wèn)題的動(dòng)態(tài)規(guī)劃函數(shù)為：算法討論1for (i=1; iN; i+) /初始化第0列 di0=ci0; 2for (j=1; j -1; j+) for (i=1; in; i+) /依次進(jìn)展第i次迭代 if (子集Vj中不包含i) 對(duì)Vj中的每個(gè)元素k，計(jì)算Vm = Vj-k;dij=min(cik+dkm)

6、; 3對(duì)V -1中的每一個(gè)元素k，計(jì)算Vm = V -1-k;d0 -1=min(c0k+dkm); 4輸出最短路徑長(zhǎng)度d0 -1;時(shí)間復(fù)雜性和蠻力法相比，動(dòng)態(tài)規(guī)劃法求解TSP問(wèn)題，把原來(lái)的時(shí)間復(fù)雜性是O(n!)的排列問(wèn)題，轉(zhuǎn)化為組合問(wèn)題，從而降低了算法的時(shí)間復(fù)雜性，但它仍需要指數(shù)時(shí)間。2.3貪心法貪心法的設(shè)計(jì)思想貪心法在解決問(wèn)題的策略上目光短淺，只根據(jù)當(dāng)前已有的信息就做出選擇，而且一旦做出了選擇，不管將來(lái)有什么結(jié)果，這個(gè)選擇都不會(huì)改變。換言之，貪心法并不是從整體最優(yōu)考慮，它所做出的選擇只是在*種意義上的局部最優(yōu)。這種局部最優(yōu)選擇并不總能獲得整體最優(yōu)解，但通常能獲得近似最優(yōu)解。最近鄰點(diǎn)策略求解

7、TSP問(wèn)題貪心法求解TSP問(wèn)題的貪心策略是顯然的，至少有兩種貪心策略是合理的：最近鄰點(diǎn)策略和最短策略。本文僅重點(diǎn)討論最近鄰點(diǎn)策略及其求解過(guò)程。最近鄰點(diǎn)策略：從任意城市出發(fā)，每次在沒(méi)有到過(guò)的城市中選擇距離已選擇的城市中最近的一個(gè)，直到經(jīng)過(guò)了所有的城市，最后回到出發(fā)城市。算法討論1P= ; 2V=V-u0; u=u0; /從頂點(diǎn)u0出發(fā)3循環(huán)直到集合P中包含n-1條邊 3.1查找與頂點(diǎn)u鄰接的最小代價(jià)邊(u, v)并且v屬于集合V； 3.2 P=P+(u, v); 3.3 V=V-v; 3.4 u=v; /從頂點(diǎn)v出發(fā)繼續(xù)求解時(shí)間復(fù)雜性但需注意，用最近鄰點(diǎn)貪心策略求解TSP問(wèn)題所得的結(jié)果不一定是最

8、優(yōu)解。當(dāng)圖中頂點(diǎn)個(gè)數(shù)較多并且各邊的代價(jià)值分布比擬均勻時(shí)，最近鄰點(diǎn)策略可以給出較好的近似解，不過(guò)，這個(gè)近似解以何種程度近似于最優(yōu)解，卻難以保證。2.4分支限界法分支限界法的設(shè)計(jì)思想 假設(shè)求解最大化問(wèn)題，解向量為，其中，的取值*圍為*個(gè)有窮集合，。在使用分支限界法搜索問(wèn)題的解空間樹(shù)時(shí)，首先根據(jù)限界函數(shù)估算目標(biāo)函數(shù)的界down, up，然后從根結(jié)點(diǎn)出發(fā)，擴(kuò)展根結(jié)點(diǎn)的個(gè)孩子結(jié)點(diǎn)，從而構(gòu)成分量的種可能的取值方式。對(duì)這個(gè)孩子結(jié)點(diǎn)分別估算可能取得的目標(biāo)函數(shù)值，其含義是以該孩子結(jié)點(diǎn)為根的子樹(shù)所可能取得的目標(biāo)函數(shù)值不大于，也就是局部解應(yīng)滿足： 本文本欲詳細(xì)討論該算法，但無(wú)奈在編程問(wèn)題中，尚有問(wèn)題有待解決，時(shí)間所

9、限，不得已放棄。本人編程過(guò)程中所用算法思想與教師課上所教略有不同，在尋找下界時(shí)，是首先把每個(gè)結(jié)點(diǎn)所能到達(dá)的各個(gè)結(jié)點(diǎn)及其可能的路徑算出來(lái)，并添加到PT表中，但最后，不知是何原因，在還有一個(gè)城市尚未參加時(shí)，PT表的添加出現(xiàn)了問(wèn)題，思忖良久，仍未解決，時(shí)間所限，迫不得已，留待以后有時(shí)間再另行研究，本文就只給出動(dòng)態(tài)規(guī)劃法和貪心法的具體求解過(guò)程。3結(jié)論本文主要重點(diǎn)討論了動(dòng)態(tài)規(guī)劃法和貪心法求解TSP問(wèn)題算法，并附錄給出了相應(yīng)程序。3.1動(dòng)態(tài)規(guī)劃法思想動(dòng)態(tài)規(guī)劃法中對(duì)于頂點(diǎn)元素生成的子集本文中用字符串形式存儲(chǔ)，然后再用遞歸方法按照子集中元素個(gè)數(shù)從小到大開(kāi)場(chǎng)賦值。因?yàn)楹竺嬖貍€(gè)數(shù)較多的子集與前面比其元素個(gè)數(shù)少1

10、的子集間有一定對(duì)應(yīng)關(guān)系，所以用遞歸方式，可以簡(jiǎn)便很多。個(gè)人覺(jué)得這算本文的一大特色。另，在計(jì)算dij =min(cik+dkj-1)時(shí)，獲得dkj-1的過(guò)程比擬困難，運(yùn)用字符串后，我們就可以首先找到指定字符，然后去掉該字符，返回剩余字符串，在與V逐個(gè)比擬，找到與其相等的V中元素對(duì)應(yīng)下標(biāo)，此下標(biāo)即為j-1；具體求解過(guò)程可參考附錄源程序，有詳細(xì)說(shuō)明。在求解最正確路徑所經(jīng)過(guò)城市順序時(shí)，本文是通過(guò)邊查找dij邊記錄路徑的，這樣可以省掉很多麻煩，另，路徑也是采用字符串形式的數(shù)組，數(shù)組規(guī)模與存儲(chǔ)城市間距離的c數(shù)組一樣，由于很多元素均不需賦值，這樣做可能會(huì)浪費(fèi)內(nèi)存空間，但是目前還沒(méi)找到更好地求解方法。3.2貪

11、心法思想貪心法中，由于貪心法相對(duì)動(dòng)態(tài)規(guī)劃法要簡(jiǎn)單很多，每次在查找最近城市時(shí)所得的頂點(diǎn)均為最后該法最正確路徑所經(jīng)過(guò)的城市編號(hào)，規(guī)模相對(duì)較小，容易確定，操作相對(duì)簡(jiǎn)單，所以本文用數(shù)組V存放最正確路徑所經(jīng)過(guò)的城市編號(hào)順序相對(duì)來(lái)說(shuō)方便很多。另外，本文用path整型數(shù)組存放所經(jīng)路徑的長(zhǎng)度，最后相加即可得最短路徑。3.3兩者比擬動(dòng)態(tài)規(guī)劃法相對(duì)貪心法來(lái)說(shuō)雖然要準(zhǔn)確些，但代碼相對(duì)繁雜很多，對(duì)時(shí)間和空間要求很多，僅適用于城市數(shù)量較小的情況。貪心法雖然比擬簡(jiǎn)單，實(shí)現(xiàn)起來(lái)比擬容易，但不是很準(zhǔn)確，當(dāng)圖中頂點(diǎn)個(gè)數(shù)較多并且各邊的代價(jià)值分布比擬均勻時(shí)，貪心法可以給出較好的近似解，不過(guò)，這個(gè)近似解以何種程度近似于最優(yōu)解，卻難以

12、保證。另外，動(dòng)態(tài)規(guī)劃法有一個(gè)明顯的缺點(diǎn)，就是出發(fā)城市只能是第0個(gè)城市城市從0開(kāi)場(chǎng)編號(hào)，假設(shè)出發(fā)城市改變，則必須以該城市為第0個(gè)城市順序給其他城市編號(hào)，輸入城市間距離。由于假設(shè)出發(fā)城市任意，編碼的難度大大增加，所以最后不得已放棄，但這大大地限制了程序的通用性。而對(duì)于貪心法，本文很好地防止了這個(gè)問(wèn)題，一旦城市編號(hào)確定，可以從任意城市出發(fā)，這也是本文中貪心法優(yōu)于動(dòng)態(tài)規(guī)劃法的一點(diǎn)。3.4優(yōu)點(diǎn)本文程序優(yōu)點(diǎn)，各個(gè)子函數(shù)功能分隔很明顯，沒(méi)有大量集中在一個(gè)函數(shù)里面，而是分成了幾個(gè)不同功能的小函數(shù)，這樣程序可閱讀性提高。另外，程序中有詳細(xì)注釋?zhuān)绦蛑凶兞咳∶际歉鶕?jù)變量的性質(zhì)和所代表的含義命名的，也相應(yīng)提高了程

13、序的可讀性。對(duì)于動(dòng)態(tài)規(guī)劃法，城市個(gè)數(shù)可以在算法時(shí)間允許的*圍內(nèi)任意，于這點(diǎn)來(lái)說(shuō)，通用性較好；對(duì)于貪心法，出發(fā)城市可以任意，城市個(gè)數(shù)也可以任意，通用性較好。4建議當(dāng)城市個(gè)數(shù)較少時(shí)，用動(dòng)態(tài)規(guī)劃法求出最優(yōu)解；當(dāng)城市個(gè)數(shù)較多并且各邊的代價(jià)值分布比擬均勻時(shí)，貪心法可以給出較好的近似解。5參考文獻(xiàn)1計(jì)算機(jī)算法分析與設(shè)計(jì)第二版，王曉東編著，電子工業(yè)2Java語(yǔ)言與面向?qū)ο蟪绦蛟O(shè)計(jì)第2版印旻、王行言編著，清華大學(xué)3求解TSP算法，周康、強(qiáng)小利、同小軍、許進(jìn)，計(jì)算機(jī)工程與應(yīng)用6附錄6.1動(dòng)態(tài)規(guī)劃法源代碼package e*p2;import java.util.Scanner;publicclass TSPDy

14、namic String V;/頂點(diǎn)生成的子集，這里把每一個(gè)子集用一個(gè)字符串表示int c;/頂點(diǎn)間距離int d;/存放迭代結(jié)果intN; /城市個(gè)數(shù)String path;/用于存放每種選擇下經(jīng)過(guò)的城市staticintIFINITE = 99999;/無(wú)窮大距離 表示城市自己到達(dá)自己時(shí)，距離無(wú)窮大，不作為考慮因素/構(gòu)造函數(shù)public TSPDynamic()initialC();initialV1();/初始化數(shù)組c，即頂點(diǎn)間距離publicvoid initialC()Scanner in = new Scanner( System.in );System.out.println(請(qǐng)

15、輸入城市個(gè)數(shù)： 注意根據(jù)實(shí)際情況城市個(gè)數(shù)不可小于1！);N = in.ne*tInt();if(N = 1) System.out.println(不符合要求，請(qǐng)認(rèn)真核對(duì)！); System.e*it(0);/輸入錯(cuò)誤，完畢！ System.out.println(請(qǐng)輸入城市相鄰城市間距離城市從0開(kāi)場(chǎng)編號(hào)，且出發(fā)城市為第0個(gè)城市?。?);c = newintNN;/為c分配空間for(int i = 0 ; i N ; i +)for(int j = 0 ; j (int)Math.pow(2,N-1) - 1)return;/如果全部頂點(diǎn)已初始化完成，則返回。if(m = 0)Vm + =

16、;/初始化出發(fā)頂點(diǎn)，即V0elseint i = m - 1;while(i = 0 & Vi.length() = len)/找與最后一個(gè)初始化的Vm-1子集內(nèi)元素個(gè)數(shù)一樣的集合，把指針i指向滿足條件的集合i -;i +;/把指針i指向滿足條件的第一個(gè)集合while(i m)int ch;/用于表示下一個(gè)即將參加子集的數(shù)字if(i = 0)ch = 0;/如果i指向V中第一個(gè)元素elseString chStr = + Vi.charAt(Vi.length() - 1);/找出Vi中最后一個(gè)數(shù)字ch = Integer.parseInt(chStr);/轉(zhuǎn)換成整型/比ch大而又比N-1(因

17、為這里頂點(diǎn)是從0開(kāi)場(chǎng)的)小的數(shù)字應(yīng)該加在子集中while(ch N - 1)Vm + = Vi + (+ ch);i +;/對(duì)已存在的自己逐個(gè)掃描添加initialV(m,Vm - 1.length();/遞歸調(diào)用/判斷自己Vj中是否存在指定元素，即行號(hào)iboolean e*clude(int i , int j)String str = + i;/把i轉(zhuǎn)換成字符串if(Vj.contains(str)/System.out.println(i + i);returnfalse;/如假設(shè)存在，則返回falseelsereturntrue;/獲得子集Vj中除指定元素k外的元素，用字符串形式表示p

18、ublic String getSubString(int k , int j)if(Vj.length() = 1)return;/如果子集中只有一個(gè)元素，則返回空串elseif(k = 0) returnVj.substring(1,Vj.length();/如果k是第一個(gè)元素，則返回其后面的元素elseif(k = Vj.length() - 1) returnVj.substring(0, Vj.length()-1);/如果k是最后一個(gè)元素，則返回其前面的元素elsereturn (Vj.substring(0, k) + Vj.substring(k+1, Vj.length();

19、/返回除k外的元素/找出V中與str一樣元素的下標(biāo)號(hào),即找出上一個(gè)子集publicint stringEqual(String str)/if(str.equals()return 0;int i = 0;while(i V.length)if(Vi.equals(str)return i;i +;return -1;/如假設(shè)沒(méi)找到，則返回錯(cuò)誤符號(hào)-1/求最小距離publicint min(int i , int j)int k = 0;/用于記錄Vj中元素個(gè)數(shù)String vStr = + Vj.charAt(k);/銘記Vj.charAt(k)得到的是字符型，轉(zhuǎn)換成整形后是字母對(duì)應(yīng)的ASC

20、碼！int v = Integer.parseInt(vStr);/把位置k處的字符轉(zhuǎn)換成整形String str = getSubString(k,j);/獲得Vj中除位置k處外的字符串/System.out.println(min + str + stringEqual(str) + v);if(stringEqual(str) = -1)System.e*it(0);int min = civ + dvstringEqual(str);/先把最小的距離賦值給從Vj中第一個(gè)頂點(diǎn)出發(fā)的距離/System.out.println(min); /stringEqual(str)表示返回與上面獲得

21、的字符串一樣的V中元素的下標(biāo)，即找上一個(gè)子集pathij = pathvstringEqual(str) + i;k +;/尋找最小距離while(k civ + dvstringEqual(str)min = civ + dvstringEqual(str);pathij = pathvstringEqual(str) + i;k +;/Vj.substring(beginInde*, endInde*)/System.out.println(pathij);return min;/返回最小值/處理函數(shù)publicvoid dynamic()d = newintN(int)Math.pow(

22、2,N-1);/分配空間path = new StringN(int)Math.pow(2,N-1);for(int i = 1 ; i N ; i +)/初始化第一列di0 = ci0;pathi0 = 0 + i;/初始化第一個(gè)元素，即為出發(fā)城市頂點(diǎn)/System.out.print(di0 + );/初始化后面的元素int j = 1;for( ; j (int)Math.pow(2,N-1) -1 ; j +)for(int i = 1 ; i N ; i +)if(e*clude(i,j)/判斷V子集中是否包含當(dāng)前頂點(diǎn)，即Vj中是否包含i/System.out.println(don

23、e！ + i + + j);dij = min(i , j);/尋找最小距離d0j = min(0,j);/初始化組后一列/輸出中間結(jié)果，各個(gè)數(shù)組，用于調(diào)試程序publicvoid print()for(int i = 0 ; i (int)Math.pow(2,N-1) ; i +)System.out.print(Vi + );/for(int i = 0 ; i c.length ; )System.out.println();for(int i = 0 ; i N ; i +)for(int j = 0 ; j N ; j +)System.out.print(cij + );Syst

24、em.out.println();for(int i = 0 ; i N ; i +)for(int j = 0 ; j = 0 ; i -)System.out.print(- + str.charAt(i);System.out.println(會(huì)有最短路徑);System.out.println(最短路徑為： + d0(int)Math.pow(2,N-1) - 1);/主函數(shù)publicstaticvoid main(String args) TSPDynamic TSP = new TSPDynamic();TSP.dynamic();/求最短路徑/TSP.print();TSP.p

25、rintShortestPath();/輸出最短路徑/測(cè)試數(shù)據(jù)/*99999 3 6 75 99999 2 36 4 99999 23 7 5 99999 */結(jié)果12346.2貪心法源代碼package e*p2;import java.util.Scanner;publicclassTSPGreedNode int V;/存放旅行所經(jīng)過(guò)的城市頂點(diǎn)int c;/存放每?jī)勺鞘虚g的距離，注意：假設(shè)路徑不存在或同一城市間距離為無(wú)窮大int path;/存放旅行所經(jīng)過(guò)的每?jī)勺鞘虚g的距離intN;/城市個(gè)數(shù)intshortestPath;/表示最短路徑intu0;/出發(fā)城市編號(hào)staticintI

26、FINITE = 99999;/無(wú)窮大距離 表示城市自己到達(dá)自己時(shí)，距離無(wú)窮大，不作為考慮因素public TSPGreedNode ()initialC();/得到最短路徑publicint getShortestPath()for(int i = 0 ; i N ; i +)shortestPath += pathi;returnshortestPath;/初始化數(shù)組c，即頂點(diǎn)間距離publicvoid initialC()Scanner in = new Scanner( System.in );System.out.println(請(qǐng)輸入城市個(gè)數(shù)： 注意根據(jù)實(shí)際情況城市個(gè)數(shù)不可小于1！);N = in.ne*tInt();if(N = 1) System.out.println(不符合要求，請(qǐng)認(rèn)真核對(duì)！); System.e*it(0);/輸入錯(cuò)誤，完畢！ System.out.println(請(qǐng)輸入城市相鄰城市間距離城市從0開(kāi)場(chǎng)編號(hào)，且出發(fā)城市為第0個(gè)城市?。?);c = newintNN;/為c分配空間for(int i = 0 ; i N ; i +)for(int j = 0 ; j N ; j +)cij = in.ne*tInt(); /輸入時(shí)，按城市