第五章回溯法

1、第五章 回溯法 學習要點 理解回溯法的深度優(yōu)先搜索策略 掌握用回溯法解題的算法框架 1）遞歸回溯最優(yōu)子結(jié)構(gòu)性質(zhì) 2）迭代回溯貪心選擇性質(zhì) 3）子集樹算法框架 4）排列樹算法框架 通過應(yīng)用范例學習回溯法的設(shè)計策略 1）0-1背包問題；引言有許多問題，當需要找出它的解集或者要求回答什么解是滿足某些約束條件的最佳解時，往往要使用回溯法。回溯法的基本做法是搜索，或是一種組織得井井有條的、能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數(shù)相當大的問題?；厮莘ㄔ趩栴}的解空間樹中，按深度優(yōu)先策略，從根結(jié)點出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點時，先判斷該結(jié)點是否包含問題的解：如果肯定不包含，

2、則跳過對該結(jié)點為根的子樹的搜索，逐層向其祖先結(jié)點回溯；否則，進入該子樹，繼續(xù)按深度優(yōu)先策略搜索。5.1 回溯法的算法框架本節(jié)介紹回溯法算法框架的有關(guān)問題： 一、問題的解空間 二、回溯法的基本思想 三、遞歸回溯 四、迭代回溯 五、子集樹與排列樹一、問題的解空間 應(yīng)用回溯法解問題時，首先應(yīng)明確定義問題的解空間。問題的解空間應(yīng)至少包含問題的一個(最優(yōu))解。 問題的解向量：回溯法希望一個問題的解能夠表示成一個n元式(x1,x2,xn)的形式。 顯約束：對分量xi的取值限定。 隱約束：為滿足問題的解而對不同分量之間施加的約束。 解空間：對于問題的一個實例，解向量滿足顯式約束條件的所有多元組，構(gòu)成了該實例

3、的一個解空間。 注意：同一個問題可以有多種表示，有些表示方法更簡單，所需表示的狀態(tài)空間更?。ù鎯α可伲阉鞣椒ê唵危?。 例如，對于有n種可選物品的0-1背包問題，其解空間由長度為n的0-1向量組成。n=3時的0-1背包問題用完全二叉樹表示的解空間二、回溯法的基本思想 回溯法的基本步驟： (1)針對所給問題，定義問題的解空間； (2)確定易于搜索的解空間結(jié)構(gòu)； (3)以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。 常用剪枝函數(shù)： 用約束函數(shù)在擴展結(jié)點處剪去不滿足約束的子樹； 用限界函數(shù)剪去得不到最優(yōu)解的子樹。 關(guān)于復雜性： 用回溯法解題的一個顯著特征是在搜索過程中動態(tài)產(chǎn)生問題的

