第5章回溯法5.1回溯法概述5.2求解0/1背包問題5.3求解裝載問題5.4求解子集和問題5.5求解n皇后問題5.6求解圖的m著色問題5.7求解任務分配問題5.8求解活動安排問題5.9求解流水作業(yè)調(diào)度問題5.1.1問題的解空間一個復雜問題的解決方案是由若干個小的決策步驟組成的決策序列，解決一個問題的所有可能的決策序列構(gòu)成該問題的解空間。回溯法概述初始狀態(tài)目標狀態(tài)…求解范圍（隱含解）

解空間應用回溯法求解問題時，首先應該明確問題的解空間。解空間中滿足約束條件的決策序列稱為可行解。一般來說，解任何問題都有一個目標，在約束條件下使目標達到最優(yōu)的可行解稱為該問題的最優(yōu)解。

問題的解由一個不等長或等長的解向量X={x1，x2，…，xn}組成，其中分量xi表示第i步的操作。

所有滿足約束條件的解向量組構(gòu)成了問題的解空間。

問題的解空間一般用樹形式來組織，也稱為解空間樹或狀態(tài)空間，樹中的每一個結(jié)點確定所求解問題的一個問題狀態(tài)。

樹的根結(jié)點位于第1層，表示搜索的初始狀態(tài)，第2層的結(jié)點表示對解向量的第一個分量做出選擇后到達的狀態(tài)，以此類推。

例如，以下求集合{a，b，c}的冪集的解空間樹：{a,b,c}AHID{a,b}JKE{a,c}{a}BLMF{b,c}NOG{c}{}C1111110000000元素a的選擇和不選擇元素b的選擇和不選擇元素c的選擇和不選擇求解過程分為3步，分別對a、b、c元素做決策，該解空間的每個葉子結(jié)點都構(gòu)成一個解。求解問題類型：找所有解找最優(yōu)解

【例5.1】有一個農(nóng)夫（人）過河問題，指在河東岸有一個農(nóng)夫、一只狼、一只雞和一袋谷子，只有當農(nóng)夫在現(xiàn)場時，狼不會把雞吃掉，雞也不會吃谷子，否則會出現(xiàn)這樣的情況。

另有一條小船，該船只能由農(nóng)夫操作，且最多只能載下農(nóng)夫和另一樣東西。設計一種過河方案，將農(nóng)夫、狼、雞和谷子借助小船運到河西岸。人狼雞谷東西初始狀態(tài)雞谷東西人狼狼谷東西人雞狼谷東西人雞狼谷東西人雞狼谷東西人雞谷東西雞狼人…東西人狼雞谷目標狀態(tài)解空間樹通常有兩種類型：子集樹：當所給的問題是從n個元素的集合S中找出滿足某種性質(zhì)的子集時，相應的解空間樹稱為子集樹。

{a,b,c}AHID{a,b}JKE{a,c}{a}BLMF{b,c}NOG{c}{}C1111110000000排列樹：當所給的問題是確定n個元素滿足某種性質(zhì)的排列時，相應的解空間樹稱為排列樹。

注意：問題的解空間樹是虛擬的，并不需要在算法運行時構(gòu)造一棵真正的樹結(jié)構(gòu)，然后再在該解空間樹中搜索問題的解，而是只存儲從根結(jié)點到當前結(jié)點的路徑。

實際上，有些問題的解空間因過于復雜或狀態(tài)過多難以畫出來。5.1.2什么是回溯法在包含問題的所有解的解空間樹中，按照深度優(yōu)先搜索的策略，從根結(jié)點（開始結(jié)點）出發(fā)搜索解空間樹。

當從狀態(tài)si搜索到狀態(tài)si+1后，如果si+1變?yōu)樗澜Y(jié)點，則從狀態(tài)si+1回退到si，再從si找其他可能的路徑，所以回溯法體現(xiàn)出走不通就退回再走的思路。si+1s1si…

回溯再找其他路徑

回溯法搜索解空間時，通常采用兩種策略避免無效搜索，提高回溯的搜索效率:

用約束函數(shù)在擴展結(jié)點處剪除不滿足約束的子樹；用限界函數(shù)剪去得不到問題解或最優(yōu)解的子樹。這兩類函數(shù)統(tǒng)稱為剪枝函數(shù)。歸納起來，用回溯法解題的一般步驟如下：確定問題的解空間樹，問題的解空間樹應至少包含問題的一個（最優(yōu)）解。確定結(jié)點的擴展規(guī)則。以深度優(yōu)先方式搜索解空間樹，并在搜索過程中可以采用剪枝函數(shù)來避免無效搜索?；厮莘?深度優(yōu)先搜索+剪枝結(jié)論：5.1.2什么是回溯法在包含問題的所有解的解空間樹中，按照深度優(yōu)先搜索的策略，從根結(jié)點（開始結(jié)點）出發(fā)搜索解空間樹。

首先根結(jié)點成為活結(jié)點（活結(jié)點是指自身已生成但其孩子結(jié)點沒有全部生成的結(jié)點），同時也成為當前的擴展結(jié)點（擴展結(jié)點是指正在產(chǎn)生孩子結(jié)點的結(jié)點）。

在當前的擴展結(jié)點處，搜索向縱深方向移至一個新結(jié)點。這個新結(jié)點就成為新的活結(jié)點，并成為當前擴展結(jié)點。

如果在當前的擴展結(jié)點處不能再向縱深方向移動，則當前擴展結(jié)點就成為死結(jié)點（死結(jié)點是指由根結(jié)點到該結(jié)點構(gòu)成的部分解不滿足約束條件，或者其子結(jié)點已經(jīng)搜索完畢）。

此時應往回移動（回溯）至最近的一個活結(jié)點處，并使這個活結(jié)點成為當前的擴展結(jié)點。

回溯法以這種方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已無活結(jié)點為止。

