西北工業(yè)大學(xué)算法設(shè)計(jì)實(shí)驗(yàn)2

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)一條路走到盡頭 ，再后退一步或若干步，從另外一種狀態(tài)出發(fā)

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

3、回溯法主要以深度優(yōu)先的方式搜索解空間樹(shù)，而分支限界法則主要以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹(shù)。在分支限界法中，每個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)。一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)。在這些兒子結(jié)點(diǎn)中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄，其余兒子結(jié)點(diǎn)被加入活結(jié)點(diǎn)表中。此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過(guò)程。這個(gè)過(guò)程一直持續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時(shí)為止。三、算法設(shè)計(jì)1、回溯法TSP問(wèn)題的目的是得到一條路徑，即一個(gè)解向量（X1,X2.Xn），為排列樹(shù)問(wèn)題。對(duì)所有城市進(jìn)行編號(hào)后，按大小順序存儲(chǔ)于數(shù)組path中，構(gòu)造一個(gè)交換函數(shù)swap（）

4、；對(duì)數(shù)組path進(jìn)行遍歷，判斷當(dāng)前城市與目標(biāo)城市是否連通，若連通，通過(guò)swap函數(shù)對(duì)當(dāng)前節(jié)點(diǎn)和目標(biāo)城市進(jìn)行交換，即樹(shù)的節(jié)點(diǎn)拓展。若不連通則恢復(fù)，并進(jìn)入下一次的循環(huán)，循環(huán)到葉子節(jié)點(diǎn)時(shí)，判斷葉是否與初始節(jié)點(diǎn)相連，并計(jì)算代價(jià)cost是否小于當(dāng)前最小代價(jià)bestc，若小于，則更新bestc，再返回上一節(jié)點(diǎn)，知道遍歷完樹(shù)中的所有節(jié)點(diǎn)。2、分支限界法因?yàn)閱?wèn)題是經(jīng)典的TSP問(wèn)題，所以確定問(wèn)題的解空間樹(shù)為排列樹(shù)。問(wèn)題解的表示：可以將問(wèn)題的解表示成一個(gè)n元式 x1,x2,xn。使用優(yōu)先級(jí)隊(duì)列實(shí)現(xiàn)最小耗費(fèi)優(yōu)先求解。界函數(shù)的確定：首先利用貪心的方法獲得一個(gè)較優(yōu)的上界。對(duì)于當(dāng)前路徑下的擴(kuò)展的過(guò)程中，每一步需要存儲(chǔ)的當(dāng)

5、前的結(jié)點(diǎn)的下界。其中的第二部分需要計(jì)算的是當(dāng)前路徑的起始結(jié)點(diǎn)以及終止結(jié)點(diǎn)各自與仍未訪(fǎng)問(wèn)過(guò)的結(jié)點(diǎn)中的結(jié)點(diǎn)只存存在的最小代價(jià)。結(jié)點(diǎn)的擴(kuò)展過(guò)程如下：根據(jù)優(yōu)先級(jí)從隊(duì)列中選取優(yōu)先級(jí)最高的元素，當(dāng)結(jié)點(diǎn)不是葉子結(jié)點(diǎn)的父節(jié)點(diǎn)時(shí)，擴(kuò)展該結(jié)點(diǎn)的所有子節(jié)點(diǎn)，在擴(kuò)展的過(guò)程中需要根據(jù)計(jì)算所得的下界與當(dāng)前求解得到的最優(yōu)解進(jìn)行對(duì)比，如果下界大于當(dāng)前的最優(yōu)解則對(duì)相應(yīng)的子節(jié)點(diǎn)時(shí)進(jìn)行剪枝處理，否則擴(kuò)展該子節(jié)點(diǎn)，將其加入到隊(duì)列中。當(dāng)當(dāng)前所訪(fǎng)問(wèn)的結(jié)點(diǎn)為葉子結(jié)點(diǎn)的父節(jié)點(diǎn)時(shí)，判斷當(dāng)前費(fèi)用+當(dāng)前結(jié)點(diǎn)到葉子結(jié)點(diǎn)的費(fèi)用+葉子結(jié)點(diǎn)到起始結(jié)點(diǎn)的費(fèi)用之和是否優(yōu)于最優(yōu)解，如果是則更新最優(yōu)解，并將當(dāng)前的解加入到隊(duì)列中。如果不是則繼續(xù)取隊(duì)列中的元素進(jìn)行擴(kuò)

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

