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

1、旅行商問題的求解方法摘要旅行商問題（TSP問題）時(shí)是指旅行家要旅行n個(gè)城市然后回到出發(fā)城市，要求各個(gè)城市經(jīng)歷且僅經(jīng)歷一次，并要求所走的路程最短。該問題又稱為貨郎擔(dān)問題、郵遞員問題、售貨員問題，是圖問題中最廣為人知的問題。本文主要介紹用蠻力法、動態(tài)規(guī)劃法、貪心法和分支限界法求解TSP問題，其中重點(diǎn)討論動態(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)化問題具有重要的參考價(jià)值。關(guān)于TSP的完全有效的算法目前尚未找到，這促

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

3、法的關(guān)鍵，為了避免陷入重復(fù)試探，應(yīng)保證處理過的元素不再被處理。在基本的數(shù)據(jù)結(jié)構(gòu)中，一次處理每個(gè)元素的方法是遍歷。2.1.2算法討論用蠻力法解決TSP問題，可以找出所有可能的旅行路線，從中選取路徑長度最短的簡單回路。如對于圖1，我們求解過程如下：（1） 路徑：1->2->3->4->1；路徑長度：18；（2） 路徑：1->2->4->3->1；路徑長度：11；（3） 路徑：1->3->2->4->1；路徑長度：23；（4） 路徑：1->3->4->2->1；路徑長度：11；（5） 路徑：1->4

4、->2->3->1；路徑長度：18；（6） 路徑：1->4->3->2->1；路徑長度：18；從中，我們可以知道，路徑（2）和（4）路徑長度最短。我們還應(yīng)注意到，圖1中，有3對不同的路徑，對每對路徑來說，不同只是路徑的方向，因此，可以將這個(gè)數(shù)量減半，則可能的解有（n-1）！/2個(gè)。這是一個(gè)非常大的數(shù)，隨著n的增長，TSP問題的可能解也在迅速增長。如：一個(gè)10城市的TSP問題有大約有180,000個(gè)可能解。一個(gè)20城市的TSP問題有大約有60,000,000,000,000,000個(gè)可能解。 一個(gè)50城市的TSP問題有大約1062個(gè)可能解，而一個(gè)行星上也

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

6、 2.2.3算法討論（1）for (i=1; i<N; i+) /初始化第0列 di0=ci0; （2）for (j=1; j< -1; j+) for (i=1; i<n; i+) /依次進(jìn)行第i次迭代 if (子集Vj中不包含i) 對Vj中的每個(gè)元素k，計(jì)算Vm = Vj-k;dij=min(cik+dkm); （3）對V -1中的每一個(gè)元素k，計(jì)算Vm = V -1-k;d0 -1=min(c0k+dkm); （4）輸出最短路徑長度d0 -1;2.3.4時(shí)間復(fù)雜性和蠻力法相比，動態(tài)規(guī)劃法求解TSP問題，把原來的時(shí)間復(fù)雜性是O(n!)的排列問題，轉(zhuǎn)化為組合問題，從而降低了

7、算法的時(shí)間復(fù)雜性，但它仍需要指數(shù)時(shí)間。2.3貪心法2.3.1貪心法的設(shè)計(jì)思想貪心法在解決問題的策略上目光短淺，只根據(jù)當(dāng)前已有的信息就做出選擇，而且一旦做出了選擇，不管將來有什么結(jié)果，這個(gè)選擇都不會改變。換言之，貪心法并不是從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)。這種局部最優(yōu)選擇并不總能獲得整體最優(yōu)解，但通常能獲得近似最優(yōu)解。2.3.2最近鄰點(diǎn)策略求解TSP問題貪心法求解TSP問題的貪心策略是顯然的，至少有兩種貪心策略是合理的：最近鄰點(diǎn)策略和最短鏈接策略。本文僅重點(diǎn)討論最近鄰點(diǎn)策略及其求解過程。最近鄰點(diǎn)策略：從任意城市出發(fā)，每次在沒有到過的城市中選擇距離已選擇的城市中最近的一個(gè)

