1、.實(shí)驗(yàn)二：回溯法VS分支定界法一、問(wèn)題分析回溯法可以處理貨郎擔(dān)問(wèn)題， 分支定界法也可以處理貨郎擔(dān)問(wèn)題，回溯法和分支定界法哪個(gè)算法處理貨郎擔(dān)問(wèn)題效率更高呢？實(shí)現(xiàn)回溯法、分支定界法，以及不同的界值函數(shù)（課上講過(guò)的或者自己新設(shè)計(jì)的），通過(guò)隨機(jī)產(chǎn)生 10 個(gè)不同規(guī)模的算例（城市數(shù)量分別為10，20，40，80，100， 120，160，180，200， 500，或者其它規(guī)模），比較回溯法和分支定界法在相同界值函數(shù)下的執(zhí)行效率。 另外，分別比較回溯法和分支定界法在不同界值函數(shù)下的執(zhí)行效率。二、算法基本思想1、回溯法從初始狀態(tài)出發(fā)，搜索其所能到達(dá)的所有“狀態(tài)”，當(dāng)一條路走到盡頭 ，再后退一步或若干步，從另

2、外一種狀態(tài)出發(fā)，繼續(xù)搜索，直到所有的路徑都搜索過(guò)。這種不斷前進(jìn) 、不斷回溯尋找解的方法叫回溯法?；厮莘ㄍǔ?wèn)題解空間組織成“樹”結(jié)構(gòu)，采用系統(tǒng)的方法搜索解空間樹，從而得到問(wèn)題解。搜索策略：深度優(yōu)先為主，也可以采用廣度優(yōu)先、函數(shù)優(yōu)先、廣度深度結(jié)合等。避免無(wú)效搜索策略：約束函數(shù)：在擴(kuò)展結(jié)點(diǎn)處剪去不滿足約束條件的子樹界限函數(shù)：在擴(kuò)展結(jié)點(diǎn)處剪去得不到最優(yōu)解的子樹2、分支限界法分支界限法類似與回溯法，也是在問(wèn)題解空間中搜索問(wèn)題解的一種算法。分支界限法與回溯法思想對(duì)比：求解目標(biāo)：回溯法的可以用于求解目標(biāo)是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標(biāo)通常是找出滿足約束條件的一個(gè)解或最優(yōu)解。搜

3、索方式的不同： 回溯法主要以深度優(yōu)先的方式搜索解空間樹，而分支限界法則;.主要以廣度 先或以最小耗 先的方式搜索解空 。在分支限界法中，每個(gè)活 點(diǎn)只有一次機(jī)會(huì)成 展 點(diǎn)。一旦成 展 點(diǎn)，就一次性 生其所有兒子 點(diǎn)。在 些兒子 點(diǎn)中， 致不可行解或 致非最 解的兒子 點(diǎn)被舍棄，其余兒子 點(diǎn)被加入活 點(diǎn)表中。此后，從活 點(diǎn)表中取下一 點(diǎn)成 當(dāng)前 展 點(diǎn)，并重復(fù)上述 點(diǎn) 展 程。 個(gè) 程一直持 到找到所需的解或活 點(diǎn)表 空 止。三、算法 1、回溯法TSP 的目的是得到一條路徑，即一個(gè)解向量 （ X1,X2.Xn ）， 排列 。 所有城市 行 號(hào)后，按大小 序存 于數(shù) path 中，構(gòu)造一個(gè)交 函數(shù)

4、swap（）； 數(shù) path 行遍 ，判斷當(dāng)前城市與目 城市是否 通，若 通，通 swap 函數(shù) 當(dāng)前 點(diǎn)和目 城市 行交 ，即 的 點(diǎn)拓展。若不 通 恢復(fù)，并 入下一次的循 ， 循 到葉子 點(diǎn) ， 判斷葉是否與初始 點(diǎn)相 ，并 算代價(jià) cost 是否小于當(dāng)前最小代價(jià) bestc ，若小于， 更新 bestc ，再返回上一 點(diǎn)，知道遍 完 中的所有 點(diǎn)。2、分支限界法因 是 典的TSP ，所以確定 的解空 排列 。 解的表示：可以將 的解表示成一個(gè)n 元式 x1,x2, ,xn 。使用 先 列 最小耗 先求解。界函數(shù)的確定： 首先利用 心的方法 得一個(gè) 的上界。 于當(dāng)前路徑下的 展的 程中，每

5、一步需要存 的當(dāng)前的 點(diǎn)的下界。 其中的第二部分需要 算的是當(dāng)前路徑的起始 點(diǎn)以及 止 點(diǎn)各自與仍未 的 點(diǎn)中的 點(diǎn)只存存在的最小代價(jià)。 點(diǎn)的 展 程如下： 根據(jù) 先 從 列中 取 先 最高的元素， 當(dāng) 點(diǎn)不是葉子 點(diǎn)的父 點(diǎn) ， 展 點(diǎn)的所有子 點(diǎn)， 在 展的 程中需要根據(jù) 算所得的下界與當(dāng)前求解得到的最 解 行 比， 如果下界大于當(dāng)前的最 解 相 的子 點(diǎn) 行剪枝 理， 否 展 子 點(diǎn)， 將其加入到 列中。 當(dāng)當(dāng)前所 的 點(diǎn) 葉子 點(diǎn)的父 點(diǎn) ，判斷當(dāng)前 用 +當(dāng)前 點(diǎn)到葉子 點(diǎn)的 ;.用 +葉子結(jié)點(diǎn)到起始結(jié)點(diǎn)的費(fèi)用之和是否優(yōu)于最優(yōu)解，如果是則更新最優(yōu)解，并將當(dāng)前的解加入到隊(duì)列中。 如果不