7、一邊elsefor(int j =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、分支限界法核心代碼：public float fzxj(int m)int n=m.length-1;/節(jié)點(diǎn)數(shù)LinkedList heap

8、=new LinkedList();/minOuti=i的最小出邊費(fèi)用float minOut=new floatn+1;float minSum=0;/最小出邊費(fèi)用和for(int i=1;i=n;i+)/針對(duì)每個(gè)節(jié)點(diǎn)，找到最小出邊/計(jì)算minOuti和minSumfloat min=Float.MAX_VALUE;for(int j=1;j=n;j+)if(mapijFloat.MAX_VALUE&mapijmin)min=mapij;if(min=Float.MAX_VALUE)return Float.MAX_VALUE;minOuti=min;minSum+=min;/初始化int

9、x=new intn;for(int i=0;in;i+)xi=i+1;TSPnode enode=new TSPnode(0,0,minSum,0,x);float bestc=Float.MAX_VALUE;/搜索排列空間樹(shù)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)/再加兩條邊構(gòu)成回路/所構(gòu)成回路是否優(yōu)于當(dāng)前最優(yōu)解if(mapxn-2xn-1!=-1&mapxn-11!=-1&enode.cost+mapxn-2xn-1+mapxn-11bestc)/找到費(fèi)用更小的回路bestc

10、=enode.cost+mapxn-2xn-1+mapxn-11;enode.cost=bestc;enode.lcost=bestc;enode.p+;heap.add(enode);Collections.sort(heap);else/內(nèi)部結(jié)點(diǎn)/產(chǎn)生當(dāng)前擴(kuò)展結(jié)點(diǎn)的兒子結(jié)點(diǎn)for(int i=enode.p+1;in;i+)if(mapxenode.pxi!=-1)/可行兒子結(jié)點(diǎn)float cc=enode.cost+mapxenode.pxi;float rcost=enode.rcost=minOutxenode.p;float b=cc+rcost;/下界if(bbestc)/子樹(shù)可

11、能含有最優(yōu)解，結(jié)點(diǎn)插入最小堆int xx=new intn;for(int j=0;jn;j+)xxj=xj;xxenode.p+1=xi;xxi=xenode.p+1;TSPnode node=new TSPnode(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(int i=0;in;i+)mi+1=xi;return bestc;五、算法復(fù)雜性理論分析1、回溯法TSP問(wèn)題是排列樹(shù)問(wèn)題，因而該算法的時(shí)間復(fù)雜度為O(n!)。2、分支限界法TSP問(wèn)題是排列樹(shù)問(wèn)題，在分支限界法界函數(shù)無(wú)法剪枝時(shí)有最壞情況時(shí)間復(fù)雜性為O(n!)，但通過(guò)界函數(shù)剪枝可以使復(fù)雜度下降。六、算法代碼（單獨(dú)文件提交）見(jiàn)項(xiàng)目文件七、算法測(cè)試（報(bào)告只寫(xiě)測(cè)試方法與用例設(shè)計(jì)方法與結(jié)果，測(cè)試程序單獨(dú)提交）問(wèn)題規(guī)?；厮莘ǚ种藿绶?3ms852ms1010ms1323ms20272510ms7541ms25-20723ms-八、實(shí)驗(yàn)中的問(wèn)題總結(jié)回溯法：優(yōu)點(diǎn)：可以快速的找到一組解，并在此基礎(chǔ)之上進(jìn)行調(diào)整。當(dāng)搜索