8、，直到經(jīng)過了所有的城市，最后回到出發(fā)城市。2.3.3算法討論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ù)求解2.3.4時(shí)間復(fù)雜性但需注意，用最近鄰點(diǎn)貪心策略求解TSP問題所得的結(jié)果不一定是最優(yōu)解。當(dāng)圖中頂點(diǎn)個(gè)數(shù)較多并且各邊的代價(jià)值分布比較均勻時(shí)，最近鄰點(diǎn)策略可以給出較好的近似解，不過，這個(gè)近似解以何種程度近似于最優(yōu)解，卻難以保證。2.4分支限界法2.4.1分支限界法的設(shè)計(jì)思想 假設(shè)求解最大化問

9、題，解向量為，其中，的取值范圍為某個(gè)有窮集合，。在使用分支限界法搜索問題的解空間樹時(shí)，首先根據(jù)限界函數(shù)估算目標(biāo)函數(shù)的界down, up，然后從根結(jié)點(diǎn)出發(fā)，擴(kuò)展根結(jié)點(diǎn)的個(gè)孩子結(jié)點(diǎn)，從而構(gòu)成分量的種可能的取值方式。對這個(gè)孩子結(jié)點(diǎn)分別估算可能取得的目標(biāo)函數(shù)值，其含義是以該孩子結(jié)點(diǎn)為根的子樹所可能取得的目標(biāo)函數(shù)值不大于，也就是部分解應(yīng)滿足： 本文本欲詳細(xì)討論該算法，但無奈在編程問題中，尚有問題有待解決，時(shí)間所限，不得已放棄。本人編程過程中所用算法思想與老師課上所教略有不同，在尋找下界時(shí)，是首先把每個(gè)結(jié)點(diǎn)所能到達(dá)的各個(gè)結(jié)點(diǎn)及其可能的路徑算出來，并添加到PT表中，但最后，不知是何原因，在還有一個(gè)城市尚未加

10、入時(shí)，PT表的添加出現(xiàn)了問題，思忖良久，仍未解決，時(shí)間所限，迫不得已，留待以后有時(shí)間再另行研究，本文就只給出動態(tài)規(guī)劃法和貪心法的具體求解過程。3結(jié)論本文主要重點(diǎn)討論了動態(tài)規(guī)劃法和貪心法求解TSP問題算法，并附錄給出了相應(yīng)程序。3.1動態(tài)規(guī)劃法思想動態(tài)規(guī)劃法中對于頂點(diǎn)元素生成的子集本文中用字符串形式存儲，然后再用遞歸方法按照子集中元素個(gè)數(shù)從小到大開始賦值。因?yàn)楹竺嬖貍€(gè)數(shù)較多的子集與前面比其元素個(gè)數(shù)少1的子集間有一定對應(yīng)關(guān)系，所以用遞歸方式，可以簡便很多。個(gè)人覺得這算本文的一大特色。另，在計(jì)算dij =min(cik+dkj-1)時(shí)，獲得dkj-1的過程比較困難，運(yùn)用字符串后，我們就可以首先找到

11、指定字符，然后去掉該字符，返回剩余字符串，在與V逐個(gè)比較，找到與其相等的V中元素對應(yīng)下標(biāo)，此下標(biāo)即為j-1；具體求解過程可參考附錄源程序，有詳細(xì)說明。在求解最佳路徑所經(jīng)過城市順序時(shí)，本文是通過邊查找dij邊記錄路徑的，這樣可以省掉很多麻煩，另，路徑也是采用字符串形式的數(shù)組，數(shù)組規(guī)模與存儲城市間距離的c數(shù)組相同，由于很多元素均不需賦值，這樣做可能會浪費(fèi)內(nèi)存空間，但是目前還沒找到更好地求解方法。3.2貪心法思想貪心法中，由于貪心法相對動態(tài)規(guī)劃法要簡單很多，每次在查找最近城市時(shí)所得的頂點(diǎn)均為最后該法最佳路徑所經(jīng)過的城市編號，規(guī)模相對較小，容易確定，操作相對簡單，所以本文用數(shù)組V存放最佳路徑所經(jīng)過的城