當從狀態(tài)si搜索到狀態(tài)si+1后，如果si+1變?yōu)樗澜Y(jié)點，則從狀態(tài)si+1回退到si，再從si找其他可能的路徑，所以回溯法體現(xiàn)出走不通就退回再走的思路。若用回溯法求問題的所有解時，需要回溯到根結(jié)點，且根結(jié)點的所有可行的子樹都要已被搜索完才結(jié)束。而若使用回溯法求任一個解時，只要搜索到問題的一個解就可以結(jié)束。si+1s1si…

回溯再找其他路徑

回溯法搜索解空間時，通常采用兩種策略避免無效搜索，提高回溯的搜索效率:

用約束函數(shù)在擴展結(jié)點處剪除不滿足約束的子樹；用限界函數(shù)剪去得不到問題解或最優(yōu)解的子樹。這兩類函數(shù)統(tǒng)稱為剪枝函數(shù)。歸納起來，用回溯法解題的一般步驟如下：針對所給問題，確定問題的解空間樹，問題的解空間樹應至少包含問題的一個（最優(yōu)）解。確定結(jié)點的擴展搜索規(guī)則。以深度優(yōu)先方式搜索解空間樹，并在搜索過程中可以采用剪枝函數(shù)來避免無效搜索。5.1.3回溯法的算法框架1.非遞歸回溯框架intx[n]; //x存放解向量，全局變量voidbacktrack(intn) //非遞歸框架{inti=1; //根結(jié)點層次為1while(i>=1) //尚未回溯到頭{if(ExistSubNode(t))

//當前結(jié)點存在子結(jié)點{for(j=下界;j<=上界;j++) //對于子集樹，j=0到1循環(huán){x[i]取一個可能的值;if(constraint(i)&&bound(i))

//x[i]滿足約束條件或界限函數(shù){if(x是一個可行解)

輸出x;else i++; //進入下一層次 }}}elsei--; //回溯：不存在子結(jié)點，返回上一層}}2.遞歸的算法框架intx[n]; //x存放解向量，全局變量voidbacktrack(inti) //求解子集樹的遞歸框架{if(i>n) //搜索到葉子結(jié)點,輸出一個可行解

