算法報告-旅行商問題模板講解

1、精選優(yōu)質(zhì)文檔-傾情為你奉上算法設(shè)計與課程設(shè)計題 目： TSP問題多種算法策略 班 級： 計算機技術(shù)14 學(xué) 號： 姓 名： 指導(dǎo)老師： 完成日期： 成 績： 旅行商問題的求解方法摘要旅行商問題（TSP問題）時是指旅行家要旅行n個城市然后回到出發(fā)城市，要求各個城市經(jīng)歷且僅經(jīng)歷一次，并要求所走的路程最短。該問題又稱為貨郎擔(dān)問題、郵遞員問題、售貨員問題，是圖問題中最廣為人知的問題。本文主要介紹用動態(tài)規(guī)劃法、貪心法、回溯法和深度優(yōu)先搜索策略求解TSP問題，其中重點討論動態(tài)規(guī)劃法和貪心法，并給出相應(yīng)求解程序。關(guān)鍵字：旅行商問題；動態(tài)規(guī)劃法；貪心法；回溯法；深度優(yōu)先搜索策略1引言旅行商問題(TSP)是組合

2、優(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ī)劃法、貪心法、回溯法和深度優(yōu)先搜索策略。2正文2.1

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

4、; （2）for (j=1; j -1; j+) for (i=1; in; i+) /依次進行第i次迭代 if (子集Vj中不包含i) 對Vj中的每個元素k，計算Vm = Vj-k;dij=min(cik+dkm); （3）對V -1中的每一個元素k，計算Vm = V -1-k;d0 -1=min(c0k+dkm); （4）輸出最短路徑長度d0 -1;2.1.4時間復(fù)雜性動態(tài)規(guī)劃法求解TSP問題，把原來的時間復(fù)雜性是O(n!)的排列問題，轉(zhuǎn)化為組合問題，從而降低了算法的時間復(fù)雜性，但它仍需要指數(shù)時間。2.2貪心法2.2.1貪心法的設(shè)計思想貪心法在解決問題的策略上目光短淺，只根據(jù)當(dāng)前已有的信息

5、就做出選擇，而且一旦做出了選擇，不管將來有什么結(jié)果，這個選擇都不會改變。換言之，貪心法并不是從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)。這種局部最優(yōu)選擇并不總能獲得整體最優(yōu)解，但通常能獲得近似最優(yōu)解。2.2.2最近鄰點策略求解TSP問題貪心法求解TSP問題的貪心策略是顯然的，至少有兩種貪心策略是合理的：最近鄰點策略和最短鏈接策略。本文僅重點討論最近鄰點策略及其求解過程。最近鄰點策略：從任意城市出發(fā)，每次在沒有到過的城市中選擇距離已選擇的城市中最近的一個，直到經(jīng)過了所有的城市，最后回到出發(fā)城市。2.2.3算法分析1P= ; 2V=V-u0; u=u0; /從頂點u0出發(fā)3循環(huán)直到集

6、合P中包含n-1條邊 3.1查找與頂點u鄰接的最小代價邊(u, v)并且v屬于集合V； 3.2 P=P+(u, v); 3.3 V=V-v; 3.4 u=v; /從頂點v出發(fā)繼續(xù)求解2.2.4時間復(fù)雜性但需注意，用最近鄰點貪心策略求解TSP問題所得的結(jié)果不一定是最優(yōu)解。當(dāng)圖中頂點個數(shù)較多并且各邊的代價值分布比較均勻時，最近鄰點策略可以給出較好的近似解，不過，這個近似解以何種程度近似于最優(yōu)解，卻難以保證。2.3回溯法2.3.1回溯法的設(shè)計思想 回溯法(探索與回溯法)是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達到目標(biāo)。但當(dāng)探索到某一步時，發(fā)現(xiàn)原先選擇并不優(yōu)或達不到目標(biāo)，就退回一步重新選擇，這種走不通

7、就退回再走的技術(shù)為回溯法，而滿足回溯條件的某個狀態(tài)的點稱為“回溯點”。若已有滿足約束條件的部分解，不妨設(shè)為（x1,x2,x3,xi），I=目標(biāo)變量，就直接不再往下面走，向上走。深度優(yōu)先 = 遞歸遞歸基:如果到達葉子節(jié)點的上一個節(jié)點，那么就進行是否更新的判斷遞歸步:如果沒有到達葉子節(jié)點，就進行剪枝操作，判斷能否進入下一個節(jié)點，如果能，更新最優(yōu)值2.3.3 關(guān)鍵實現(xiàn)（回溯法+深度優(yōu)先搜索策略）1 /遞歸基：如果已經(jīng)遍歷到葉子節(jié)點的上一層節(jié)點，i標(biāo)識遞歸深度if(i = g_n)/判斷累加和是否超過最大值,如果有0，應(yīng)該排除;滿足這個條件，才打印if(g_iArrpArri-1pArri != 0)

