《算法設(shè)計與分析》第章

,.,8.1一般方法8.2n-皇后8.3子集和數(shù)8.4圖的著色8.5哈密頓環(huán)8.60/1背包8.7批處理作業(yè)調(diào)度,第8章回溯法,.,8.1.1基本概念,規(guī)定每個xi取值的約束條件稱為顯式約束（explicitconstraint）。對給定的一個問題實例，顯式約束規(guī)定了所有可能的元組，它們組成問題的候選解集，被稱為該問題實例的解空間（solutionspace）。隱式約束（implicitconstraint）給出了判定一個候選解是否為可行解的條件。,8.1一般方法,.,目標(biāo)函數(shù)，也稱代價函數(shù)（costfunction），用來衡量每個可行解的優(yōu)劣。使目標(biāo)函數(shù)取最大（或最?。┲档目尚薪鉃閱栴}的最優(yōu)解。狀態(tài)空間樹（statespace）是描述問題解空間的樹形結(jié)構(gòu)。樹中每個結(jié)點稱為一個問題狀態(tài)（problemstate）。如果從根到樹中某個狀態(tài)的路徑代表一個作為候選解的元組，則稱該狀態(tài)為解狀態(tài)（solutionstate）。如果從根到某個解狀態(tài)的路徑代表一個作為可行解的元組，則稱該解狀態(tài)為答案狀態(tài)(answerstate)。,.,8.1.2剪枝函數(shù)和回溯法,為了提高搜索效率，在搜索過程中使用約束函數(shù)（constraintfunction），可以避免無謂地搜索那些已知不含答案狀態(tài)的子樹。如果是最優(yōu)化問題，還可使用限界函數(shù)（boundfunction）剪去那些不可能包含最優(yōu)答案結(jié)點的子樹。約束函數(shù)和限界函數(shù)的目的是相同的，都為了剪去不必要搜索的子樹，減少問題求解所需實際生成的狀態(tài)結(jié)點數(shù)，它們統(tǒng)稱為剪枝函數(shù)（pruningfunction）。,.,使用剪枝函數(shù)的深度優(yōu)先生成狀態(tài)空間樹中結(jié)點的求解方法稱為回溯法（backtracking）；廣度優(yōu)先生成結(jié)點，并使用剪枝函數(shù)的方法稱為分枝限界法（branch-and-bound）。,.,【程序81】遞歸回溯法VoidRBacktrack(intk)/應(yīng)以Rbacktrack(0)調(diào)用本函數(shù)for(每個xk,使得xkT(x0,xk-1),.,【程序8-2】迭代回溯法VoidIBacktrack(intn)intk=0;while(k=0)if(還剩下尚未檢測的xk，使得xkT(x0,xk-1),.,8.1.3回溯法的效率分析,回溯算法的最壞情況時間復(fù)雜度可達O(p(n)n!)（或O(p(n)2n)或O(p(n)nn)），這里p(n)是n的多項式，是生成一個結(jié)點所需的時間。,.,蒙特卡羅方法（MonteCarlo）。這種估計方法的基本思想是在狀態(tài)空間樹中隨機選擇一條路徑(x0,x1,xn1)。設(shè)X是這條隨機路徑上，代表部分向量(x0,x1,xk1)的結(jié)點，如果在X處不受限制的孩子數(shù)目是mk，則認(rèn)為與X同層的其他結(jié)點不受限制的孩子數(shù)目也都是mk。整個狀態(tài)空間樹上將實際生成的結(jié)點數(shù)估計為m=1+m0+m0m1+m0m1m2+,.,【程序8-3】蒙特卡羅算法intEstimate(SType*x)intk=0,m=1,r=1;doSetTypeS=xk|xkT(x1,xk1),.,8.2.1問題描述,n-皇后問題要求在一個nn的棋盤上放置n個皇后，使得它們彼此不受“攻擊”。n-皇后問題要求尋找在棋盤上放置這n個皇后的方案，使得它們中任何兩個都不在同一行、同一列或同一斜線上。,8.2n-皇后,.,8.2.2回溯法求解,皇后問題可用n-元組（x0,x1,xn1）表示n-皇后問題的解，其中xi表示第i行的皇后所處的列號(0xin)。顯式約束的一種觀點是：Si=0,1,n1，0in。相應(yīng)的隱式約束為：對任意0i,jn，當(dāng)ij時，xixj且。此時的解空間大小為nn。另一種顯式約束的觀點是：Si=0,1,n1，0in，且xixj(0i,jn,ij)。相應(yīng)的隱式約束為：對任意0i,jn，當(dāng)ij時，。與此相對應(yīng)的解空間大小為n!。,.,皇后問題的狀態(tài)空間樹是一棵排列樹。排列樹有n!個葉結(jié)點，遍歷排列樹的時間為(n!)。,.,.,8.2.3n-皇后算法,【程序8-4】n-皇后問題的回溯算法boolPlace(intk,inti,int*x)/判定兩個皇后是否在同一列或在同一斜線上for(intj=0;jk;j+)if(xj=i)|(abs(xj-i)=abs(j-k)returnfalse;returntrue;voidNQueens(intn,int*x)NQueens(0,n,x);,.,voidNQueens(intk,intn,int*x)for(inti=0;in;i+)if(Place(k,i,x)xk=i;if(k=n-1)for(i=0;in;i+)coutxi;coutendl;elseNQueens(k+1,n,x);,.,.,.,.,8.2.4時間分析,可通過計算得到這5次試驗中實際需要生成的結(jié)點數(shù)的平均值為1625。8-皇后問題狀態(tài)空間樹的結(jié)點總數(shù)是：因此，需要實際生成的結(jié)點數(shù)目大約占總結(jié)點數(shù)的1.55%。,.,.,8.3.1問題描述,已知n個不同正數(shù)wi，0in-1，的集合，求該集合的所有滿足條件的子集，使得每個子集中的正數(shù)之和等于另一個給定的正數(shù)M。例82設(shè)有n=4個正數(shù)的集合W=w0,w1,w2,w3=(11,13,24,7)和整數(shù)M=31，求W的所有滿足條件的子集，使得子集中的正數(shù)之和等于M。,8.3子集和數(shù),.,8.3.2回溯法求解,解結(jié)構(gòu)形式：可變長度元組和固定長度元組?？勺冮L度元組（x0,xk1,xk），0kn。元組的每個分量的取值可以是元素值，也可以是選入子集的正數(shù)的下標(biāo)。固定長度n-元組（x0,x1,xn1），xi0,1,0in。xi=0，表示wi未選入子集，xi=1，表示wi入選子集。,.,.,.,稱這種從n個元素的集合中找出滿足某些性質(zhì)的子集的狀態(tài)空間樹為子集樹。子集樹有2n個解狀態(tài)，遍歷子集樹的時間為(2n)。,.,約束函數(shù)：Bk(x0,x1,xk)為true，當(dāng)且僅當(dāng),.,8.3.3子集和數(shù)算法,【程序85】子集和數(shù)的回溯算法voidSumOfSub(floats,intk,floatr,int*x,floatm,float*w)xk=1;if(s+wk=m)for(intj=0;j=k;j+)coutxj;coutendl;,.,elseif(s+wk+wk+1=m),.,例83設(shè)有n=6個正數(shù)的集合W=(5,10,12,13,15,18)和整數(shù)M=30，求W的所有元素之和為M的子集。,.,8.4.1問題描述,已知無向圖G=(V,E)和m種不同的顏色，如果只允許使用這m種顏色對圖G的結(jié)點著色，每個結(jié)點著一種顏色。問是否存在一種著色方案，使得圖中任意相鄰的兩個結(jié)點都有不同的顏色。這就是m-著色判定問題（m-colorabilitydecisionproblem）,8.4圖的著色,.,.,8.4.2回溯法求解,設(shè)無向圖G=(V,E)采用如下定義的鄰接矩陣a表示：解的形式：n-元組(x0,x1,xn1),xi1，m,0in，表示結(jié)點i的顏色，這就是顯式約束。xi=0表示沒有可用的顏色。因此解空間的大小為mn。隱式約束可描述為：如果邊(i,j)E，則xixj。,.,約束函數(shù)：對所有i和j，0i,jk，ij，若aij=1，則xixj。,.,8.4.3圖著色算法,【程序86】圖的m著色算法templatevoidMGraph:NextValue(intk,intm,int*x)doxk=(xk+1)%(m+1);if(!xk)return;for(intj=0;jk;j+)if(akj,.,templatevoidMGraph:mColoring(intk,intm,int*x)doNextValue(k,m,x);if(!xk)break;if(k=n-1)for(inti=0;in;i+)coutxi;coutendl;elsemColoring(k+1,m,x);while(1);,.,templatevoidMGraph:mColoring(intm,int*x)mColoring(0,m,x);,.,8.4.4時間分析,算法的計算時間上界可由狀態(tài)空間樹的結(jié)點數(shù)確定。每個結(jié)點的處理時間即NextValue的執(zhí)行時間，為O(mn)。因此總時間為,.,8.5.1問題描述,已知圖G=(V,E)是一個n個結(jié)點的連通圖。連通圖G的一個哈密頓環(huán)(Hamiltonlancycle)是圖G的一個回路，它經(jīng)過圖中每個結(jié)點，且只經(jīng)過一次。一個哈密頓環(huán)是從某個結(jié)點v0V開始，沿著圖G的n條邊環(huán)行的一條路徑（v0,v1,vn1,vn），其中，(vi,vi+1)E,0in，它訪問圖中每個結(jié)點且只訪問一次，最后返回開始結(jié)點，即除v0=vn，路徑上其余結(jié)點各不相同。,8.5哈密頓環(huán),.,.,8.5.2哈密頓環(huán)算法,對于n個結(jié)點的圖G=(V,E)的哈密頓環(huán)問題，可采用n-元組表示問題的解(x0,x1,xn1)。每個xi0,1,n-1,0in，代表路徑上一個結(jié)點的編號，這就是顯式約束。因此解空間的大小為nn。其隱式約束可描述為：xixj,0i,jn，ij，且（xi,xi+1）E，xi,xi+1V，i=0,1,n2，又（xn1，x0）E。哈密頓環(huán)問題的分析和求解方法與圖的m-著色問題非常相似,.,【程序87】哈密頓環(huán)算法templatevoidMGraph:NextValue(intk,int*x)doxk=(xk+1)%n;if(!xk)return;if(axk-1xk)for(intj=0;jk;j+)if(xj=xk)break;if(j=k)if(kn-1)|(k=n-1),.,templatevoidExtMGraph:Hamiltonian(intk,int*x)doNextValue(k,x);if(!xk)return;if(k=n-1)for(inti=0;in;i+)coutxi;cout0n;elseHamiltonian(k+1,x);while(1);,.,templatevoidExtMGraph:Hamiltonian(int*x)Hamiltonian(1,x);,.,8.7.1問題描述,設(shè)有n個作業(yè)的集合0,1,n-1，每個作業(yè)有兩項任務(wù)要求分別在2臺設(shè)備P1和P2上完成。每個作業(yè)必須先在P1上加工，然后在P2上加工。P1和P2加工作業(yè)i所需的時間分別為ai和bi。作業(yè)i的完成時間fi(S)是指在調(diào)度方案S下，該作業(yè)的所有任務(wù)得以完成的時間，則是采用調(diào)度方案S的平均完成時間。,8.7批處理作業(yè)調(diào)度,.,批處理作業(yè)調(diào)度(batchjobschedule)問題要求確定這n個作業(yè)的最優(yōu)作業(yè)調(diào)度方案使其MFT最小。這等價于求使得所有作業(yè)的完成時間之和最小的調(diào)度方案。,.,例85設(shè)有三個作業(yè)和兩臺設(shè)備，作業(yè)任務(wù)的處理時間為（a0,a1,a2）=(2,3,2)和（b0,b1,b2）=(1,1,3)。這三個作業(yè)有6種可能的調(diào)度方案：(0,1,2),(0,2,1),(1,0,2),(1,2,0),(2,0,1),(2,1,0),它們相應(yīng)的完成時間之和分別是19,18,20,21,19,19。其中，最佳調(diào)度方案S=(0,2,1)。在這一調(diào)度方案下，f0(S)=3，f1(S)=7，f2(S)=8，F(xiàn)T=3+7+8=18。,.,8.7.2回溯法求解,對于雙機批處理作業(yè)調(diào)度問題，其可行解是n個作業(yè)所有可能的排列，每一種排列代表一種作業(yè)調(diào)度方案S，其目標(biāo)函數(shù)是使FT(S)具有最小值的調(diào)度方案或作業(yè)排列是問題的最優(yōu)解。對于雙機作業(yè)調(diào)度，存在一個最優(yōu)非搶先調(diào)度方案，使得在P1和P2上的作業(yè)完全以相同次序處理。批處理作業(yè)調(diào)度問題的狀態(tài)空間樹解空間的大小為n！。,.,求解這一問題沒有有效的約束函數(shù)，但可以使用最優(yōu)解的上界值U進行剪枝。如果對于已經(jīng)調(diào)度的作業(yè)子集的某種排列，所需的完成時間和已經(jīng)大于迄今為止所記錄下的關(guān)于最優(yōu)調(diào)度方案的完成時間和的上界值U,則該分枝可以剪去。,.,8.7.3批處理作業(yè)調(diào)度算法,【程序89】批處理作業(yè)調(diào)度算法classBatchJobpublic:BatchJob(intsz,int*aa,int*bb,intup)n=sz;U=up;f=f1=0;a=newintn;b=newintn;f2=newintn;y=newintn;for(inti=0;in;i+)ai=aai;bi=bbi;yi=i;,.,intJobSch(int*x);priva