輸出結(jié)果;else{for(j=下界;j<=上界;j++)//用j枚舉i所有可能的路徑{x[i]=j; //產(chǎn)生一個可能的解分量

…

//其他操作if(constraint(i)&&bound(i))backtrack(i+1);

//滿足約束條件和限界函數(shù),繼續(xù)下一層}}}（1）解空間為子集樹

【例5.3】有一個含n個整數(shù)的數(shù)組a，所有元素均不相同，設計一個算法求其所有子集（冪集）。

例如，a[]={1，2，3}，所有子集是：{}，{3}，{2}，{2，3}，{1}，{1，3}，{1，2}，{1，2，3}（輸出順序無關(guān)）。

解：顯然本問題的解空間為子集樹，每個元素只有兩種擴展，要么選擇，要么不選擇。

采用深度優(yōu)先搜索思路。解向量為x[]，x[i]=0表示不選擇a[i]，x[i]=1表示選擇a[i]。

用i掃描數(shù)組a，也就是說問題的初始狀態(tài)是（i=0，x的元素均為0），目標狀態(tài)是（i=n，x為一個解）。從狀態(tài)（i，x）可以擴展出兩個狀態(tài)：不選擇a[i]元素

下一個狀態(tài)為（i+1，x[i]=0）。選擇a[i]元素

下一個狀態(tài)為（i+1，x[i]=1）。voiddfs(inta[],intn,inti,intx[])//回溯算法求解向量x{if(i>=n)dispasolution(a,n,x);else{x[i]=0;dfs(a,n,i+1,x); //不選擇a[i]x[i]=1;dfs(a,n,i+1,x); //選擇a[i]}}

【例5.4】設計一個算法在1，2，…，9（順序不能變）數(shù)字之間插入+或-或什么都不插入，使得計算結(jié)果總是100的程序，并輸出所有的可能性。

例如：1+2+34–5+67–8+9=100。

解：用數(shù)組a存放1～9的整數(shù)，用字符數(shù)組op存放插入的運算符，op[i]表示在a[i]之前插入的運算符。

采用回溯法產(chǎn)生和為100的表達式，op[i]只能取值+、-或者空格（不同于上一個示例，這里是三選一）。設計函數(shù)：

fun(op，sum，prevadd，a，i)

其中：sum記錄考慮整數(shù)a[i]時前面表達式計算的整數(shù)和（初始值為a[0]），prevadd記錄前面表達式中的一個數(shù)值（初始值為a[0]），i從1開始到9結(jié)束，如果sum=100，得到一個解。voidfun(charop[],intsum,intprevadd,inta[],inti){if(i==N) //掃描完所有位置{if(sum==100) //找到一個解{printf("%d",a[0]); //輸出解for(intj=1;j<N;j++){if(op[j]!='') printf("%c",op[j]);printf("%d",a[j]);}printf("=100\n");}return;}op[i]='+'; //位置i插入'+'sum+=a[i]; //計算結(jié)果

fun(op,sum,a[i],a,i+1);

//繼續(xù)處理下一個位置sum-=a[i]; //回溯op[i]='-'; //位置i插入'-'sum-=a[i]; //計算結(jié)果fun(op,sum,-a[i],a,i+1);

//繼續(xù)處理下一個位置sum+=a[i]; //回溯op[i]=''; //位置i插入''sum-=prevadd; //先減去前面的元素值inttmp; //計算新元素值if(prevadd>0) tmp=prevadd*10+a[i]; //如prevadd=5,a[i]=6,結(jié)果為56else tmp=prevadd*10-a[i]; //如prevadd=-5,a[i]=6,結(jié)果為-56sum+=tmp; //計算合并結(jié)果

fun(op,sum,tmp,a,i+1);

//繼續(xù)處理下一個位置sum-=tmp; //回溯sumsum+=prevadd;}voidmain(){inta[N];charop[N]; //op[i]表示在位置i插入運算符for(inti=0;i<N;i++) //為a賦值為1,2，...,9 a[i]=i+1;printf("求解結(jié)果\n");

fun(op,a[0],a[0],a,1); //插入位置i從1開始}求解結(jié)果1+2+3-4+5+6+78+9=1001+2+34-5+67-8+9=1001+23-4+5+6+78-9=1001+23-4+56+7+8+9=10012+3+4+5-6-7+89=10012+3-4+5+67+8+9=10012-3-4+5-6+7+89=100123+4-5+67-89=100123+45-67+8-9=100123-4-5-6-7+8-9=100123-45-67+89=100（2）解空間為排列樹intx[n]; //x存放解向量，并初始化voidbacktrack(inti) //求解排列樹的遞歸框架{if(i>n) //搜索到葉子結(jié)點,輸出一個可行解

輸出結(jié)果;else{for(j=i;j<=n;j++) //用j枚舉i所有可能的路徑{…

//第i層的結(jié)點選擇x[j]的操作

swap(x[i],x[j]);

//為保證排列中每個元素不同,通過交換來實現(xiàn)if(constraint(i)&&bound(i)) backtrack(i+1); //滿足約束條件和限界函數(shù)，進入下一層

swap(x[i],x[j]);

//恢復狀態(tài)

…

//第i層的結(jié)點選擇x[j]的恢復操作}}}

【例5.5】有一個含n個整數(shù)的數(shù)組a，所有元素均不相同，求其所有元素的全排列。

例如，a[]={1，2，3}，得到結(jié)果是（1，2，3）、（1，3，2）、（2，3，1）、（2，1，3）、（3，1，2）、（3，2，1）。{1,2,3}{1,2,3}3{1,3,2}2{1,2,3}2{1,3,2}3{2,1,3}3{2,3,1}1{2,1,3}1{2,3,1}3{3,2,1}1{3,1,2}2{3,2,1}2{3,1,2}1{1,2,3}1{2,1,3}2{3,2,1}3產(chǎn)生了所有的解voiddfs(inta[],intn,inti) //求a[0..n-1]的全排列{if(i>=n) //遞歸出口dispasolution(a,n);else{for(intj=i;j<n;j++){swap(a[i],a[j]); //交換a[i]與a[j]

dfs(a,n,i+1);swap(a[i],a[j]); //交換a[i]與a[j]：恢復}}}5.1.4回溯法與深度優(yōu)先遍歷的異同兩者的相同點：

回溯法在實現(xiàn)上也是遵循深度優(yōu)先的，即一步一步往前探索，而不像廣度優(yōu)先遍歷那樣，由近及遠一片一片地搜索。兩者的不同點：

（1）訪問序不同：深度優(yōu)先遍歷目的是“遍歷”，本質(zhì)是無序的。而回溯法目的是“求解過程”，本質(zhì)是有序的。

（2）訪問次數(shù)的不同：深度優(yōu)先遍歷對已經(jīng)訪問過的頂點不再訪問，所有頂點僅訪問一次。而回溯法中已經(jīng)訪問過的頂點可能再次訪問。

（3）剪枝的不同：深度優(yōu)先遍歷不含剪枝，而很多回溯算法采用剪枝條件剪除不必要的分枝以提高效能。5.1.5回溯法算法的時間分析通常以回溯算法的解空間樹中的結(jié)點數(shù)作為算法的時間分析依據(jù)，假設解空間樹共有n層。第1層有m0個滿足約束條件的結(jié)點，每個結(jié)點有m1個滿足約束條件的結(jié)點；第2層有m0m1個滿足約束條件的結(jié)點，同理，第3層有m0m1m2個滿足約束條件的結(jié)點。第n層有m0m1…mn-1個滿足約束條件的結(jié)點，則采用回溯法求所有解的算法的執(zhí)行時間為

T(n)=m0+m0m1+m0m1m2+…+m0m1m2…mn-1。通常情況下，回溯法的效率會高于蠻力法。5.2求解0/1背包問題

【問題描述】有n個重量分別為{w1，w2，…，wn}的物品，它們的價值分別為{v1，v2，…，vn}，給定一個容量為W的背包。

設計從這些物品中選取一部分物品放入該背包的方案，每個物品要么選中要么不選中，要求選中的物品不僅能夠放到背包中，而且滿足重量限制具有最大的價值。第4章采用蠻力法求解，這里采用回溯法求解該問題。

用w[1..n]/v[1..n]存放物品信息，x[1..n]數(shù)組存放最優(yōu)解，其中每個元素取1或0，x[i]=1表示第i個物品放入背包中，x[i]=0表示第i個物品不放入背包中。

這是一個求最優(yōu)解問題。找到更優(yōu)解(op,tv)(x,maxv)。1.裝入背包中物品重量和恰好為W解空間是一棵子集樹！

對第i層上的某個分枝結(jié)點，對應的狀態(tài)為dfs(i，tw，tv，op)，其中tw表示裝入背包中的物品總重量，tv表示背包中物品總價值，op記錄一個解向量。該狀態(tài)的兩種擴展如下：第i層結(jié)點：dfs(i，tw，tv，op)選擇第i個物品：op[i]=1，tw=tw+w[i]，tv=tv+v[i]dfs(i+1，tw，tv，op)不選擇第i個物品：op[i]=0tw不變tv不變dfs(i+1，tw，tv，op)第i+1層結(jié)點第i層結(jié)點：dfs(i，tw，tv，op)選擇第i個物品：op[i]=1，tw=tw+w[i]，tv=tv+v[i]不選擇第i個物品：op[i]=0tw不變tv不變第i+1層結(jié)點第n+1層結(jié)點葉子結(jié)點表示已經(jīng)對n個物品做了決策。對所有葉子結(jié)點進行比較求出滿足tw==W的最大maxv，對應的最優(yōu)解op存放到x中。物品編號重量價值1542343234110/1背包問題（W=6）：11,12110,1109,918,808,817,706,515,4010,1118,807,715,408,815,406,815,704,513,403,412,301,110,005,713,402,310,003,410,000,05,410,00x1：選或不選物品1x2：選或不選物品2x3：選或不選物品3x4：選或不選物品4根結(jié)點：i=1i=2i=3i=4i=5最優(yōu)解(總重量tw,總價值tv)物品編號重量價值154234323411//問題表示intn=4; //4種物品intW=6; //限制重量為6intw[]={0,5,3,2,1}; //存放4個物品重量,不用下標0元素intv[]={0,4,4,3,1}; //存放4個物品價值,不用下標0元素//求解結(jié)果表示intx[MAXN]; //存放最終解intmaxv; //存放最優(yōu)解的總價值voiddfs(inti,inttw,inttv,intop[]){if(i>n) //找到一個葉子結(jié)點{if(tw==W&&tv>maxv) //找到一個滿足條件的更優(yōu)解,保存

{maxv=tv;for(intj=1;j<=n;j++)x[j]=op[j];}}else //尚未找完所有物品{op[i]=1; //選取第i個物品

dfs(i+1,tw+w[i],tv+v[i],op);op[i]=0; //不選取第i個物品,回溯

dfs(i+1,tw,tv,op);}}采用解空間為子集樹遞歸的算法框架