8、 & (g_iArrpArrg_n1 != 0) &(g_iCurResult + g_iArrpArri-1pArri + g_iArrpArrg_n1 g_iResult )g_iResult = g_iCurResult + g_iArrpArri-1pArri + g_iArrpArrg_n1;/用當(dāng)前最優(yōu)路徑去更新最優(yōu)路徑，防止下一次沒有for(int k = 1 ; k = g_n ; k+)g_iBestPathk = pArrk;2 /遞歸步:判斷能否進入子樹，需要嘗試每一個節(jié)點else/嘗試不同的組合for(int j = i ; j = g_n ; j+)/判斷能否進入子樹

9、:如果當(dāng)前值+下一個連線值的和 最優(yōu)值，就進入,0要passif( (g_iArrpArri-1pArrj != 0) & (g_iCurResult + g_iArr pArri-1 pArrj g_iResult) )3 /交換i與j,則i為當(dāng)前可以嘗試的范圍/為完成后面k個元素的排列，逐一對數(shù)組第n-kn個元素互換。數(shù)組第一個元素為1，生成后面n-1個元素的排列/數(shù)組第一個元素與第二個元素互換，第一個元素為2，第2個元素為1，生成后面的n-1個元素的排列.swap(&pArri,&pArrj);/更新當(dāng)前累加值,是i-1與i的g_iCurResult += g_iArr pArri-1

10、pArri ;/遞歸backTrace(i+1,pArr);/回溯，清空累加值；能夠走到這里，說明上述結(jié)果不是最優(yōu)解，需要向求解樹上一層回退g_iCurResult -= g_iArrpArri-1 pArri ;swap(&pArri,&pArrj);*/2.3.4時間復(fù)雜性T = O(n!), 該方法并沒有有效的提高時間效率。3結(jié)論本文主要重點討論了動態(tài)規(guī)劃法、貪心法、回溯法和深度優(yōu)先搜索策略求解TSP問題算法，并附錄給出了相應(yīng)程序，并通過對比得到動態(tài)規(guī)劃法和貪心法相對更有優(yōu)勢，下面對這兩種方法進行詳述和進一步對比。3.1動態(tài)規(guī)劃法思想動態(tài)規(guī)劃法中對于頂點元素生成的子集本文中用字符串形式存

11、儲，然后再用遞歸方法按照子集中元素個數(shù)從小到大開始賦值。因為后面元素個數(shù)較多的子集與前面比其元素個數(shù)少1的子集間有一定對應(yīng)關(guān)系，所以用遞歸方式，可以簡便很多。個人覺得這算本文的一大特色。另，在計算dij =min(cik+dkj-1)時，獲得dkj-1的過程比較困難，運用字符串后，我們就可以首先找到指定字符，然后去掉該字符，返回剩余字符串，在與V逐個比較，找到與其相等的V中元素對應(yīng)下標(biāo)，此下標(biāo)即為j-1；具體求解過程可參考附錄源程序，有詳細說明。在求解最佳路徑所經(jīng)過城市順序時，本文是通過邊查找dij邊記錄路徑的，這樣可以省掉很多麻煩，另，路徑也是采用字符串形式的數(shù)組，數(shù)組規(guī)模與存儲城市間距離的

12、c數(shù)組相同，由于很多元素均不需賦值，這樣做可能會浪費內(nèi)存空間，但是目前還沒找到更好地求解方法。3.2貪心法思想貪心法中，由于貪心法相對動態(tài)規(guī)劃法要簡單很多，每次在查找最近城市時所得的頂點均為最后該法最佳路徑所經(jīng)過的城市編號，規(guī)模相對較小，容易確定，操作相對簡單，所以本文用數(shù)組V存放最佳路徑所經(jīng)過的城市編號順序相對來說方便很多。另外，本文用path整型數(shù)組存放所經(jīng)路徑的長度，最后相加即可得最短路徑。3.3兩者比較動態(tài)規(guī)劃法相對貪心法來說雖然要精確些，但代碼相對繁雜很多，對時間和空間要求很多，僅適用于城市數(shù)量較小的情況。貪心法雖然比較簡單，實現(xiàn)起來比較容易，但不是很精確，當(dāng)圖中頂點個數(shù)較多并且各邊