12、市編號順序相對來說方便很多。另外，本文用path整型數(shù)組存放所經(jīng)路徑的長度，最后相加即可得最短路徑。3.3兩者比較動態(tài)規(guī)劃法相對貪心法來說雖然要精確些，但代碼相對繁雜很多，對時(shí)間和空間要求很多，僅適用于城市數(shù)量較小的情況。貪心法雖然比較簡單，實(shí)現(xiàn)起來比較容易，但不是很精確，當(dāng)圖中頂點(diǎn)個(gè)數(shù)較多并且各邊的代價(jià)值分布比較均勻時(shí)，貪心法可以給出較好的近似解，不過，這個(gè)近似解以何種程度近似于最優(yōu)解，卻難以保證。另外，動態(tài)規(guī)劃法有一個(gè)明顯的缺點(diǎn)，就是出發(fā)城市只能是第0個(gè)城市（城市從0開始編號），若出發(fā)城市改變，則必須以該城市為第0個(gè)城市順序給其他城市編號，輸入城市間距離。由于若出發(fā)城市任意，編碼的難度大大

13、增加，所以最后不得已放棄，但這大大地限制了程序的通用性。而對于貪心法，本文很好地避免了這個(gè)問題，一旦城市編號確定，可以從任意城市出發(fā)，這也是本文中貪心法優(yōu)于動態(tài)規(guī)劃法的一點(diǎn)。3.4優(yōu)點(diǎn)本文程序優(yōu)點(diǎn)，各個(gè)子函數(shù)功能分隔很明顯，沒有大量集中在一個(gè)函數(shù)里面，而是分成了幾個(gè)不同功能的小函數(shù)，這樣程序可閱讀性提高。另外，程序中有詳細(xì)注釋，程序中變量取名都是根據(jù)變量的性質(zhì)和所代表的含義命名的，也相應(yīng)提高了程序的可讀性。對于動態(tài)規(guī)劃法，城市個(gè)數(shù)可以在算法時(shí)間允許的范圍內(nèi)任意，于這點(diǎn)來說，通用性較好；對于貪心法，出發(fā)城市可以任意，城市個(gè)數(shù)也可以任意，通用性較好。4建議當(dāng)城市個(gè)數(shù)較少時(shí)，用動態(tài)規(guī)劃法求出最優(yōu)解；

14、當(dāng)城市個(gè)數(shù)較多并且各邊的代價(jià)值分布比較均勻時(shí)，貪心法可以給出較好的近似解。5參考文獻(xiàn)（1）計(jì)算機(jī)算法分析與設(shè)計(jì)第二版，王曉東編著，電子工業(yè)出版社（2）Java語言與面向?qū)ο蟪绦蛟O(shè)計(jì)（第2版）印旻、王行言編著，清華大學(xué)出版社（3）求解TSP算法，周康、強(qiáng)小利、同小軍、許進(jìn)，計(jì)算機(jī)工程與應(yīng)用6附錄6.1動態(tài)規(guī)劃法6.1.1源代碼package exp2;import java.util.Scanner;public class TSPDynamic String V;/頂點(diǎn)生成的子集，這里把每一個(gè)子集用一個(gè)字符串表示int c;/頂點(diǎn)間距離int d;/存放迭代結(jié)果int N; /城市個(gè)數(shù)Stri