改進1：左剪枝：對于第i層的有些結(jié)點，tw+w[i]已超過了W（

W=6），顯然再選擇w[i]是不合適的。如第2層的（5，4）結(jié)點

進行擴展是不必要的。11,1210,1110,11109,98,88,8108,85,4101i=2tw>W僅僅擴展?jié)M足tw+w[i]<=W的左孩子結(jié)點

6,55,45,4105,45,410106,85,75,7104,53,43,4103,43,42,32,3101,10,00,0100,00,01010100,010x1：選或不選物品1x2：選或不選物品2x3：選或不選物品3x4：選或不選物品4根結(jié)點：i=1i=2i=3i=4i=5最優(yōu)解(總重量tw,總價值tv)物品編號重量價值154234323411voiddfs(inti,inttw,inttv,intop[]){if(i>n) //找到一個葉子結(jié)點{if(tw==W&&tv>maxv) //找到一個滿足條件的更優(yōu)解,保存{maxv=tv;maxw=tw;for(intj=1;j<=n;j++)x[j]=op[j];}}else //尚未找完所有物品{if(tw+w[i]<=W) //左孩子結(jié)點剪枝{op[i]=1; //選取第i個物品

dfs(i+1,tw+w[i],tv+v[i],op);}op[i]=0; //不選取第i個物品,回溯

dfs(i+1,tw,tv,op);}}左剪枝

改進2：右剪枝：rw=w[i]+w[i+1]+…+w[n]。

當不選擇物品i時：rw-w[i]=w[i+1]+…+w[n]，若tw+rw-w[i]<W，也就是說即使選擇后面的所有物品，重量也不會達到W，因此不必要再考慮擴展這樣的結(jié)點。

僅僅擴展?jié)M足tw+rw-w[i]≥W的右孩子結(jié)點物品編號重量價值154234323411W=60,0,11根結(jié)點：i=1rw=5+3+2+1=110,0,60不選物品1：w[1]=5rw=rw-w[1]=11-5=6tw+rw-w[1]=6≥W成立0

tw+rw-w[2]=3≥W不成立3,4,31…

6,5,05,4,1105,4,35,4,610106,8,05,7,1103,4,30,0,61100,0,1110x1：選或不選物品1x2：選或不選物品2x3：選或不選物品3x4：選或不選物品4根結(jié)點：i=1i=2i=3i=4i=5最優(yōu)解(tw,tv,rw)

0

物品編號重量價值154234323411

W=6voiddfs(inti,inttw,inttv,intrw,intop[]){//初始調(diào)用時rw為所有物品重量和intj;if(i>n) //找到一個葉子結(jié)點{if(tw==W&&tv>maxv) //找到一個滿足條件的更優(yōu)解,保存{maxv=tv;for(j=1;j<=n;j++) //復制最優(yōu)解x[j]=op[j];}}else //尚未找完所有物品{if(tw+w[i]<=W) //左孩子結(jié)點剪枝{op[i]=1; //選取第i個物品

dfs(i+1,tw+w[i],tv+v[i],rw-w[i],op);}if(tw+rw-w[i]>=W){op[i]=0; //不選取第i個物品,回溯

dfs(i+1,tw,tv,rw-w[i],op);}}}右剪枝

【算法分析】該算法不考慮剪枝時解空間樹中有2n+1-1個結(jié)點（剪枝的結(jié)點個數(shù)不確定），所以最壞情況下算法的時間復雜度為O(2n)。2.裝入背包中物品重量和不超過W前面左剪枝方式不變。但右剪枝方式不再有效，改為采用上界函數(shù)進行右剪枝。問題變?yōu)榍蟊嘲形锲分亓亢筒怀^W的最大價值的裝入方案：第i層結(jié)點：dfs(i，tw，tv，op)1dfs(i+1，tw，tv，op)第i+1層結(jié)點0：不選擇第i個物品上界函數(shù)bound(i)=tv+r表示沿著該方向選擇得到物品的價值上界r表示剩余物品的總價值第i層結(jié)點：dfs(i，tw，tv，op)10上界函數(shù)bound(i)=tv+r假設當前求出最大價值maxv，若bound(i)≤maxv，則右剪枝，否則繼續(xù)擴展。顯然r越小，bound(i)也越小，剪枝越多，為了構(gòu)造更小的r，將所有物品以單位重量價值遞減排列。intbound(inti,inttw,inttv) //求上界{i++; //從i+1開始while(i<=n&&tw+A[i].w<=W) //若序號為i的物品可以整個放入{tw+=A[i].w;tv+=A[i].v;i++;}if(i<=n)returntv+(W-tw)*A[i].p; //序號為i的物品不能整個放入elsereturntv;}第i層結(jié)點：dfs(i，tw，tv，op)第i+1層結(jié)點0：不選擇第i個物品葉子結(jié)點剪枝：左剪枝：僅僅擴展tw+w[i]≤W的左孩子結(jié)點右剪枝：僅僅擴展bound(i,tw,tv)>maxv的右孩子結(jié)點一旦找到一個解后，后面找到的其他解（tv，op）只能越來越優(yōu)voiddfs(inti,inttw,inttv,intop[])//求解0/1背包問題{if(i>n) //找到一個葉子結(jié)點{maxv=tv; //存放更優(yōu)解for(intj=1;j<=n;j++)x[j]=op[j];}else //尚未找完所有物品{if(tw+A[i].w<=W) //左孩子結(jié)點剪枝{op[i]=1; //選取序號為i的物品