13、的代價值分布比較均勻時，貪心法可以給出較好的近似解，不過，這個近似解以何種程度近似于最優(yōu)解，卻難以保證。另外，動態(tài)規(guī)劃法有一個明顯的缺點，就是出發(fā)城市只能是第0個城市（城市從0開始編號），若出發(fā)城市改變，則必須以該城市為第0個城市順序給其他城市編號，輸入城市間距離。由于若出發(fā)城市任意，編碼的難度大大增加，所以最后不得已放棄，但這大大地限制了程序的通用性。而對于貪心法，本文很好地避免了這個問題，一旦城市編號確定，可以從任意城市出發(fā)，這也是本文中貪心法優(yōu)于動態(tài)規(guī)劃法的一點。3.4優(yōu)點本文程序優(yōu)點，各個子函數(shù)功能分隔很明顯，沒有大量集中在一個函數(shù)里面，而是分成了幾個不同功能的小函數(shù)，這樣程序可閱讀性

14、提高。另外，程序中有詳細注釋，程序中變量取名都是根據(jù)變量的性質(zhì)和所代表的含義命名的，也相應(yīng)提高了程序的可讀性。對于動態(tài)規(guī)劃法，城市個數(shù)可以在算法時間允許的范圍內(nèi)任意，于這點來說，通用性較好；對于貪心法，出發(fā)城市可以任意，城市個數(shù)也可以任意，通用性較好。3.5 建議當(dāng)城市個數(shù)較少時，用動態(tài)規(guī)劃法求出最優(yōu)解；當(dāng)城市個數(shù)較多并且各邊的代價值分布比較均勻時，貪心法可以給出較好的近似解。4參考文獻（1）計算機算法分析與設(shè)計第二版，王曉東編著，電子工業(yè)出版社（2）Java語言與面向?qū)ο蟪绦蛟O(shè)計（第2版）印旻、王行言編著，清華大學(xué)出版社（3）求解TSP算法，周康、強小利、同小軍、許進，計算機工程與應(yīng)用（4）

15、算法設(shè)計與分析，王紅梅編著，清華大學(xué)出版社（5）ACM/ICPC算法訓(xùn)練教程，余立功主編，清華大學(xué)出版社6附錄6.1動態(tài)規(guī)劃法6.1.1源代碼package Tsp;import java.util.Scanner;public class TSPDP String V;/ 頂點生成的子集，這里把每一個子集用一個字符串表示int c;/ 頂點間距離int d;/ 存放迭代結(jié)果int N; / 城市個數(shù)String path;/ 用于存放每種選擇下經(jīng)過的城市static int IFINITE = 99999;/ 無窮大距離 表示城市自己到達自己時，距離無窮大，不作為考慮因素/ 構(gòu)造函數(shù)publ

16、ic TSPDP() initialC();initialV1();/ 初始化數(shù)組c，即頂點間距離public void initialC() Scanner in = new Scanner(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個城市?。?

17、);c = new intNN;/ 為c分配空間for (int i = 0; i N; i+)for (int j = 0; j (int) Math.pow(2, N - 1) - 1)return;/ 如果全部頂點已初始化完成，則返回。if (m = 0)Vm+ = ;/ 初始化出發(fā)頂點，即V0else int i = m - 1;while (i = 0 & Vi.length() = len)/ 找與最后一個初始化的Vm-1子集內(nèi)元素個數(shù)相同的集合，把指針i指向滿足條件的集合i-;i+;/ 把指針i指向滿足條件的第一個集合while (i m) int ch;/ 用于表示下一個即將加

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