6、是則繼續(xù)取隊(duì)列中的元素進(jìn)行擴(kuò)展。 但取出的元素為葉子節(jié)點(diǎn)或者隊(duì)列中的元素為空的時(shí)候， 則搜索結(jié)束，輸出當(dāng)前的最優(yōu)解。四、算法實(shí)現(xiàn)1、回溯法核心代碼：publicvoid backtrack(intdepth)/depth深度if (depth=size)if (mappathdepth-1pathdepth != -1 &mappathdepthpath1!= -1& cost +mappathdepthpath1bestc)bestp=path.clone();bestc = cost + mappathdepthpath1;/bestc = cost +apathi-1pathi+apat

7、hipath1;/ 重復(fù)計(jì)算了上一邊 else for ( intj =depth;j=size;j+)if (mappathdepthpathj!=-1)swap(path,depth+1,j);cost +=mappathdepthpathdepth+1;/System.out.println(Arrays.toString(x)+:+cost);backtrack(depth+1);cost -=mappathdepthpathdepth+1;swap(path,depth+1,j);.2、分支限界法核心代碼：publicfloatfzxj( int m)intn=m. length-

8、1; / 節(jié)點(diǎn)數(shù)LinkedList heap=new LinkedList() ;/minOuti=i的最小出邊費(fèi)用floatminOut =new float n+1 ;floatminSum=0; / 最小出邊費(fèi)用和for ( inti =1; i =n; i +) / 針對(duì)每個(gè)節(jié)點(diǎn)，找到最小出邊/ 計(jì)算 minOuti和 minSumfloatmin =Float. MAX_VALUE;for ( intj =1; j =n; j +)if ( map i j Float . MAX_VALUE&map i j min)min =map i j ;if ( min=Float. MAX

9、_VALUE)returnFloat . MAX_VALUE;minOut i =min ;minSum+=min ;/ 初始化int x=new int n ;for ( inti =0; i n; i +)x i =i +1;TSPnode enode=new TSPnode( 0, 0, minSum, 0, x) ; float bestc =Float . MAX_VALUE;/ 搜索排列空間樹while ( enode != null&enode . pn- 1)/ 非葉節(jié)點(diǎn) x=enode . path ;if ( enode . p=n- 2)/ 當(dāng)前擴(kuò)展結(jié)點(diǎn)是葉節(jié)點(diǎn)的父節(jié)點(diǎn)/

10、 再加兩條邊構(gòu)成回路/ 所構(gòu)成回路是否優(yōu)于當(dāng)前最優(yōu)解if ( map x n- 2 x n- 1 !=- 1&map x n- 1 1 !=- 1&enode . cost + map x n- 2 x n- 1 +map x n- 1 1 bestc )/ 找到費(fèi)用更小的回路bestc =enode . cost +map x n- 2 x n- 1 +map x n- 1 1 ; enode . cost =bestc ;.enode . lcost=bestc ;enode . p+;heap . add( enode ) ;Collections. sort ( heap ) ; el

11、se / 內(nèi)部結(jié)點(diǎn)/ 產(chǎn)生當(dāng)前擴(kuò)展結(jié)點(diǎn)的兒子結(jié)點(diǎn)for ( inti =enode . p+1; i n; i +)if ( map x enode . px i !=- 1)/ 可行兒子結(jié)點(diǎn)floatcc =enode . cost+map x enode . p x i ;floatrcost =enode . rcost =minOut x enode . p;floatb=cc +rcost ; /下界if ( bbestc )/ 子樹可能含有最優(yōu)解，結(jié)點(diǎn)插入最小堆intxx =new int n ;for ( intj =0; j n; j +)xx j =x j ;xx enode

12、 . p+1 =x i ;xx i =x enode . p+1 ; TSPnode node =newTSPnode( b, cc, rcost, enode . p+1, xx ) ;heap . add( node ) ;Collections. sort ( heap) ;/ 取下一個(gè)擴(kuò)展結(jié)點(diǎn) enode =heap . poll () ;/ 將最優(yōu)解復(fù)制到v1.nfor ( inti =0; i n; i +)m i +1 =x i ;returnbestc ;五、算法復(fù)雜性理論分析1、回溯法TSP問(wèn)題是排列樹問(wèn)題，因而該算法的時(shí)間復(fù)雜度為O(n!) 。;.2、分支限界法TSP 是排列 ， 在分支限界法界函數(shù)無(wú)法剪枝 有最壞情況 復(fù) 性為 O(n!) ，但通 界函數(shù)剪枝可以使復(fù) 度下降。六、算法代 （ 獨(dú)文件提交） 目文件七、算法 （ 告只寫 方法與用例 方法與 果， 程序 獨(dú)提交） 模回溯法分支限界法53ms852ms1010ms1323ms20272510ms7541ms25-20723ms-八、 中的 回溯法： 點(diǎn)：可以快速的找到一 解， 并在