dfs(i+1,tw+A[i].w,tv+A[i].v,op);}if(bound(i,tw,tv)>maxv) //右孩子結(jié)點剪枝{op[i]=0; //不選取序號為i的物品,回溯

dfs(i+1,tw,tv,op);}}}物品編號重量價值1542343234110/1背包問題（W=6）：inowivipi13231.522341.33411141540.8p=v/w0.81.31.51A數(shù)組:2,3最優(yōu)解0,0根結(jié)點：i=1(tw,tv)6,85,7inowivipi13231.522341.33411141540.8

6+w[4]>WW=6,maxv=06,8bound=8bound>maxv√maxv=8

bound=7bound>maxv×

bound=6bound>maxv×

bound=6bound>maxv×

【算法分析】該算法不考慮剪枝時解空間樹中有2n+1-1個結(jié)點（剪枝的結(jié)點個數(shù)不確定），所以最壞情況下算法的時間復雜度為O(2n)。5.3求解裝載問題5.3.1求解簡單裝載問題

【問題描述】有n個集裝箱要裝上一艘載重量為W的輪船，其中集裝箱i（1≤i≤n）的重量為wi。不考慮集裝箱的體積限制，現(xiàn)要從這些集裝箱中選出重量和小于等于W并且盡可能大的若干裝上輪船。

例如，n=5，W=10，w={5，2，6，4，3}時，其最佳裝載方案是（1，1，0，0，1）或者（0，0，1，1，0），maxw=10。

【問題求解】采用帶剪枝的回溯法求解。問題的表示如下：intw[]={0，5，2，6，4，3};//各集裝箱重量，不用下標0的元素intn=5，W=10;求解的結(jié)果表示如下：intmaxw=0; //存放最優(yōu)解的總重量intx[MAXN]; //存放最優(yōu)解向量將上述數(shù)據(jù)設計為全局變量。求解算法如下：

voiddfs(inti，inttw，intrw，intop[])其中參數(shù)i表示考慮的集裝箱i，tw表示選擇的集裝箱重量和，rw表示剩余集裝箱的重量和（初始時為全部集裝箱重量和），op表示一個解，即對應一個裝載方案。最優(yōu)解：x，maxw剪枝：左剪枝：僅僅擴展tw+w[i]≤W的左孩子結(jié)點右剪枝：僅僅擴展tw+rw-w[i]>maxw的右孩子結(jié)點0,205,157,13×i=1,w[1]=57,7×7,310,0×maxw=10×5,135,79,3×××0,152,138,7×8,3××0,136,710,3××××i=2,w[2]=2i=3,w[3]=6i=4,w[4]=4i=5,w[5]=3(tw,rw)n=5w:5，2，6，4，3W=10voiddfs(inti,inttw,intrw,intop[])//求解簡單裝載問題{if(i>n) //找到一個葉子結(jié)點{if(tw>maxw){maxw=tw; //找到一個滿足條件的更優(yōu)解,保存它for(intj=1;j<=n;j++) //復制最優(yōu)解x[j]=op[j];}}else //尚未找完所有集裝箱{if(tw+w[i]<=W) //左孩子結(jié)點剪枝{op[i]=1; //選取第i個集裝箱

dfs(i+1,tw+w[i],rw-w[i],op);}if(tw+rw-w[i]>maxw) //右孩子結(jié)點剪枝{op[i]=0; //不選取第i個集裝箱,回溯

dfs(i+1,tw,rw-w[i],op);}}}最優(yōu)方案

選取第1個集裝箱

選取第2個集裝箱

選取第5個集裝箱總重量=10intw[]={0，5，2，6，4，3};//各集裝箱重量，不用下標0的元素intn=5，W=10;5.3.2求解復雜裝載問題

【問題描述】有一批共n個集裝箱要裝上兩艘載重量分別為c1和c2的輪船，其中集裝箱i的重量為wi，且w1+w2+…+wn≤c1+c2。

裝載問題要求確定是否有一個合理的裝載方案可將這些集裝箱裝上這兩艘輪船。如果有，找出一種裝載方案。

例如：n=3，c1=c2=50，w={10，40，40}時，可以將集裝箱1和2裝到第一艘輪船上，而將集裝箱3裝到第二艘輪船上。n=3，c1=c2=50，w={20，40，40}，則無法將這3個集裝箱都裝上輪船。

【問題求解】如果一個給定的復雜裝載問題有解，則可以采用如下方式得到一個裝載方案：

首先將第一艘輪船盡可能裝滿，然后將剩余的集裝箱裝在第二艘輪船上。

可以用反證法證明其正確性。

如果這樣做得不到一個裝載方案，說明該復雜裝載問題沒有解?。?）將盡可能多的集裝箱裝到第一艘輪船上，得到解向量x。（2）累計第一艘輪船裝完后剩余的集裝箱重量sum。（3）若sum<=c2，表示第二艘輪船可以裝完，返回true；否則表示第二艘輪船不能裝完，返回false。算法思路（輸入為w1，w2，…，wn，c1，c2）：#include<stdio.h>#include<string.h>#defineMAXN20 //最多集裝箱個數(shù)//問題表示intw[]={0,10,40,40}; //各集裝箱重量,不用下標0的元素intn=3;intc1=50,c2=50;intmaxw=0; //存放第一艘輪船最優(yōu)解的總重量intx[MAXN]; //存放第一艘輪船最優(yōu)解向量voiddfs(inti,inttw,intrw,intop[]) //求第一艘輪船的最優(yōu)解{if(i>n) //找到一個葉子結(jié)點{if(tw>maxw){maxw=tw; //找到一個滿足條件的更優(yōu)解for(intj=1;j<=n;j++) //復制最優(yōu)解x[j]=op[j];}}else //尚未找完所有集裝箱{if(tw+w[i]<=c1) //左孩子結(jié)點剪枝{op[i]=1; //選取第i個集裝箱

