西北工業(yè)大學算法設計實驗2

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

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

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

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

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

6、展。但取出的元素為葉子節(jié)點或者隊列中的元素為空的時候，則搜索結束，輸出當前的最優(yōu)解。四、算法實現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;/重復計算了上

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é)點數LinkedList heap

8、=new LinkedList();/minOuti=i的最小出邊費用float minOut=new floatn+1;float minSum=0;/最小出邊費用和for(int i=1;i=n;i+)/針對每個節(jié)點，找到最小出邊/計算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;/搜索排列空間樹while(enode!=null&enode.pn-1)/非葉節(jié)點x=enode.path;if(enode.p=n-2)/當前擴展結點是葉節(jié)點的父節(jié)點/再加兩條邊構成回路/所構成回路是否優(yōu)于當前最優(yōu)解if(mapxn-2xn-1!=-1&mapxn-11!=-1&enode.cost+mapxn-2xn-1+mapxn-11bestc)/找到費用更小的回路bestc

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

11、能含有最優(yōu)解，結點插入最小堆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);/取下一個擴展結點enode=heap.poll();/將最優(yōu)解復制到v1.nfor(int i=0;in;i+)mi+1=xi;return bestc;五、算法復雜性理論分析1、回溯法TSP問題是排列樹問題，因而該算法的時間復雜度為O(n!)。2、分支限界法TSP問題是排列樹問題，在分支限界法界函數無法剪枝時有最壞情況時間復雜性為O(n!)，但通過界函數剪枝可以使復雜度下降。六、算法代碼（單獨文件提交）見項目文件七、算法測試（報告只寫測試方法與用例設計方法與結果，測試程序單獨提交）問題規(guī)模回溯法分支限界法53ms852ms1010ms1323ms20272510ms7541ms25-20723ms-八、實驗中的問題總結回溯法：優(yōu)點：可以快速的找到一組解，并在此基礎之上進行調整。當搜索