算法分析設計回溯法求解裝載問題實驗報告

1、算法分析設計回溯法求解裝載問題實驗報告 算法分析設計回溯法求解裝載問題,完善版報告 回溯法求解裝載問題 一、方法一般原理 回溯法也稱為摸索法，該方法首先臨時放棄關(guān)于問題規(guī)模大小的限制，并將問題的候選解按某種挨次逐一枚舉和檢驗。當發(fā)覺當前候選解不行能是解時，就選擇下一個候選解；如果當前候選解除了還不滿足問題規(guī)模要求外，滿足全部其他要求時，連續(xù)擴大當前候選解的規(guī)模，并連續(xù)摸索。假如當前候選解滿足包括問題規(guī)模在內(nèi)的全部要求時，該候選解就是問題的一個解。在回溯法中，放棄當前候選解，查找下一個候選解的過程稱為回溯。擴大當前候選解的規(guī)模，以連續(xù)摸索的過程稱為向前摸索。 可用回溯法求解的問題P，通常要能表達

2、為：對于已知的由n元組（x1，x2，xn）組成的一個狀態(tài)空間E=（x1，x2，xn）xiSi ，i=1，2，n，給定關(guān)于n元組中的一個重量的一個約束集D，要求E中滿足D的全部約束條件的全部n元組。其中Si是重量xi的定義域，且 |Si| 有限，i=1，2，n。我們稱E中滿足D的全部約束條件的任一n元組為問題P的一個解。 解問題P的最儉樸的方法就是枚舉法，即對E中的全部n元組逐一地檢測其是否滿足D的全部約束，若滿足，則為問題P的一個解。但明顯，其計算量是相當大的。 我們發(fā)覺，對于很多問題，所給定的約束集D具有完備性，即i元組（x1，x2，xi）滿足D中僅涉及到x1，x2，xi的全部約束意味著j（

3、ji）元組（x1，x2，xj）肯定也滿足D中僅涉及到x1，x2，xj的全部約束，i=1，2，n。換句話說，只要存在0jn-1，使得（x1，x2，xj）違反D中僅涉及到x1，x2，xj的約束之一，則以（x1，x2，xj）為前綴的任何n元組（x1，x2，xj，xj+1，xn）肯定也違反D中僅涉及到x1，x2，xi的一個約束，nij。因此，對于約束集D具有完備性的問題P，一旦檢測斷定某個j元組（x1，x2，xj）違反D中僅涉及x1，x2，xj的一個約束，就可以確定，以（x1，x2，xj）為前綴的任何n元組（x1，x2，xj，xj+1，xn）都不會是問題P的解，因而就不必去搜索它們、檢測它們?；厮莘ㄕ?/p>

4、是針對這類問題，利用這類問題的上述性質(zhì)而提出來的比枚舉法效率更高的算法。 回溯法首先將問題P的n元組的狀態(tài)空間E表示成一棵高為n的帶權(quán)有序樹T，把在E中求問題P的全部解轉(zhuǎn)化為在T中搜索問題P的全部解。樹T類似于檢索樹，它可以這樣構(gòu)造： 設Si中的元素可排成xi ，xi ，xi (1)(2)(mi)(1)(2)(mi-1) ，|Si| =mi，i=1，2，n。從根開頭，讓T的第I層的每一個結(jié)點都有mi個兒子。這mi個兒子到它們的雙親的邊，按從左到右的次序，分別帶權(quán)xi+1 ，xi+1 ，xi+1 ，i=0，1，2，n-1。照這種構(gòu)造方式，E中的一個n元組（x1，x2，xn）對應于T中的一個葉子結(jié)