dfs(i+1,tw+w[i],rw-w[i],op);}if(tw+rw-w[i]>maxw) //右孩子結(jié)點剪枝{op[i]=0; //不選取第i個集裝箱,回溯

dfs(i+1,tw,rw-w[i],op);}}}boolsolve()

//求解復雜裝載問題{intsum=0; //累計第一艘輪船裝完后剩余的集裝箱重量for(intj=1;j<=n;j++)if(x[j]==0)sum+=w[j];if(sum<=c2) //第二艘輪船可以裝完returntrue;else //第二艘輪船不能裝完returnfalse;}在第一艘輪船裝滿后考慮第2艘輪船是否能夠裝完剩余的集裝箱？voidmain(){intop[MAXN]; //存放臨時解memset(op,0,sizeof(op));intrw=0;for(inti=1;i<=n;i++)rw+=w[i];

dfs(1,0,rw,op); //求第一艘輪船的最優(yōu)解printf("求解結(jié)果\n");if(solve()) //輸出結(jié)果{printf("最優(yōu)方案\n");dispasolution(n);}elseprintf("沒有合適的裝載方案\n");}求解結(jié)果

最優(yōu)方案

將第1個集裝箱裝上第一艘輪船

將第2個集裝箱裝上第一艘輪船

將第3個集裝箱裝上第二艘輪船//問題表示intw[]={0,10,40,40}; //各集裝箱重量,不用下標0的元素intn=3;intc1=50,c2=50;5.4.1求子集和問題的解5.4求解子集和問題

【問題描述】給定n個不同的正整數(shù)集合w=（w1，w2，…，wn）和一個正整數(shù)W，要求找出w的子集s，使該子集中所有元素的和為W。

例如，當n=4時，w=（11，13，24，7），W=31，則滿足要求的子集為（11，13，7）和（24，7）。

【問題求解】該問題的解空間樹是一棵子集樹。

設解向量x=（x1，x2，…，xn），這里是求所有滿足目標條件的解，所以一旦搜索到葉子結(jié)點（即i>n），如果相應的子集和為W，則輸出x解向量。第i層結(jié)點：dfs(i，tw，rw，x)選擇第i個整數(shù)x[i]=1tw=tw+w[i]rw=rw-w[i]不選擇第i個整數(shù)x[i]=0tw不變rw=rw-w[i]第i+1層結(jié)點第n+1層結(jié)點：葉子結(jié)點

當搜索到第i（1≤i≤n）的某個結(jié)點時，用tw表示選取的整數(shù)和，rw表示余下的整數(shù)和，即rw=w[i]+…+w[n]（其中包含w[i]），采用的剪枝函數(shù)如下：左剪枝：通過檢查當前整數(shù)w[i]加入后子集和是否超過W，若是則剪枝，即僅僅擴展?jié)M足tw+w[i]≤W的左孩子結(jié)點。右剪枝：如果一個結(jié)點滿足tw+rw-w[i]<W，也就是說即便選擇剩余所有整數(shù)，也不可能找到一個解，即僅僅擴展?jié)M足tw+rw-w[i]≥W的右孩子結(jié)點。voiddfs(inti,inttw,intrw,intx[])//求解子集和{if(i>n) //找到一個葉子結(jié)點{if(tw==W) //找到一個滿足條件的解,輸出它

dispasolution(x);}else //尚未找完所有整數(shù){if(tw+w[i]<=W) //左孩子結(jié)點剪枝{x[i]=1; //選取第i個整數(shù)

dfs(i+1,tw+w[i],rw-w[i],x);}if(tw+rw-w[i]>=W) //右孩子結(jié)點剪枝{x[i]=0; //不選取第i個整數(shù),回溯

dfs(i+1,tw,rw-w[i],x);}}}intn=4,W=31;intw[]={0,11,13,24,7}; //存放所有整數(shù),不用下標0的元素第1個解:

選取的數(shù)為11137第2個解:

選取的數(shù)為24701111110,5511,4424,31×i=1,w[1]=1124,7××11,31×0,4413,31××0,3124,731,0××i=2,w[2]=13i=3,w[3]=24i=4,w[4]=731,000010000101tw,rwintn=4,W=31;intw[]={0,11,13,24,7};tw=13,w[3]=24,tw+w[3]=37>Wtw=0,rw=31,w[3]=24tw+rw-w[3]=7<W

【算法分析】算法的解空間樹中有2n+1-1個結(jié)點，最壞情況下算法的時間復雜度為O(2n)。5.4.2判斷子集和問題是否存在解

采用回溯法一般是針對問題存在解時求出相應的一個或多個解，或者最優(yōu)解。

如果要判斷問題是否存在解（一個或者多個），可以將求解函數(shù)改為bool類型，當找到任何一個解時返回true，否則返回false。需要注意的是當問題沒有解時需要搜索所有解空間。booldfs(inti,inttw,intrw) //求解子集和{if(i>n) //找到一個葉子結(jié)點{if(tw==W) //找到一個滿足條件的解returntrue;}else //尚未找完所有物品{if(tw+w[i]<=W) //左孩子結(jié)點剪枝returndfs(i+1,tw+w[i],rw-w[i]); //選取第i個整數(shù)if(tw+rw-w[i]>=W) //右孩子結(jié)點剪枝returndfs(i+1,tw,rw-w[i]); //不選取第i個整數(shù),回溯}returnfalse;}intn=4,W;intw[]={0,11,13,24,7}; //存放所有整數(shù),不用下標0的元素boolsolve() //判斷子集和問題是否存在解{intrw=0;for(intj=1;j<=n;j++) //求所有整數(shù)和rwrw+=w[j];returndfs(1,0,rw); //i從1開始}voidmain(){W=7;printf("W=%d時%s\n",W,(solve()?"存在解":"沒有解"));W=15;printf("W=%d時%s\n",W,(solve()?"存在解":"沒有解"));W=21;printf("W=%d時%s\n",W,(solve()?"存在解":"沒有解"));W=24;printf("W=%d時%s\n",W,(solve()?"存在解":"沒有解"));}W=7時存在解W=15時沒有解W=21時沒有解W=24時存在解intn=4,W;intw[]={0,11,13,24,7};//存放所有整數(shù),不用下標0的元素

