TSP問題-實驗報告

1、TSP 問題目錄 TOC o 1-5 h z HYPERLINK l bookmark12 o Current Document 1實驗?zāi)康? HYPERLINK l bookmark14 o Current Document 2 問題描述與分析1 HYPERLINK l bookmark16 o Current Document 3 算法分析 1 HYPERLINK l bookmark22 o Current Document 3.1 回溯法1 HYPERLINK l bookmark28 o Current Document 3.2 動態(tài)規(guī)劃1 HYPERLINK l bookmark1

2、8 o Current Document 3.3 模擬退火算法2 HYPERLINK l bookmark20 o Current Document 4 程序設(shè)計 24.1 回溯法24.2 動態(tài)規(guī)劃算法3 HYPERLINK l bookmark30 o Current Document 4.3 模擬退火算法4 HYPERLINK l bookmark32 o Current Document 5 實驗結(jié)果及分析5 HYPERLINK l bookmark36 o Current Document 6 實驗總結(jié) 6 HYPERLINK l bookmark38 o Current Docume

3、nt 7 源代碼 6實驗?zāi)康氖褂盟阉鞣椒ㄟM(jìn)行TSP問題的求解了解相關(guān)智能算法了解 NP 難問題的求解策略問題描述與分析某售貨員要到若干城市去推銷商品，已知各城市之間的路程（或旅費(fèi)）。他要選定一條從 駐地出發(fā)，經(jīng)過每個城市一遍，最后回到駐地的路線，使總的路程（或旅費(fèi)）最小。分析：問題的本質(zhì)是搜索問題，而且這個問題是NP完全問題，問題的復(fù)雜度指數(shù)增長，所以 普通的搜索無法在有限的時間里完成搜索，盡管有各種優(yōu)化的算法：啟發(fā)式算法、深度優(yōu)先 搜索、動態(tài)規(guī)劃、回溯等。都無法改變復(fù)雜度。實際上大多時候人們并不關(guān)心NP完全問題的最優(yōu)解，只要得出一個近似的解就可以了， 因此，人們發(fā)明了很多算法，例如粒子群算法

4、、遺傳算法、模擬退火算法，這一類算法被稱 為“智能算法”，但是，他們都無法求出最優(yōu)解，僅能得到近似解，但這已經(jīng)足夠了。在本次試驗中，一共設(shè)計了三個算法：回溯法，動態(tài)規(guī)劃，模擬退火算法。算法分析3.1 回溯法回溯法采用深度優(yōu)先方式系統(tǒng)地搜索問題的所有解，基本思路是：確定解空間的組織結(jié) 構(gòu)之后，從根結(jié)點(diǎn)出發(fā)，即第一個活結(jié)點(diǎn)和第一個擴(kuò)展結(jié)點(diǎn)向縱深方向轉(zhuǎn)移至一個新結(jié)點(diǎn)， 這個結(jié)點(diǎn)成為新的活結(jié)點(diǎn)，并成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。如果在當(dāng)前擴(kuò)展結(jié)點(diǎn)處不能再向縱深方向 轉(zhuǎn)移,則當(dāng)前擴(kuò)展結(jié)點(diǎn)成為死結(jié)點(diǎn)。此時,回溯到最近的活結(jié)點(diǎn)處,并使其成為當(dāng)前擴(kuò)展結(jié)點(diǎn)， 回溯到以這種工作方式遞歸地在解空間中搜索,直到找到所求解空間中已經(jīng)

5、無活結(jié)點(diǎn)為止。旅行商問題的解空間是一棵排列樹對于排列樹的回溯搜索與生成1,2,n的所有排列 的遞歸算法Perm類似，設(shè)開始時x= 1,2,. n ，則相應(yīng)的排列樹由x 1:n 的所有排列構(gòu)成. 旅行商問題的回溯算法。3.2 動態(tài)規(guī)劃設(shè)s, s1, s2,，sp, s是從s出發(fā)的一條路徑長度最短的簡單回路,假設(shè)從s到下一個城市 si已經(jīng)求出，則問題轉(zhuǎn)化為求從si到s的最短路徑，顯然si, s2,，sp, s 一定構(gòu)成一條從si 到s的最短路徑，所以TSP問題是構(gòu)成最優(yōu)子結(jié)構(gòu)性質(zhì)的，用動態(tài)規(guī)劃來求解也是合理的。推導(dǎo)動態(tài)規(guī)劃方程假設(shè)從頂點(diǎn)s出發(fā)，令d（i, V）表示從頂點(diǎn)i出發(fā)經(jīng)過V（是一個點(diǎn)的集合

6、）中各個頂點(diǎn)一 次且僅一次，最后回到出發(fā)點(diǎn)s的最短路徑長度。推導(dǎo)：(分情況來討論)當(dāng)V為空集，那么d(i, V),表示從i不經(jīng)過任何點(diǎn)就回到s 了，如上圖的城市3- 城市0(0為起點(diǎn)城市)。此時d(i, V)=Cis(就是 城市i到 城市s的距離)、如果V不為空，那么就是對子問題的最優(yōu)求解。你必須在V這個城市集合中，嘗試 每一個，并求出最優(yōu)解。d(i, V)=minCik + d(k, V-k)注：Cik表示你選擇的城市和城市i的距離，d(k, V-k)是一個子問題。綜上所述，TSP問題的動態(tài)規(guī)劃方程就出來了：3.3模擬退火算法模擬退火算法是解決TSP問題的有效方法之一，其最初的思想由Metr