4、解空間。在任何時刻，算法只保存從根結(jié)點到當前擴展結(jié)點的路徑。如果解空間樹中從根結(jié)點到葉結(jié)點的最長路徑的長度為h(n)，則回溯法所需的計算空間通常為O(h(n)。而顯式地存儲整個解空間則需要O(2h(n)或O(h(n)!)內(nèi)存空間。生成問題狀態(tài)的基本方法 擴展結(jié)點：一個正在產(chǎn)生兒子的結(jié)點稱為擴展結(jié)點 活結(jié)點：一個自身已生成但其兒子還沒有全部生成的節(jié)點稱做活結(jié)點 死結(jié)點：一個所有兒子已經(jīng)產(chǎn)生的結(jié)點稱做死結(jié)點 深度優(yōu)先的問題狀態(tài)生成法：如果對一個擴展結(jié)點R，一旦產(chǎn)生了它的一個兒子C，就把C當做新的擴展結(jié)點。在完成對子樹C（以C為根的子樹）的窮盡搜索之后，將R重新變成擴展結(jié)點，繼續(xù)生成R的下一個兒子（

5、如果存在） 寬度優(yōu)先的問題狀態(tài)生成法：在一個擴展結(jié)點變成死結(jié)點之前，它一直是擴展結(jié)點 回溯法：為了避免生成那些不可能產(chǎn)生最佳解的問題狀態(tài)，要不斷地利用限界函數(shù)(bounding function)來處死那些實際上不可能產(chǎn)生所需解的活結(jié)點，以減少問題的計算量。具有限界函數(shù)的深度優(yōu)先生成法稱為回溯法。示例1 0-1背包問題 n=3, C=30, w=16, 15, 15, v=45, 25, 25開始時，Cr=C=30，V=0，A為唯一活結(jié)點，也是當前擴展結(jié)點擴展A，先到達B結(jié)點Cr=Cr-w1=14，V=V+v1=45此時A、B為活結(jié)點，B成為當前擴展結(jié)點擴展B，先到達DCrw2，D導致一個不可

6、行解，回溯到B再擴展B到達EE可行，此時A、B、E是活結(jié)點，E成為新的擴展結(jié)點擴展E，先到達JCr45，皆得到一個可行解x=(0,1,1)，V=50L不可擴展，成為死結(jié)點，返回到F再擴展F到達MM是葉結(jié)點，且2550，不是最優(yōu)解M不可擴展，成為死結(jié)點，返回到FF沒有可擴展結(jié)點，成為死結(jié)點，返回到C再擴展C到達GCr=30，V=0，活結(jié)點為A、C、G，G為當前擴展結(jié)點擴展G，先到達N，N是葉結(jié)點，且2550，不是最優(yōu)解，又N不可擴展，返回到G再擴展G到達O，O是葉結(jié)點，且050，不是最優(yōu)解，又O不可擴展，返回到GG沒有可擴展結(jié)點，成為死結(jié)點，返回到CC沒有可擴展結(jié)點，成為死結(jié)點，返回到AA沒有可

7、擴展結(jié)點，成為死結(jié)點，算法結(jié)束，最優(yōu)解X=(0,1,1)，最優(yōu)值V=50ACr=C=30，V=0Bw1=16，v1=45Cr=14，V=45C Cr=30，V=0DCrw2不可行解JCr45x=(0,1,1)Fw2=15，v2=25Cr=15，V=25M25n) output(x);elsefor (int i=f(n,t);i0) if (f(n,t)=g(n,t) for (int i=f(n,t);in) output(x); else for (int i=t;i=n;i+) xt=i; if (legal(t) backtrack(t+1); 5.6 0-1背包問題 解空間：子集樹

8、可行性約束函數(shù)：wixiC 上界函數(shù)：Bound() 算法：祥見P168-171templateTypep Knap:Bound(int i)/ 計算上界，貪心算法得到上界 Typew cleft = c - cw; / 剩余容量 Typep b = cp; / 以物品單位重量價值遞減序裝入物品 while (i = n & wi = cleft) cleft -= wi; b += pi; i+; / 裝滿背包 if (i = n) b += pi/wi * cleft; return b;嚴格按照P170中的算法解決下列問題： n=3, C=30, w=16, 15, 15, v=

9、45, 25, 25代碼#includeusing namespace std;double c;/背包容量int n; /物品數(shù)double w100;/物品重量數(shù)組double p100;/物品價值數(shù)組double cw=0;/當前重量double cp=0;/當前價值double bestp=0;/當前最優(yōu)值double bound(int i) double cleft,b; /計算上界 cleft=c-cw;/剩余容量 b=cp; /以物品單位重量價值遞減序裝入物品 while(i=n&wi=cleft) cleft-=wi; b+=pi; i+; /裝滿背包 if(in)

10、if(cpbestp) bestp=cp; return; if(cw+wibestp)/搜索右子樹 Backtrack(i+1);double Knapsack (double pp,double ww,double d)int i;double TP=0,TW=0;cw=0.0;cp=0.0;bestp=0.0;/計算所有物品的重量及價值for(i=1;i=n;i+)TP=TP+ppi;TW=TW+wwi;if(TW=d)/所有物品裝入背包bestp=TP;elseBacktrack(1);return bestp;int main()int i,j;double t,a,x100;cout請輸入物品種類數(shù)和最大載重量：n;cinc;cout請輸入各物品重量：endl;for(i=1;iwi;cout請輸入各物品價值：endl;for(i=1;ipi;/排序for(i=1