另外一種方法是通過解個數(shù)來判斷，如設置全局變量count表示解個數(shù)，初始化為0，調(diào)用搜索解的回溯算法，當找到一個解時置count++。

最后判斷count>0算法成立，若為真，表示存在解，否則表示不存在解。intcount;

//全局變量，累計解個數(shù)voiddfs(inti,inttw,intrw) //求解子集和{if(i>n) //找到一個葉子結(jié)點{if(tw==W) //找到一個滿足條件的解,解個數(shù)增1count++;}else //尚未找完所有物品{if(tw+w[i]<=W) //左孩子結(jié)點剪枝

dfs(i+1,tw+w[i],rw-w[i]); //選取第i個整數(shù)if(tw+rw-w[i]>=W) //右孩子結(jié)點剪枝

dfs(i+1,tw,rw-w[i]); //不選取第i個整數(shù),回溯}}boolsolve()

//判斷子集和問題是否存在解{count=0;intrw=0;for(intj=1;j<=n;j++) //求所有整數(shù)和rwrw+=w[j];

dfs(1,0,rw);

//i從1開始if(count>0) //有解的情況returntrue;else //無解的情況returnfalse;}5.5求解n皇后問題

第2章采用遞歸技術(shù)求解，這里采用回溯法求解。實際上，2.3.2小節(jié)的遞歸算法對應的就是回溯法的遞歸框架，這里討論采用非遞歸框架求解皇后問題。非遞歸回溯算法對應的算法：voidQueens(intn) //求解n皇后問題{inti=1; //i表示當前行,也表示放置第i個皇后q[i]=0; //q[i]是當前列,每個新考慮的皇后初始位置置為0列while(i>=1) //尚未回溯到頭，循環(huán){q[i]++; //原位置后移動一列while(q[i]<=n&&!place(i))//試探一個位置(i,q[i])q[i]++;if(q[i]<=n) //為第i個皇后找到了一個合適位置(i,q[i]){if(i==n) //若放置了所有皇后,輸出一個解dispasolution(n);else //皇后沒有放置完{i++; //轉(zhuǎn)向下一行,即開始下一個新皇后的放置q[i]=0; //每個新考慮的皇后初始位置置為0列}}elsei--; //若第i個皇后找不到合適的位置,則回溯到上一個皇后}}boolplace(inti) //測試第i行的q[i]列上能否擺放皇后{intj=1;if(i==1)returntrue;while(j<i) //j=1～i-1是已放置了皇后的行{if((q[j]==q[i])||(abs(q[j]-q[i])==abs(j-i)))

//該皇后是否與以前皇后同列，位置(j,q[j])與(i,q[i])是否同對角線 returnfalse;j++;}returntrue;}

【算法分析】該算法中每個皇后都要試探n列，共n個皇后，其解空間是一棵子集樹，不同于前面一般的二叉樹子集樹，這里每個結(jié)點可能有n棵子樹。

對應的算法時間復雜度為O(nn)。5.6求解圖的m著色問題

【問題描述】給定無向連通圖G和m種不同的顏色。用這些顏色為圖G的各頂點著色，每個頂點著一種顏色。如果有一種著色法使G中每條邊的兩個頂點著不同顏色，則稱這個圖是m可著色的。圖的m著色問題是對于給定圖G和m種顏色，找出所有不同的著色法。

【輸入格式】第1行有3個正整數(shù)n、k和m，表示給定的圖G有n個頂點和k條邊，m種顏色。頂點編號為1，2，…，n。接下來的k行中，每行有兩個正整數(shù)u、v，表示圖G的一條邊（u，v）。

【輸出格式】程序運行結(jié)束時，將計算出的不同的著色方案數(shù)輸出。如果不能著色，程序輸出-1?！据斎霕永?841213142324253445【輸出樣例】48

【問題求解】對于圖G，采用鄰接矩陣a存儲，根據(jù)求解問題需要，這里a為一個二維數(shù)組（下標0不用），當頂點i與頂點j有邊時，置a[i][j]=1，其他情況置a[i][j]=0。

圖中的頂點編號為1～n，著色編號為1～m。對于圖G中的每一個頂點，可能的著色為1～m，所以對應的解空間是一棵m叉樹，高度為n，層次i從1開始。boolSame(inti) //判斷頂點i是否與相鄰頂點存在相同的著色{for(intj=1;j<=n;j++)if(a[i][j]==1&&x[i]==x[j])returnfalse;returntrue;}voiddfs(inti) //求解圖的m著色問題{if(i>n) //達到葉子結(jié)點count++; //著色方案數(shù)增1else{for(intj=1;j<=m;j++) //試探每一種著色{x[i]=j; //試探著色jif(Same(i)) //可以著色j，進入下一個頂點著色

dfs(i+1);x[i]=0; //回溯}}}1234n=4，k=4，m=3，其著色方案有12個。第1個著色方案：1223第2個著色方案：1232第3個著色方案：1323第4個著色方案：1332第5個著色方案：2113第6個著色方案：2131第7個著色方案：2313第8個著色方案：2331第9個著色方案：3112第10個著色方案：3121第11個著色方案：3212第12個著色方案：3221

【算法分析】該算法中每個頂點試探1～m種著色，共n個頂點，對應解空間樹是一棵m叉樹（子集樹），算法的時間復雜度為O(mn)。5.7求解任務分配問題

【問題描述】有n（n≥1）個任務需要分配給n個人執(zhí)行，每個任務只能分配給一個人，每個人只能執(zhí)行一個任務。