7、opolis在1953年 提出，Kirkpatrick在1983年成功地將其應(yīng)用在組合最優(yōu)化問題中。模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時， 固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達(dá) 到平衡態(tài)，最后在常溫時達(dá)到基態(tài)，內(nèi)能減為最小。用固體退火模擬組合優(yōu)化問題，將內(nèi)能 E模擬為目標(biāo)函數(shù)值f,溫度T演化成控制參數(shù)t,即得到解組合優(yōu)化問題的模擬退火算法： 由初始解i和控制參數(shù)初值t開始，對當(dāng)前解重復(fù)“產(chǎn)生新解一計算目標(biāo)函數(shù)差一接受或舍 棄”的迭代，并逐步衰減t值，算法終止時的當(dāng)前解即為所得近似最優(yōu)解，這是基于蒙特卡 羅迭代求解

8、法的一種啟發(fā)式隨機(jī)搜索過程。求解TSP的模擬退火算法模型可描述如下：解空間：解空間S是遍訪每個城市恰好一次的所有路經(jīng)，解可以表示為w1,w2 , wn，w1, , wn是1,2, ,n的一個排列，表明w1城市出發(fā)，依次經(jīng)過w2, , wn城 市，再返回w1城市。初始解可選為(1,n);目標(biāo)函數(shù)：目標(biāo)函數(shù)為訪問所有城市的路徑 總長度；我們要求的最優(yōu)路徑為目標(biāo)函數(shù)為最小值時對應(yīng)的路徑。新路徑的產(chǎn)生：隨機(jī)產(chǎn)生 1和n之間的兩相異數(shù)k和m，不妨假設(shè)kvm,則將原(w1,w2,wk,wk+1,wm,wm+1,wn 變?yōu)樾侣窂?(w1,w2,wm,wk+1,wk,wm+1,wn)上述變換方法就是將k和m對

9、應(yīng)的兩個 城市在路徑序列中交換位置，稱為2-opt映射。4程序設(shè)計4.1回溯法基本思想：把求解最小值嵌入全排列算法中，對于每一種路徑情況，計算其路徑長度, 然后求出最短路徑。void tsp(int i)int j;/一個全排列完成了if (i = n) / 位于一個葉子的父節(jié)點(diǎn)/ 通過增加兩條邊來完成旅行if (disttemp_pathn-1temp_pathn!=0&disttemp_pathn1!=0&(cur_len+disttemp_pathn-1temp_pathn+disttemp_pathn1min_len|min_len =0) / 找到更優(yōu)的旅行路徑for(j = 1;

10、j = n; j+) cur_pathj = temp_pathj; min_len=cur_len+disttemp_pathn-1temp_pathn + disttemp_pathn1; /構(gòu)造全排列的過程else / 嘗試子樹for (j = i; j = n; j+)層中循環(huán)+層間遞歸，整體上是深度優(yōu)先能移動到子樹x j 嗎？if (disttemp_pathi-1temp_pathj !=0& (cur_len+disttemp_pathi-1temp_pathjmin_len|min_len = 0) /能搜索該子樹Swap(&temp_pathi, &temp_pathj);/

11、第 n 層的一種情況 cur_len += disttemp_pathi-1temp_pathi; tsp(i+l);確定一層的某一種情況之后，馬上以此情況為基礎(chǔ)向下搜索 cur_len -= disttemp_pathi-1temp_pathi;Swap(&temp_pathi, &temp_pathj);復(fù)原，然后再變成下一種情況 4.2 動態(tài)規(guī)劃算法基本思想：循環(huán)+遞歸，構(gòu)造深度優(yōu)先搜索，然后從后向前每次求解出局部的最短路徑 最后合起來就是最短路徑。int SearchMinPath(int n)int CurrentMin = l000; /int back=index;/int si

12、gn=0;if(index=N-l)return distn0;for(int i=l;iN;i+)index=back;sign = 0;for(int j=0;jtemp)CurrentMin = temp;for(int m = 0;mN-l;m+)exd_pathm=cur_pathm;for(int j=0;j end) swap(begin,end);len = end - begin + 1;for(i=0;ilen/2;i+) swap(pathbegin+i,pathend-i);確定是否接受新的解：bool accept(int *curPath,int *exdPath)

13、int curResult = result(curPath);int exdResult = result(exdPath);if(exdResult 0.000001)probability = exp(curResult - exdResult) / t);if(probability randf()return true;return false;褪火過程：while(s!=2)bChange = false;for(i=0;i411 10 78 24 43求解結(jié)果：最短路徑咱8 7Press any key Q 26 75 69 982& 0 45 67 8675 45 0 19 2

14、8bV 67 IV U 7798 86 28 77 04 5 6 2 3 19 o continue動態(tài)規(guī)劃運(yùn)彳丁結(jié)果:動態(tài)規(guī)劃運(yùn)彳丁結(jié)果: E:VC6.0M SDev98MyProj ectstipaDebuga a.exe距離矩陣:0 14 24 35 461424354657621324110 17 15 33 1?153312354523100 14 5314532&156457780 :2563875B95245712266325e 14141 632664羽623EIf. i87 1G3 E:VC6.0M SDev98MyProj ectstipaDebuga a.exe距離矩陣:0 14 24 35 461424354657621324110 17 15 33 1?153312354523100 14 5314532&156457780 :2563875B95245712266325e 14141 632664羽623EIf. i87 1G3 :26 126 075 4569 6798 86134564582G754501 19 028 77 0S-解短度24235795G469671?11137B24439B8B2B770987654321nnnt i niift_24 1