5、點，T的根到這個葉子結(jié)點的路徑上依次的n條邊的權(quán)分別為x1，x2，xn，反之亦然。另外，對于任意的0in-1，E中n元組（x1，x2，xn）的一個前綴I元組（x1，x2，xi）對應于T中的一個非葉子結(jié)點，T的根到這個非葉子結(jié)點的路徑上依次的I條邊的權(quán)分別為x1，x2，xi，反之亦然。格外，E中的任意一個n元組的空前綴（），對應于T的根。 因而，在E中查找問題P的一個解等價于在T中搜索一個葉子結(jié)點，要求從T的根到該 算法分析設計回溯法求解裝載問題,完善版報告 葉子結(jié)點的路徑上依次的n條邊相應帶的n個權(quán)x1，x2，xn滿足約束集D的全部約束。在T中搜索所要求的葉子結(jié)點，很自然的一種方式是從根動身，

6、按深度優(yōu)先的策略逐步深化，即依次搜索滿足約束條件的前綴1元組（x1i）、前綴2元組（x1，x2）、，前綴I元組（x1，x2，xi），直到i=n為止。 在回溯法中，上述引入的樹被稱為問題P的狀態(tài)空間樹；樹T上任意一個結(jié)點被稱為問題P的狀態(tài)結(jié)點；樹T上的任意一個葉子結(jié)點被稱為問題P的一個解狀態(tài)結(jié)點；樹T上滿足約束集D的全部約束的任意一個葉子結(jié)點被稱為問題P的一個回答狀態(tài)結(jié)點，它對應于問題P的一個解。 二、描述問題 有一批共n個集裝箱要裝上2艘載重量分別為c1和c2的輪船，其中集裝箱i的重量為n wi ，且 i 1艘輪船。假如有，請給出該方案。 wi c1 c2 ，要求確定是否有一個合理的裝載方案可