第i個人執(zhí)行第j個任務的成本是c[i][j]（1≤i，j≤n）。求出總成本最小的分配方案?！締栴}求解】這里采用回溯法求解。問題表示如下：人員任務1任務2任務3任務4192782643735818476944個人員、4個任務的信息intn=4;intc[MAXN][MAXN]={{0},{0,9,2,7,8},{0,6,4,3,7},{0,5,8,1,8},{0,7,6,9,4}};

//下標0的元素不用，c[i][j]表示第i個人執(zhí)行第j個任務的成本

考慮為第i個人員分配任務（i從1開始），由于每個任務只能分配給一個人員，為了避免重復分配，設計一個worker布爾數(shù)組，初始時均為false，當任務j分配后置worker[j]=true。求解結(jié)果表示如下：intx[MAXN]; //臨時解intcost=0; //臨時解的成本intbestx[MAXN]; //最優(yōu)解intmincost=INF; //最優(yōu)解的成本boolworker[MAXN]; //worker[j]表示任務j是否已經(jīng)分配人員voiddfs(inti) //為第i個人員分配任務{(diào)if(i>n) //到達葉子結(jié)點{if(cost<mincost) //比較求最優(yōu)解{mincost=cost;for(intj=1;j<=n;j++)bestx[j]=x[j];}}else{for(intj=1;j<=n;j++) //為人員i試探任務j:1到nif(!worker[j]) //若任務j還沒有分配{worker[j]=true;x[i]=j; //任務j分配給人員icost+=c[i][j];

dfs(i+1);

//為人員i+1分配任務worker[j]=false; //回退x[j]=0;cost-=c[i][j];}}}程序的執(zhí)行結(jié)果：最優(yōu)方案:

第1個人安排任務2

第2個人安排任務1

第3個人安排任務3

第4個人安排任務4總成本=13人員任務1任務2任務3任務419278264373581847694

【算法分析】該算法中每個人員試探1～n個任務，對應解空間樹是一棵n叉樹（子集樹），算法的時間復雜度為O(nn)。5.8求解活動安排問題

【問題描述】假設有一個需要使用某一資源的n個活動所組成的集合S，S={1，…，n}。該資源任何時刻只能被一個活動所占用，活動i有一個開始時間bi和結(jié)束時間ei（bi<ei），其執(zhí)行時間為ei-bi，假設最早活動執(zhí)行時間為0。

一旦某個活動開始執(zhí)行，中間不能被打斷，直到其執(zhí)行完畢。若活動i和活動j有bi≥ej或bj≥ei，則稱這兩個活動兼容。

設計算法求一種最優(yōu)活動安排方案，使得所有安排的活動個數(shù)最多?；顒泳幪杋1234開始時間bi1246結(jié)束時間ei35810【問題求解】調(diào)度方案（一種排列）:x[1]，x[2]，…，x[n]第1步選擇活動x[1]…第i步選擇活動x[i]…第n步選擇活動x[n]活動編號i1234開始時間bi1246結(jié)束時間ei358101234

兼容活動個數(shù)=22134

兼容活動個數(shù)=24123

兼容活動個數(shù)=1…求出最多的兼容活動個數(shù)采用回溯法求解，相當于找到S={1，…，n}的某個排列即調(diào)度方案，使得其中所有兼容活動個數(shù)最多，顯然對應的解空間是一個是排列樹。直接采用排列樹遞歸框架實現(xiàn)，對于每一種調(diào)度方案求出所有兼容活動個數(shù)，通過比較求出最多活動個數(shù)maxsum，對應的調(diào)度方案就是最優(yōu)調(diào)度方案bestx，即為本問題的解。

對于一種調(diào)度方案，如何計算所有兼容活動的個數(shù)呢？因為其中可能存在不兼容的活動。

例如，右表的4個活動，若調(diào)度方案為（1，2，3，4），求所有兼容活動個數(shù)的過程如下：活動編號1234開始時間1246結(jié)束時間35810置當前活動的結(jié)束時間laste=0，所有兼容活動個數(shù)sum=0?；顒?：其開始時間為1，大于等于laste，屬于兼容活動，選取它，sum增加1，sum=1，置laste=其結(jié)束時間=3?；顒?：其開始時間為2，小于laste，屬于非兼容活動，不選取它?；顒?：其開始時間為4，大于等于laste，屬于兼容活動，選取它，sum增加1，sum=2，置laste=其結(jié)束時間=8?；顒?：其開始時間為6，小于laste，屬于非兼容活動，不選取它。該調(diào)度方案的所有兼容活動個數(shù)sum為2。求解過程產(chǎn)生所有排列，每個排列x=(x[1],x[2],…,x[n])對應一種調(diào)度方案計算每種調(diào)度方案的兼容活動個數(shù)sum比較求出最大的兼容活動個數(shù)maxsum和最優(yōu)方案bestx問題表示structAction{intb; //活動起始時間inte; //活動結(jié)束時間};intn=4;ActionA[]={{0,0},{1,3},{2,5},{4,8},{6,10}};//下標0不用問題的求解結(jié)果表示：intx[MAX]; //臨時解向量intbestx[MAX]; //最優(yōu)解向量intlaste=0; //一個調(diào)度方案中最后兼容活動的結(jié)束時間,初值為0intsum=0; //一個調(diào)度方案中所有兼容活動個數(shù),初值為0intmaxsum=0; dfs(i)[sum,x,laste]第i層結(jié)點swap(x[i],x[j])修改sum和laste第i+1層結(jié)點dfs(i+1)[sum,x,laste]swap(x[i],x[j])恢復sum和laste…voiddfs(inti) //搜索活動問題最優(yōu)解{if(i>n) //到達葉子結(jié)點,產(chǎn)生一種調(diào)度方案{if(sum>maxsum){maxsum=sum;for(intk=1;k<=n;k++)bestx[k]=x[k];}}else{for(intj=i;j<=n;j++) //沒有到達葉子結(jié)點,考慮i到n的活動{ //第i層結(jié)點選擇活動x[j]

swap(x[i],x[j]);

//排序樹問題遞歸框架:交換x[i],x[j]intsum1=sum; //保存sum，laste以便回溯