15、ng path;/用于存放每種選擇下經(jīng)過的城市static int IFINITE = 99999;/無窮大距離 表示城市自己到達(dá)自己時(shí)，距離無窮大，不作為考慮因素/構(gòu)造函數(shù)public TSPDynamic()initialC();initialV1();/初始化數(shù)組c，即頂點(diǎn)間距離public void initialC()Scanner in = new Scanner( System.in );System.out.println("請輸入城市個(gè)數(shù)： （注意根據(jù)實(shí)際情況城市個(gè)數(shù)不可小于1?。?quot;); N = in.nextInt(); if(N <= 1) Sy

16、stem.out.println("不符合要求，請認(rèn)真核對！"); System.exit(0);/輸入錯誤，結(jié)束！ System.out.println("請輸入城市相鄰城市間距離（城市從0開始編號，且出發(fā)城市為第0個(gè)城市?。?");c = new intNN;/為c分配空間for(int i = 0 ; i < N ; i +)for(int j = 0 ; j < N ; j +)cij = in.nextInt(); /輸入時(shí)，按城市編號從小到大，如若兩城市間沒有公路相連，則距離為無窮大。本城市與本城市間距離也為無窮大。/初始化頂點(diǎn)

17、生成的子集的對外調(diào)用函數(shù)public void initialV1()V = new String(int)Math.pow(2,N-1);/為V分配空間initialV(0,0);/具體的初始化頂點(diǎn)生成的子集/本程序使用遞歸調(diào)用方法初始化V，并按照數(shù)字大小順序排序。另，子集使用字符型形式存放的/我們是按照子集中元素個(gè)數(shù)從小到大逐個(gè)添加的，后面的子集是前面對應(yīng)子集加上一個(gè)元素組成的，故用遞歸public void initialV(int m , int len)/m代表下一個(gè)即將初始化的V數(shù)組的元素的下標(biāo)；len是最后一個(gè)初始化的元素的長度if(m > (int)Math.pow(2,

18、N-1) - 1)return;/如果全部頂點(diǎn)已初始化完成，則返回。if(m = 0)Vm + = ""/初始化出發(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 = "&quo

19、t; + Vi.charAt(Vi.length() - 1);/找出Vi中最后一個(gè)數(shù)字ch = Integer.parseInt(chStr);/轉(zhuǎn)換成整型/比ch大而又比N-1(因?yàn)檫@里頂點(diǎn)是從0開始的)小的數(shù)字應(yīng)該加在子集中while(ch < N - 1)Vm + = Vi + (+ ch);i +;/對已存在的自己逐個(gè)掃描添加initialV(m,Vm - 1.length();/遞歸調(diào)用/判斷自己Vj中是否存在指定元素，即行號iboolean exclude(int i , int j)String str = "" + i;/把i轉(zhuǎn)換成字符串if(Vj.

20、contains(str)/System.out.println(i + "i");return false;/如若存在，則返回falseelse return true;/獲得子集Vj中除指定元素k外的元素，用字符串形式表示public String getSubString(int k , int j)if(Vj.length() = 1)return ""/如果子集中只有一個(gè)元素，則返回空串else if(k = 0) return Vj.substring(1,Vj.length();/如果k是第一個(gè)元素，則返回其后面的元素 else if(k

21、= Vj.length() - 1) return Vj.substring(0, Vj.length()-1);/如果k是最后一個(gè)元素，則返回其前面的元素 else return (Vj.substring(0, k) + Vj.substring(k+1, Vj.length();/返回除k外的元素/找出V中與str相同元素的下標(biāo)號,即找出上一個(gè)子集public int stringEqual(String str)/if(str.equals("")return 0;int i = 0;while(i < V.length)if(Vi.equals(str)re

22、turn i;i +;return -1;/如若沒找到，則返回錯誤符號-1/求最小距離public int min(int i , int j)int k = 0;/用于記錄Vj中元素個(gè)數(shù)String vStr = "" + Vj.charAt(k);/銘記Vj.charAt(k)得到的是字符型，轉(zhuǎn)換成整形后是字母對應(yīng)的ASC碼！int v = Integer.parseInt(vStr);/把位置k處的字符轉(zhuǎn)換成整形String str = getSubString(k,j);/獲得Vj中除位置k處外的字符串/System.out.println("min&qu

23、ot; + str + stringEqual(str) + v);if(stringEqual(str) = -1)System.exit(0);int min = civ + dvstringEqual(str);/先把最小的距離賦值給從Vj中第一個(gè)頂點(diǎn)出發(fā)的距離/System.out.println(min); /stringEqual(str)表示返回與上面獲得的字符串相同的V中元素的下標(biāo)，即找上一個(gè)子集pathij = pathvstringEqual(str) + i;k +;/尋找最小距離while(k < Vj.length()vStr = "" +

24、Vj.charAt(k);v = Integer.parseInt(vStr);str = getSubString(k,j);if(min > civ + dvstringEqual(str)min = civ + dvstringEqual(str);pathij = pathvstringEqual(str) + i;k +;/Vj.substring(beginIndex, endIndex)/System.out.println(pathij);return min;/返回最小值/處理函數(shù)public void dynamic()d = new intN(int)Math.po

25、w(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(exclude(i,j)/判斷V子集

26、中是否包含當(dāng)前頂點(diǎn)，即Vj中是否包含i/System.out.println("done！" + i + " " + j);dij = min(i , j);/尋找最小距離d0j = min(0,j);/初始化組后一列/輸出中間結(jié)果，各個(gè)數(shù)組，用于調(diào)試程序public void 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

27、.println();for(int i = 0 ; i < N ; i +)for(int j = 0 ; j < N ; j +)System.out.print(cij + " ");System.out.println();for(int i = 0 ; i < N ; i +)for(int j = 0 ; j < (int)Math.pow(2,N-1) ; j +)System.out.print(dij + " ");System.out.println();/輸出最短路徑public void printShor

28、testPath()/輸出所經(jīng)城市System.out.print("經(jīng)過城市：");String str = path0(int)Math.pow(2,N-1) - 1;/System.out.println(str);System.out.print(str.charAt(str.length() - 1);for(int i = str.length() - 2 ; i >= 0 ; i -)System.out.print("->" + str.charAt(i);System.out.println("會有最短路徑&quo

29、t;);System.out.println("最短路徑為：" + d0(int)Math.pow(2,N-1) - 1);/主函數(shù)public static void main(String args) TSPDynamic TSP = new TSPDynamic();TSP.dynamic();/求最短路徑/TSP.print();TSP.printShortestPath();/輸出最短路徑/測試數(shù)據(jù)/*99999 3 6 75 99999 2 36 4 99999 23 7 5 99999 */6.1.2結(jié)果（1）（2）（3）（4）6.2貪心法6.2.1源代碼pa

30、ckage exp2;import java.util.Scanner;public class TSPGreedNode int V;/存放旅行所經(jīng)過的城市頂點(diǎn)int c;/存放每兩座城市間的距離，注意：若路徑不存在或同一城市間距離為無窮大int path;/存放旅行所經(jīng)過的每兩座城市間的距離int N;/城市個(gè)數(shù)int shortestPath;/表示最短路徑int u0;/出發(fā)城市編號static int IFINITE = 99999;/無窮大距離 表示城市自己到達(dá)自己時(shí)，距離無窮大，不作為考慮因素public TSPGreedNode ()initialC();/得到最短路徑publ

31、ic int getShortestPath()for(int i = 0 ; i < N ; i +)shortestPath += pathi;return shortestPath;/初始化數(shù)組c，即頂點(diǎn)間距離public void initialC()Scanner in = new Scanner( System.in );System.out.println("請輸入城市個(gè)數(shù)： （注意根據(jù)實(shí)際情況城市個(gè)數(shù)不可小于1?。?quot;); N = in.nextInt(); if(N <= 1) System.out.println("不符合要求，請認(rèn)真核對！"); System.exit(0);/輸入錯誤，結(jié)束！ System.out.println("請輸入城市相鄰城市間距離（城市從0開始編號，且出發(fā)城市為第0個(gè)城市！）： ");c = new intNN;/為c分配空間for(int i = 0 ; i < N ; i +)for(int j = 0 ; j < N ; j +)cij = in.nextInt(); /輸入時(shí)，按城市編號從小到大，如若