1、回溯法求解裝載問題一、方法一般原理回溯法也稱為試探法，該方法首先暫時放棄關于問題規(guī)模人小的限制，并將問題的候選解按某種順序逐一枚舉和檢驗。當發(fā)現當前候選解不可能是解時，就選擇下一個候選解；倘若當前候選解除了還不滿足問題規(guī)模要求外，滿足所有其他要求時，繼續(xù)擴人當前候選解的規(guī)模，并繼續(xù)試探。如果當前候選解滿足包括問題規(guī)模在內的所有要求時，該候選解就是問題的一個解。在回溯法中，放棄當前候選解，尋找卞一個候選解的過程稱為回溯。擴人當前候選解的規(guī)模，以繼續(xù)試探的過程稱為向前試探。可用回溯法求解的問題P,通常要能表達為：對于已知的由n元組（X1,x2,，xa）組成的一個狀態(tài)空間E=（xi,X2，xj|Xi

2、ESi,i二1,2,，n,給定關于n元組中的一個分量的一個約束集D,要求E中滿足D的全部約束條件的所有n元組。其中&是分量監(jiān)的定義域，且|SJ有限，i=l,2,，no我們稱E中滿足D的全部約束條件的任一n元組為問題P的一個解。解問題P的最樸素的方法就是枚舉法，即對E中的所有n元組逐一地檢測其是否滿足D的全部約束，若滿足，則為問題P的一個解。但顯然，其計算量是相當大的。我們發(fā)現，對于許多問題，所給定的約束集D具有完備性，即i元組（X1,x2,，監(jiān)）滿足D中僅涉及到畑，&的所有約束意味著j（ji）元組（&,劉,，Xj）一定也滿足D中僅涉及到x2,，的所有約束，i=l,2,，no換句話說，只要存在0

3、WjWn-l,使得（xi,X：,，）違反D中僅涉及到xi,x2,，為的約束之一，則以（xi,X2,，Xj）為前綴的任何n元組（X1,X2,，Xj,Xj+1,，xa）一定也違反D中僅涉及到xx,也，監(jiān)的一個約束，因此，對于約束集D具有完備性的問題P,旦檢測斷定某個j元組（&,x:,，禺）違反D中僅涉及x：,，的一個約束，就可以肯定，以（X1,X2,，Xj）為前綴的任何n元組（X1,X2，Xj,Xj+11，xa）都不會是問題P的解，因而就不必去搜索它們、檢測它們。回溯法正是針對這類問題，利用這類問題的上述性質而提出來的比枚舉法效率更高的算法?；厮莘ㄊ紫葘栴}P的n元組的狀態(tài)空間E表示成一棵高為n的

4、帶權有序樹T,把在E中求問題P的所有解轉化為在T中搜索問題P的所有解。樹T類似于檢索樹，它可以這樣構造：設S沖的元素可排成&,xj2）,，x嚴,|Si|壬,i=l,2,，no從根開始,讓T的第I層的每一個結點都有血個兒子。這血個兒子到它們的雙親的邊，按從左到右的次序，分別帶權Xi+1,Xi+1,，Xi+i,i二0,1,2,，n-lo照這種構造方式,E中的一個n元組（&,x2,，xj對應于T中的一個葉子結點，T的根到這個葉子結點的路徑上依次的n條邊的權分別為也，x2,，反之亦然。另外，對于任意的0WiWn-l,E中n元組（劉，xa）的一個前綴I元組（xi,也，Xi）對應于T中的一個非葉子結點，T

5、的根到這個非葉子結點的路徑上依次的I條邊的權分別為Xi，也，Xi,反之亦然。特別，E中的任意一個n元組的空前綴（），對應于T的根。因而，在E中尋找問題P的一個解等價于在T中搜索一個葉子結點，要求從T的根到該葉子結點的路徑上依次的n條邊相應帶的n個權劉，x2,，x滿足約束集D的全部約束。在T中搜索所要求的葉子結點，很自然的一種方式是從根出發(fā)，按深度優(yōu)先的策略逐步深入,即依次搜索滿足約束條件的前綴1元組(知)、前綴2元組(&,禺)、，前綴I元組(&,X2,，Xi),，直到i=n為止。在回溯法中，上述引入的樹被稱為問題P的狀態(tài)空間樹；樹T上任意一個結點被稱為問題P的狀態(tài)結點：樹T上的任意一個葉子結點

