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

,算法設(shè)計與分析,DeSignandAnalysisofAlgorithmsInC+,“十一五”國家級規(guī)劃教材,陳慧南編著,電子工業(yè)出版社,第2部分算法設(shè)計策略,第8章回溯法,8.1一般方法8.2n-皇后8.3子集和數(shù)8.4圖的著色8.5哈密頓環(huán)8.60/1背包8.7批處理作業(yè)調(diào)度,最優(yōu)化問題：滿足一定的約束條件解稱為可行解。使目標(biāo)函數(shù)最優(yōu)的（最大或最?。┛尚薪夥Q為最優(yōu)解。問題的解向量：表示成一個n元式(x0,x1,xn-1)的形式貪心算法：最優(yōu)子結(jié)構(gòu)特性和最優(yōu)量度標(biāo)準(zhǔn)動態(tài)規(guī)劃法：最優(yōu)子結(jié)構(gòu)特性和重疊子問題,8.1一般方法,回溯法的基本做法是搜索，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數(shù)相當(dāng)大的問題。,回溯法的基本思想,一般的搜索算法（暴力算法），對所有可能的解逐一的試驗(yàn)，看是否是問題的解。任何問題都可以用暴力搜索算法解決，因?yàn)樗闅v了全部可能解，但是顯然會很慢。,搜索過程，要保證每個可能情況都要試到，不漏不重，所以就有了各種各樣的搜索算法，比如深度優(yōu)先搜索，廣度優(yōu)先搜索。他們的區(qū)別只在于構(gòu)造可能解的方式不同，本質(zhì)是一樣的，都是試解，回溯算法是一種采用深度優(yōu)先方式來構(gòu)造可能解的搜索算法。,n=3時的0-1背包問題用完全二叉樹表示的解空間,M=30（w0,w1,w2）=(18,15,10)，（p0,p1,p2）=(25,24,15)。,搜索算法如果不做任何優(yōu)化那么執(zhí)行效率是一樣的。因?yàn)橐欢ㄒ阉魅靠赡芙狻５侨绻覀冊谒阉鬟^程（可能解的構(gòu)造）中已經(jīng)和問題不符合，我們就沒必要繼續(xù)構(gòu)造下去，這就是所謂搜索算法里面的剪枝，不同的搜索算法就是為了盡可能地舍棄那些不可能的解，來達(dá)到提高搜索算法效率的目的。,n=3時的0-1背包問題用完全二叉樹表示的解空間,M=30（w0,w1,w2）=(18,15,10)，（p0,p1,p2）=(25,24,15)。,回溯法在問題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點(diǎn)時，先判斷該結(jié)點(diǎn)是否包含問題的解。如果肯定不包含，則跳過對該結(jié)點(diǎn)為根的子樹的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。,n=3時的0-1背包問題用完全二叉樹表示的解空間,8.1.1基本概念,問題的解向量：回溯法希望一個問題的解能夠表示成一個n元式(x0,x1,xn-1)的形式。規(guī)定每個xi取值的約束條件稱為顯式約束。對給定的一個問題實(shí)例，顯式約束規(guī)定了所有可能的元組，它們組成問題的候選解集，被稱為該問題實(shí)例的解空間。隱式約束給出了判定一個候選解是否為可行解的條件。目標(biāo)函數(shù)也稱代價函數(shù)，用來衡量每個可行解的優(yōu)劣。使目標(biāo)函數(shù)取最大（或最小）值的可行解為問題的最優(yōu)解。,狀態(tài)空間樹（statespace）是描述問題解空間的樹形結(jié)構(gòu)。樹中每個結(jié)點(diǎn)稱為一個問題狀態(tài)（problemstate）。如果從根到樹中某個狀態(tài)的路徑代表一個作為候選解的元組，則稱該狀態(tài)為解狀態(tài)（solutionstate）。如果從根到某個解狀態(tài)的路徑代表一個作為可行解的元組，則稱該解狀態(tài)為答案狀態(tài)(answerstate)。,M=30（w0,w1,w2）=(18,15,10)，（p0,p1,p2）=(25,24,15)。,8.1.2剪枝函數(shù)和回溯法,為了提高搜索效率，在搜索過程中使用約束函數(shù)（constraintfunction），可以避免無謂地搜索那些已知不含答案狀態(tài)的子樹。如果是最優(yōu)化問題，還可使用限界函數(shù)（boundfunction）剪去那些不可能包含最優(yōu)答案結(jié)點(diǎn)的子樹。約束函數(shù)和限界函數(shù)的目的是相同的，都為了剪去不必要搜索的子樹，減少問題求解所需實(shí)際生成的狀態(tài)結(jié)點(diǎn)數(shù)，它們統(tǒng)稱為剪枝函數(shù)（pruningfunction）。,使用剪枝函數(shù)的深度優(yōu)先生成狀態(tài)空間樹中結(jié)點(diǎn)的求解方法稱為回溯法（backtracking）；廣度優(yōu)先生成結(jié)點(diǎn)，并使用剪枝函數(shù)的方法稱為分枝限界法（branch-and-bound）。,剪枝函數(shù)：約束函數(shù)在擴(kuò)展結(jié)點(diǎn)處剪去不滿足約束的子樹；限界函數(shù)剪去得不到最優(yōu)解的子樹。,對n個元素（a0,a1,an-1)排序，本質(zhì)是求元素下標(biāo)（0，1,n-1)的一種排列X(x0,x1,xn-1)，使得axiaxi+1例如：n=3,（a0,a1,a2)=(13,24,9),設(shè)(x0,x1,xk-1)是從根到某個問題狀態(tài)Y的一條路徑，令T(x0,x1,xk-1)是xk可取值的集合，對于xk的每個取值(x0,x1,xk-1，xk)，是一條從根到Y(jié)再到Y(jié)的某個孩子Z的路徑。如果約束函數(shù)Bk(x0,x1,xk)為真，則繼續(xù)檢測以Z為根的子樹，否則將不再考慮以Z為根的子樹。如果(x0,x1,xk-1)到達(dá)葉子結(jié)點(diǎn)，T(x0,x1,xk-1)應(yīng)為空集。,【程序81】遞歸回溯法VoidRBacktrack(intk)/應(yīng)以RBacktrack(0)調(diào)用本函數(shù)for(每個xk,使得xkT(x0,xk-1)/深度優(yōu)先進(jìn)入下一層,n=3,（a0,a1,a2)=(13,24,9),【程序8-2】迭代回溯法VoidIBacktrack(intn)intk=0;while(k>=0)if(還剩下尚未檢測的xk，使得xkT(x0,xk-1)/回溯到上一層,8.1.3回溯法的效率分析,回溯算法的最壞情況時間復(fù)雜度可達(dá)O(p(n)n!)（或O(p(n)2n)或O(p(n)nn)），這里p(n)是n的多項(xiàng)式，是生成一個結(jié)點(diǎn)所需的時間。,蒙特卡羅方法（MonteCarlo）。這種估計方法的基本思想是在狀態(tài)空間樹中隨機(jī)選擇一條路徑(x0,x1,xn1)。設(shè)X是這條隨機(jī)路徑上，代表部分向量(x0,x1,xk1)的結(jié)點(diǎn)，如果在X處不受限制的孩子數(shù)目是mk，則認(rèn)為與X同層的其他結(jié)點(diǎn)不受限制的孩子數(shù)目也都是mk。整個狀態(tài)空間樹上將實(shí)際生成的結(jié)點(diǎn)數(shù)估計為m=1+m0+m0m1+m0m1m2+,【程序8-3】蒙特卡羅算法intEstimate(SType*x)intk=0,m=1,r=1;doSetTypeS=xk|xkT(x1,xk1),8.2n-皇后,8.2.1問題描述,n-皇后問題要求在一個nn的棋盤上放置n個皇后，使得它們彼此不受“攻擊”。n-皇后問題要求尋找在棋盤上放置這n個皇后的方案，使得它們中任何兩個都不在同一行、同一列或同一斜線上。,8.2.2回溯法求解,皇后問題可用n-元組（x0,x1,xn1）表示n-皇后問題的解，其中xi表示第i行的皇后所處的列號(0xin)。顯式約束的一種觀點(diǎn)是：xi0,1,n1，0in。此時的解空間大小為nn。相應(yīng)的隱式約束為：對任意0i,jn，當(dāng)ij時，xixj且|i-j|xi-xj|。另一種顯式約束的觀點(diǎn)是：xi0,1,n1，0in，且xixj(0i,jn,ij)。與此相對應(yīng)的解空間大小為n!。相應(yīng)的隱式約束為：對任意0i,jn，當(dāng)ij時，|i-j|xi-xj|。,皇后問題的狀態(tài)空間樹是一棵排列樹。排列樹有n!個葉結(jié)點(diǎn)，遍歷排列樹的時間為(n!).,8.2.3n-皇后算法,【程序8-4】n-皇后問題的回溯算法boolPlace(intk,inti,int*x)/假定第k+1個皇后放在第i列上(xk=i)，判定第k+1個皇后是否與之前的k個皇后在同一列或在同一斜線上for(intj=0;j<k;j+)if(xj=i)|(abs(xj-i)=abs(j-k)returnfalse;returntrue;,voidNQueens(intk,intn,int*x)for(inti=0;i<n;i+)/顯式約束的第一種觀點(diǎn)，xk=0,1,n-1if(Place(k,i,x)/約束函數(shù)xk=i;if(k=n-1)for(i=0;i<n;i+)cout<<xi<<""/輸出一個可行解cout<<endl;elseNQueens(k+1,n,x);/深度優(yōu)先進(jìn)入下一層voidNQueens(intn,int*x)NQueens(0,n,x);,8.2.4時間分析,可通過計算得到這5次試驗(yàn)中實(shí)際需要生成的結(jié)點(diǎn)數(shù)的平均值為1625。8-皇后問題狀態(tài)空間樹的結(jié)點(diǎn)總數(shù)是：因此，需要實(shí)際生成的結(jié)點(diǎn)數(shù)目大約占總結(jié)點(diǎn)數(shù)的1.55%。,8.3子集和數(shù),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.2回溯法求解,解結(jié)構(gòu)形式：可變長度元組和固定長度元組?？勺冮L度元組（x0,xk1,xk），0k<n。元組的每個分量的取值可以是元素值，也可以是選入子集的正數(shù)的下標(biāo)。例如：（11，13，7）或者（0，1，2）固定長度n-元組（x0,x1,xn1），xi0,1,0i<n。xi=0，表示wi未選入子集，xi=1，表示wi入選子集。例如：（x0,x1,x2,x3）=（1,1,0,1),W=w0,w1,w2,w3=(11,13,24,7)，M=31,W=w0,w1,w2,w3=(11,13,24,7)，M=31可變長度元組的解空間樹,W=w0,w1,w2,w3=(11,13,24,7)，M=31固定長度n-元組（x0,x1,xn1），xi0,1,0i<n。xi=0，表示wi未選入子集，xi=1，表示wi入選子集。例如：（x0,x1,x2,x3）=（1,1,0,1),稱這種從n個元素的集合中找出滿足某些性質(zhì)的子集的狀態(tài)空間樹為子集樹。子集樹有2n個解狀態(tài)，遍歷子集樹的時間為(2n)。,固定長度n-元組（x0,x1,xn1），表示的子集和數(shù)問題的約束函數(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+)cout<<xj<</輸出一個解cout<<endl;,elseif(s+wk+wk+1=m),W=w0,w1,w2,w3=(11,13,24,7)，M=31,例83設(shè)有n=6個正數(shù)的集合W=(5,10,12,13,15,18)和整數(shù)M=30，求W的所有元素之和為M的子集。,8.4圖的著色,8.4.1問題描述,已知無向圖G=(V,E)和m種不同的顏色，如果只允許使用這m種顏色對圖G的結(jié)點(diǎn)著色，每個結(jié)點(diǎn)著一種顏色。問是否存在一種著色方案，使得圖中任意相鄰的兩個結(jié)點(diǎn)都有不同的顏色。這就是m-著色判定問題（m-colorabilitydecisionproblem）,8.4.2回溯法求解,設(shè)無向圖G=(V,E)采用如下定義的鄰接矩陣a表示：解的形式：n-元組(x0,x1,xn1),xi1，m,0i<n，表示結(jié)點(diǎn)i的顏色，這就是顯式約束。xi=0表示沒有可用的顏色。因此解空間的大小為mn。隱式約束可描述為：如果邊(i,j)E，則xixj。,約束函數(shù)：對所有i和j，0i,j<k，ij，若aij=1，則xixj。,8.4.3圖著色算法,【程序86】圖的m著色算法voidMGraph:NextValue(intk,intm,int*x)/本函數(shù)在1,m中為xk確定一個值最小的，且不與其鄰接點(diǎn)沖突的顏色xk=0/表示沒有可用顏色，顏色從1開始編號doxk=(xk+1)%(m+1);/嘗試下一種顏色if(!xk)return;/沒有可用顏色for(intj=0;j<k;j+)if(akj,voidMGraph:mColoring(intk,intm,int*x)doNextValue(k,m,x);/為xk分配顏色if(!xk)break;/xk=0表示當(dāng)前沒有適當(dāng)?shù)念伾玦f(k=n-1)/得到圖G的一種m-著色方案for(inti=0;i:mColoring(intm,int*x)mColoring(0,m,x);,8.4.4時間分析,算法的計算時間上界可由狀態(tài)空間樹的結(jié)點(diǎn)數(shù)確定。每個結(jié)點(diǎn)的處理時間即NextValue的執(zhí)行時間，為O(mn)。因此總時間為,8.5哈密頓環(huán),8.5.1問題描述,已知圖G=(V,E)是一個n個結(jié)點(diǎn)的連通圖。連通圖G的一個哈密頓環(huán)(Hamiltonlancycle)是圖G的一個回路，它經(jīng)過圖中每個結(jié)點(diǎn)，且只經(jīng)過一次。一個哈密頓環(huán)是從某個結(jié)點(diǎn)v0V開始，沿著圖G的n條邊環(huán)行的一條路徑（v0,v1,vn1,vn），其中，(vi,vi+1)E,0i<n，它訪問圖中每個結(jié)點(diǎn)且只訪問一次，最后返回開始結(jié)點(diǎn)，即除v0=vn，路徑上其余結(jié)點(diǎn)各不相同。,8.5.2哈密頓環(huán)算法,對于n個結(jié)點(diǎn)的圖G=(V,E)的哈密頓環(huán)問題，可采用n-元組表示問題的解(x0,x1,xn1)。每個xi0,1,n-1,0i<n，代表路徑上一個結(jié)點(diǎn)的編號，這就是顯式約束。因此解空間的大小為nn。其隱式約束可描述為：xixj,0i,j<n，ij，且（xi,xi+1）E，xi,xi+1V，i=0,1,n2，又（xn1，x0）E。哈密頓環(huán)問題的分析和求解方法與圖的m-著色問題非常相似,【程序87】哈密頓環(huán)算法voidMGraph:NextValue(intk,int*x)xk=0;doxk=(xk+1)%n;/下一個結(jié)點(diǎn)編號if(!xk)return;if(axk-1xk)/(xk-1,xk)是否是圖中一條邊?for(intj=0;j<k;j+)/檢查與前k個結(jié)點(diǎn)是否相同if(xj=xk)break;/結(jié)點(diǎn)xk與前k個結(jié)點(diǎn)有重復(fù)if(j=k)/xk是當(dāng)前可取的結(jié)點(diǎn)編號if(k<n-1)|(k=n-1),voidExtMGraph:Hamiltonian(intk,int*x)doNextValue(k,x);/產(chǎn)生xk的下一個值if(!xk)return;/xk=0表示xk已沒有可取值if(k=n-1)/輸出一個哈密頓環(huán)for(inti=0;i<n;i+)cout<<xi<<cout<<"0n"elseHamiltonian(k+1,x);/深度優(yōu)先進(jìn)入下一層while(1);voidExtMGraph:Hamiltonian(int*x)Hamiltonian(1,x);/x0=0為約定的起始結(jié)點(diǎn),8.7批處理作業(yè)調(diào)度,8.7.1問題描述,設(shè)有n個作業(yè)的集合0,1,n-1，每個作業(yè)有兩項(xiàng)任務(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的平均完成時間。,批處理作業(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回溯法求解,對于雙機(jī)批處理作業(yè)調(diào)度問題，其可行解是n個作業(yè)所有可能的排列，每一種排列代表一種作業(yè)調(diào)度方案S，其目標(biāo)函數(shù)是使FT(S)具有最小值的調(diào)度方案或作業(yè)排列是問題的最優(yōu)解。對于雙機(jī)作業(yè)調(diào)度，存在一個最優(yōu)非搶先調(diào)度方案，使得在P1和P2上的作業(yè)完全以相同次序處理。批處理作業(yè)調(diào)度問題的狀態(tài)空間樹解空間的大小為n！。,求解這一問題沒有有效的約束函數(shù)，但可以使用最優(yōu)解的上界值U進(jìn)行剪枝。如果對于已經(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;i<n;i+)ai=aai;bi=bbi;yi=i;,intJobSch(int*x);private:voidJobSch(inti,int*x);int*a,*b,n,U,f,f1,*f2,*y;,voidBatchJob:JobSch(inti,int*x)if(i=n)for(intj=0;j<n;j+)xj=yj;U=f;else,for(intj=i;jf1)?f2i1:f1)+byj;f+=f2i;if(f<U)Swap(y,i,j);JobSch(i+1,x);Swap(y,i,j);f1-=ayj;f-=f2i;,intBatchJob:JobSch(int*x)JobSch(0,x);returnU;,