7、將這n個集裝箱裝上這2 三、由原理得到的算法、算法的簡單度、改進 1、 可得算法 回溯法解裝載問題時，用子集樹表示解空間最合適。 void Backtrack(int t) if(tn) Output(x); else for(int i=0; iz; i+) xt = i; if(Constraint(t) Bound(t) Backtrack(t+1); Maxloading調(diào)用遞歸函數(shù)backtrack實現(xiàn)回溯。Backtrack（i）搜索子集樹第i層子樹。in時，搜索至葉節(jié)點，若裝載量bestw，更新bestw。 當i=n時，擴展節(jié)點Z是子集樹內(nèi)部節(jié)點。左兒子節(jié)點當cw+wi=c時進入

8、左子樹，對左子樹遞歸搜索。右兒子節(jié)點表示xi=0的情形。 2、時間簡單度 Backtrack動態(tài)的生成解空間樹。每個節(jié)點花費O（1）時間。Backtrack執(zhí)行時間簡單度為nO(2)。另外Backtrack還需要額外O(n)遞歸?？臻g。 3、可能的改進 算法分析設計回溯法求解裝載問題,完善版報告 可以再加入一個上界函數(shù)來剪去已經(jīng)不含最優(yōu)解的子樹。設Z是解空間樹第i層上的一個當前擴展結(jié)點，curw是當前載重量，maxw是已經(jīng)得到的最優(yōu)載重量，假如能在當前結(jié)點確定curw+剩下的全部載重量 maxw 則可以剪去些子樹。所以可以引入一個變量r表示剩余的全部載重量。雖然改進后的算法時間簡單度不變，但是

9、平均狀況下改進后算法檢查 結(jié)點數(shù)較少。 進一步改進： （1） 首先運行只計算最優(yōu)值算法，計算最優(yōu)裝載量，再運行backtrack算法，并在算法 中將bestw置為W，在首次到葉節(jié)點處終止。 （2） 在算法中動態(tài)更新bestw。每當回溯一層，將xi存入bestxi.從而算法更新bestx n所需時間為O(2)。 四、算法實現(xiàn) int Backtrack(int i)/搜索第i層節(jié)點 int j_index; /假如到達葉結(jié)點，則推斷當前的cw，假如比前面得到的最優(yōu)解bestw好，則替換原最優(yōu)解。 if(in) if(cwbestw) for(j_index=1; j_index=n; j_ind

10、ex+) bestxj_index=xj_index; bestw=cw; return 1; /搜索子樹 r-=wi; if(cw+wi=c)/搜索左子樹,假如當前剩余空間可以放下當前物品也就是， cw + w i = c xi=1; cw+=wi;/把當前載重 cw += w i Backtrack(i+1);/遞歸訪問其左子樹，Backtrack( i + 1 ) cw-=wi;/訪問結(jié)束，回到調(diào)用點， cw - = w i if(cw+rbestw)/搜索右子樹 算法分析設計回溯法求解裝載問題,完善版報告 xi=0; Backtrack(i+1); r+=wi; int maxload

11、ing(int mu,int c,int n,int *mx) loading x; x.w=mu; x.x=mx; x.c=c; x.n=n; x.bestw=0; x.cw=0; x.Backtrack(1); return x.bestw; 五、總結(jié) 由此，我們可以總結(jié)出回溯法的一般步驟： （1）針對所給問題，定義問題的解空間； （2）確定易于搜索的解空間結(jié)構(gòu)； （3）以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避開無效搜索。 通過DFS思想完成回溯，完整過程如下： (1)設置初始化的方案（給變量賦初值，讀入已知數(shù)據(jù)等）。 (2)變換方式去摸索，若全部試完則轉(zhuǎn)(7)。 (3)推斷此

12、法是否勝利（通過約束函數(shù)），不勝利則轉(zhuǎn)(2)。 (4)摸索勝利則前進一步再摸索。 (5)正確方案還未找到則轉(zhuǎn)(2)。 (6)已找到一種方案則記錄并打印。 (7)退回一步（回溯），若未退到頭則轉(zhuǎn)(2)。 (8)已退到頭則結(jié)束或打印無解。 可以看出，回溯法的優(yōu)點在于其程序結(jié)構(gòu)明確，可讀性強，易于理解，而且通過對問題的分析可以大大提高運行效率。但是，對于可以得出明顯的遞推公式迭代求解的問題，還是不要用回溯法，由于它花費的時間比較長。 六、附錄（源碼） #includestdlib.h 算法分析設計回溯法求解裝載問題,完善版報告 #includestdio.h #includeiostream.h t

13、ypedef int Status; typedef int Type; int n=0; /集裝箱數(shù) Type *x=(Type*)malloc(50)*sizeof(Type);/當前解 Type *bestx=(Type*)malloc(50)*sizeof(Type);/當前最優(yōu)解 Type c=0, /第一艘輪船的載重量 cw=0, /當前載重量 bestw=0, /當前最優(yōu)載重量 r=0, *w=(Type*)malloc(50)*sizeof(Type); /集裝箱重量數(shù)組 int Backtrack(int i)/搜索第i層節(jié)點 int j_index; /假如到達葉結(jié)點，則推

14、斷當前的cw，假如比前面得到的最優(yōu)解bestw好，則替換原最優(yōu)解。 if(in) if(cwbestw) for(j_index=1; j_index=n; j_index+) bestxj_index=xj_index; bestw=cw; return 1; /搜索自樹 r-=wi; if(cw+wi=c)/搜索左子樹,假如當前剩余空間可以放下當前物品也就是， cw + w i = c xi=1; cw+=wi;/把當前載重 cw += w i Backtrack(i+1);/遞歸訪問其左子樹，Backtrack( i + 1 ) cw-=wi;/訪問結(jié)束，回到調(diào)用點， cw - = w

15、i if(cw+rbestw)/搜索右子樹 xi=0; 算法分析設計回溯法求解裝載問題,完善版報告 Backtrack(i+1); r+=wi; Type* Initiate() int index=1; printf(輸入集裝箱個數(shù)：); scanf(%d,n); printf(輸入輪船載重量：); scanf(%d,c); while(index=n)/數(shù)組從1號單元開頭存儲 printf(輸入集裝箱%d的重量：,index); scanf(%d,windex); index+; bestw = 0; cw = 0; r = 0; for(index =1;index = n; index+) r += windex; /初始時r為全體物品的重量和 printf(n=%d c=%d cw=%d bestw=%d r=%