6、被稱為問題P的一個解狀態(tài)結點；樹T上滿足約束集D的全部約束的任意一個葉子結點被稱為問題P的一個回答狀態(tài)結點，它對應于問題P的一個解。二、描述問題有一匕共n個集裝箱要裝上2艘載重量分別為6和心的輪船，其中集裝箱i的重量為他，且Wxn)Output(x);elsefor(inti二0;in時，搜索至葉節(jié)點，若裝載量bestw,更新bestwo當i=n時，擴展節(jié)點Z是子集樹內部節(jié)點。左兒子節(jié)點當cw+win)if(cwbestw)for(j_index=l;j_index=n;j_index+)bestxj_index=xj_index;bestw=cw;return1;)搜索子樹r-二wi;if(

7、cw+wi=c)/搜索左子樹，如果當前剩余空間可以放下當前物品也就是，cw+wibestvz)/搜索右子樹xi二0;Backtrack(i+1);)r+=wil;intmaxloading(intinu,intc,intn,int*mx)loadingx;x.w=inu;x.x二mx;x.c=c;x.n=n;x.bestw二0;x.cw=0;x.Backtrack(1);returnx.bestw;五、總結由此，我們可以總結出回溯法的一般步驟：針對所給問題，定義問題的解空間；確定易于搜索的解空間結構；以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數避免無效搜索。通過DFS思想完成回溯，完整過

8、程如下：設置初始化的方案(給變量賦初值，讀入已知數據等)。變換方式去試探，若全部試完則轉(7)。判斷此法是否成功(通過約束函數)，不成功則轉(2)。試探成功則前進一步再試探。正確方案還未找到則轉(2)已找到一種方案則記錄并打印。退回一步(回溯)，若未退到頭則轉(2)。已退到頭則結束或打印無解?？梢钥闯觯厮莘ǖ膬?yōu)點在于其程序結構明確，可讀性強，易于理解，而且通過對問題的分析可以人人提高運行效率。但是，對于可以得出明顯的遞推公式迭代求解的問題，還是不要用回溯法，因為它花費的時間比較長。附錄(源碼)#include#include#includetypedefintStatus;typedefin

9、tType;intn二0;集裝箱數Type*x=(Type*)malloc(50)*sizeof(Type);/當前解Type*bestx=(Type*)malloc(50)*sizeof(Type);當前最優(yōu)解Typec二0,/第一艘輪船的載重量cw二0,當前載重量bestw=0,當前最優(yōu)載重量r二0,*w=(Type*)malloc(50)*sizeof(Type);集裝箱重量數組intBacktrack(inti)搜索第i層節(jié)點intj_index;如果到達葉結點，則判斷當前的cw,如果比前面得到的最優(yōu)解bestw好，則替換原最優(yōu)解。辻(in)if(cwbestw)for(j_index

10、=l;j_index=n;j_index+)bestxj_index=xj_index;bestw=cw.:return1;)搜索自樹r-二wi;if(cw+wi=c)/搜索左子樹，如果當前剩余空間可以放下當前物品也就是，cw+wibestv7)/搜索右子樹i二0;Backtrack(i+1);)r+=wil;Type*Initiate()intindex=l;printfC輸入集裝箱個數：“)；scanf&n);printf(z/輸入輪船載重量：”)；scanf&c);曲訂e(index=n)/數組從1號單元開始存儲printf(輸入集裝箱%(1的重量：，index);scanf&windex);index+;)bestw=0;cw=0;r=0;for(index=1;index=n;index+)r+=windex;/初始時r為全體物品的重量和printfc=%dcw=%dbestw=%dn,c,cw,bestw,r);for(index=l;index=n;i