19、, int j) String str = + i;/ 把i轉(zhuǎn)換成字符串if (Vj.contains(str)/ System.out.println(i + i);return false;/ 如若存在，則返回falseelsereturn true;/ 獲得子集Vj中除指定元素k外的元素，用字符串形式表示public String getSubString(int k, int j) if (Vj.length() = 1)return ;/ 如果子集中只有一個元素，則返回空串else if (k = 0)return Vj.substring(1, Vj.length();/ 如果k是

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

21、(Vi.equals(str)return i;i+;return -1;/ 如若沒找到，則返回錯誤符號-1/ 求最小距離public int min(int i, int j) int k = 0;/ 用于記錄Vj中元素個數(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(m

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

23、 + 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.pow(2, N - 1);/ 分配空間path = new StringN(int) Math.pow(2, N - 1);for (int i = 1; i N; i+) / 初始化第一列di0 = ci0;

24、pathi0 = 0 + i;/ 初始化第一個元素，即為出發(fā)城市頂點/ 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子集中是否包含當(dāng)前頂點，即Vj中是否包含i/ System.out.println(done！ + i + + j);dij = min(i, j);/ 尋找最小距離d0j = min(0, j);/ 初始化組后一列/ 輸出中間結(jié)果，各個數(shù)組，用于調(diào)試程序pu

25、blic void print() System.out.println(顯示定點生成子集：);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();System.out.println(打印代價矩陣：);for (int i = 0; i N; i+) for (int j = 0; j N; j+)System.out.print(cij + );System.out.println();Syste

26、m.out.println(動態(tài)規(guī)劃表填表結(jié)果：);for (int i = 0; i N; i+) for (int j = 0; j = 0; i-) System.out.print(- + str.charAt(i);System.out.println(會有最短路徑);System.out.println(最短路徑為： + d0(int) Math.pow(2, N - 1) - 1);/ 主函數(shù)public static void main(String args) TSPDP TSP = new TSPDP();TSP.dynamic();/ 求最短路徑TSP.print();/

27、打印中間結(jié)果，測試和理解用TSP.printShortestPath();/ 輸出最短路徑/ 測試數(shù)據(jù)/* * 99999 3 6 7 * 5 99999 2 3 * 6 4 99999 2 * 3 7 5 99999 */6.1.2結(jié)果（1）（2）（3）（4）6.2貪心法6.2.1源代碼/* * TSP：貪心法之最近鄰點策略求解 */package Tsp;import java.util.Scanner;public class TSPGreedy int V;/ 存放旅行所經(jīng)過的城市頂點int c;/ 存放每兩座城市間的距離，注意：若路徑不存在或同一城市間距離為無窮大int path;/

28、 存放旅行所經(jīng)過的每兩座城市間的距離int N;/ 城市個數(shù)int shortestPath;/ 表示最短路徑int u0;/ 出發(fā)城市編號static int IFINITE = 99999;/ 無窮大距離 表示城市自己到達自己時，距離無窮大，不作為考慮因素public TSPGreedy() initialC();/ 得到最短路徑public int getShortestPath() for (int i = 0; i N; i+) shortestPath += pathi;return shortestPath;/ 初始化數(shù)組c，即頂點間距離public void initialC(

29、) Scanner in = new Scanner(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 = new intNN;/ 為c分配空間for (int i = 0; i N; i+)for (int j = 0; j N; j

30、+) cij = in.nextInt(); / 輸入時，按城市編號從小到大，如若兩城市間沒有公路相連，則距離為無窮大。本城市與本城市間距離也為無窮大。public void tspGreedy() Scanner in = new Scanner(System.in);System.out.println(請輸入出發(fā)城市編號（注意城市從0開始編號，請按照輸入城市間距離即初始化c時順序計算）：);u0 = in.nextInt();V = new intN + 1;path = new intN;int k = 0;Vk = u0;while (k N) int min = IFINITE;k

31、+;for (int i = 0; i N; i+) int mark = 0;for (int j = 0; j k; j+)if (Vj = i)mark = 1;if (mark = 0 & cVk - 1i min) min = cVk - 1i;Vk = i;pathk - 1 = min;Vk = u0;pathk - 1 = cVk - 1Vk;/ 輸出最短路徑下所經(jīng)城市，兩城市間距離和最短路徑public void print() shortestPath = 0;System.out.println(按照下列方式旅游會使所走路程最短：);for (int i = 0; i +

32、 Vi + 1 + ,所經(jīng)路程為：+ pathi);shortestPath += pathi;System.out.println(總路程為： + shortestPath);public static void main(String args) TSPGreedy tg = new TSPGreedy();tg.tspGreedy();/tg.print();/* * 99999 3 3 2 6 * 3 99999 7 3 2 * 3 7 99999 2 5 * 2 3 2 99999 3 * 6 2 5 3 99999 */6.2.2結(jié)果(1)(2)(3)(4)6.3回溯法（回溯法+深

33、度優(yōu)先搜索策略）6.3.1源代碼#include #include using namespace std;const int MAXSIZE = 100;const int MAX = ;int g_iArrMAXSIZEMAXSIZE;/鄰接矩陣int g_iResult;/存放最優(yōu)解int g_iPathMAXSIZE;/存放最優(yōu)路徑上int g_n;/元素個數(shù)int g_iCurResult;/當(dāng)前累加路徑和int g_iBestPathMAXSIZE;/還需要設(shè)置一個數(shù)組，用來保存最優(yōu)解void swap(int* pI,int* pJ)int iTemp = *pI;*pI= *p

34、J;*pJ = iTemp;void printResult(int n,int* pArr) cout最短距離為：endl; coutg_iResultendl; cout最優(yōu)路線為：endl;for(int i = 1 ; i = n ; i+)if( i != 1)coutpArri;elsecoutpArri;cout1endl;/可以做成字符串全排列的性質(zhì)track(int i,int* pArr,int* pResult),其中pArr是用于存放最優(yōu)解的路徑void backTrace(int i,int* pArr)/遞歸基：如果已經(jīng)遍歷到葉子節(jié)點的上一層節(jié)點if(i = g_n)/判斷累加和是否超過最大值,如果有0，應(yīng)該排除;滿足這個條件，才打印if(g_iArrpArri-1pArri != 0) & (g_iAr