算法設(shè)計(jì)與分析教學(xué)課件

1、 第2部分 算法設(shè)計(jì)策略第8章 回溯法 8.1 一般方法 8.2 n-皇后 8.3 子集和數(shù) 8.4 圖的著色 8.5 哈密頓環(huán) 8.6 0/1背包 8.7 批處理作業(yè)調(diào)度8.1 一般方法 問(wèn)題的所有可能的解可以用樹(shù)形結(jié)構(gòu)來(lái)表示，通過(guò)在樹(shù)中遍歷搜索找到可行解或最優(yōu)解 8.1.1 基本概念 問(wèn)題解可以用向量形式表示：(x0,x2,xn-1) 問(wèn)題中規(guī)定了每個(gè)xi取值的約束條件稱為顯式約束（explicit constraint）。 對(duì)給定的一個(gè)問(wèn)題實(shí)例，顯式約束規(guī)定了所有可能的元組(候選解)，它們組成問(wèn)題的候選解集，被稱為該問(wèn)題實(shí)例的解空間（solution space）。判定一個(gè)候選解是否為可

2、行解的條件為問(wèn)題的隱式約束（implicit constraint）。 目標(biāo)函數(shù)，也稱代價(jià)函數(shù)（cost function），用來(lái)衡量每個(gè)可行解的優(yōu)劣。使目標(biāo)函數(shù)取最大（或最?。┲档目尚薪鉃閱?wèn)題的最優(yōu)解。狀態(tài)空間樹(shù)（state space）是描述問(wèn)題解空間的樹(shù)形結(jié)構(gòu)。樹(shù)中每個(gè)結(jié)點(diǎn)稱為一個(gè)問(wèn)題狀態(tài)（problem state）。如果從根到樹(shù)中某個(gè)狀態(tài)的路徑代表了一個(gè)作為候選解的元組，則稱該狀態(tài)為解狀態(tài)（solution state）。若這個(gè)候選解可行，則稱該解狀態(tài)為答案狀態(tài)(answer state)。 例 0/1背包問(wèn)題M，n；wi, pi(x0,x1,x2,x3)顯示約束：xi0，1隱式約束

3、： xiwiM目標(biāo)函數(shù)： xipi當(dāng)n=3時(shí)對(duì)應(yīng)的狀態(tài)空間樹(shù) 樹(shù)中總結(jié)點(diǎn)數(shù)2n+1-1樹(shù)中葉子結(jié)點(diǎn)數(shù)2n01010101010101第1層第2層第3層第4層 例 排序問(wèn)題元素a0,a1,an-1排序問(wèn)題解向量（x0,x1,xn-1), xi表示元素ai在排列中的位置顯示約束：xi0,1,n-1且xixj (ij)隱式約束： aiaj (xixj)無(wú)目標(biāo)函數(shù)(13,24,09) 樹(shù)中總結(jié)點(diǎn)數(shù)：1+n+n(n-1)+n(n-1)(n-2)+n!樹(shù)中葉子結(jié)點(diǎn)數(shù)n!ai012n-1 8.1.2剪枝函數(shù)和回溯法 為了提高搜索效率，在搜索過(guò)程中使用約束函數(shù)（constraint function），可以避

4、免搜索那些已知不含答案狀態(tài)的子樹(shù)。如果是最優(yōu)化問(wèn)題，還可使用限界函數(shù)（bound function）剪去那些不可能包含最優(yōu)答案結(jié)點(diǎn)的子樹(shù)。約束函數(shù)和限界函數(shù)的目的都是為了剪去不必要搜索的子樹(shù)，減少問(wèn)題求解過(guò)程中實(shí)際生成的狀態(tài)結(jié)點(diǎn)數(shù)，它們統(tǒng)稱為剪枝函數(shù)（pruning function）。 使用剪枝函數(shù)的深度優(yōu)先生成狀態(tài)空間樹(shù)中結(jié)點(diǎn)的求解方法稱為回溯法（backtracking）；廣度優(yōu)先生成結(jié)點(diǎn)，并使用剪枝函數(shù)的方法稱為分枝限界法（branch-and-bound）。 【程序81】遞歸回溯法Void RBacktrack(int k) /應(yīng)以Rbacktrack(0)調(diào)用本函數(shù) for (每個(gè)

5、xk,使得 xkT(x0,xk-1) &(Bk(x0,xk) if ( (x0,x1,xk)是一個(gè)可行解) 輸出 (x0,x1,xk); RBacktrack(k+1); T(x0,xk-1) 代表xk所有可能取值約束函數(shù) Bk(x0,xk)部分向量(x0,xk-1) 代表從根到一個(gè)中間狀態(tài)Y的路徑 【程序8-2】 迭代回溯法Void IBacktrack(int n) int k=0; while (k=0) if (還剩下尚未檢測(cè)的xk，使得xk T(x0,xk-1) & Bk(x0,xk) if ( (x0,x1,xk)是一個(gè)可行解) 輸出(x0,x1,xk); k+; else k-;

6、 8.1.3回溯法的效率分析 狀態(tài)空間樹(shù)種總結(jié)點(diǎn)數(shù)為：2n,n!, nnp(n)是n的多項(xiàng)式，是生成一個(gè)結(jié)點(diǎn)所需的時(shí)間回溯算法的最壞情況時(shí)間復(fù)雜度可達(dá)O(p(n)n!)（或O(p(n)2n)或O(p(n)nn)）。 蒙特卡羅方法（Monte Carlo）基本思想是在狀態(tài)空間樹(shù)中隨機(jī)選擇一條路徑(x0, x1, xn1)。設(shè)X是這條隨機(jī)路徑上第k+1層的結(jié)點(diǎn)，代表部分向量(x0, x1, xk1) ，如果在X不受限制的孩子數(shù)目是mk，則認(rèn)為與X同層的其他結(jié)點(diǎn)不受限制的孩子數(shù)目也都是mk。推測(cè)整個(gè)狀態(tài)空間樹(shù)上將實(shí)際生成的結(jié)點(diǎn)數(shù)估計(jì)為 m = 1+m0+m0m1+m0m1m2+ 這種方法一般重復(fù)進(jìn)行

7、幾次，取平均值 【程序8-3】 蒙特卡羅算法int Estimate(SType* x) int k=0, m=1, r=1; do SetType S= xk| xkT(x1,xk1) & Bk(x1,xk=true)； if (!Size(S) return m; r=r*Size(S); m=m+r; xk=Choose(S);k+; while(1);函數(shù)size返回集合S的大小；函數(shù)Choose從集合S中隨機(jī)選擇一個(gè) 8.2 n-皇后 8.2.1 問(wèn)題描述 n-皇后問(wèn)題要求在一個(gè)nn的棋盤上放置n個(gè)皇后，使得它們彼此不受“攻擊”。n-皇后問(wèn)題要求尋找在棋盤上放置這n個(gè)皇后的方案，使得

8、它們中任何兩個(gè)都不在同一行、同一列或同一斜線上。 8.2.2 回溯法求解 皇后問(wèn)題可用n-元組（x0, x1, xn1）表示n-皇后問(wèn)題的解，其中xi表示第i行的皇后所處的列號(hào)(0 xin)。顯式約束的一種觀點(diǎn)是：Si=0, 1, , n1，0in。相應(yīng)的隱式約束為：對(duì)任意0i, jn，當(dāng)ij時(shí)，xixj且|xi-xj|i-j|。此時(shí)的解空間大小為nn。另一種顯式約束的觀點(diǎn)是：Si=0, 1, , n1，0in，且xi xj(0i, jn, ij)。相應(yīng)的隱式約束為：對(duì)任意0i, jn，當(dāng)ij時(shí)，。與此相對(duì)應(yīng)的解空間大小為n!。 如排序問(wèn)題相同，皇后問(wèn)題的狀態(tài)空間樹(shù)是一棵排列樹(shù)。排列樹(shù)有n!個(gè)

9、葉結(jié)點(diǎn)，遍歷排列樹(shù)的時(shí)間為(n!)。 4皇后問(wèn)題對(duì)應(yīng)的排列圖 8.2.3 n-皇后算法 【程序8-4】 n-皇后問(wèn)題的回溯算法bool Place(int k, int i,int* x) /xk=i是否可行/判定兩個(gè)皇后是否在同一列或在同一斜線上 for (int j=0;jk;j+) if (xj=i) | (abs(xj-i)=abs(j-k) return false; return true; void NQueens(int n,int *x) NQueens(0,n,x); void NQueens(int k,int n,int *x) for (int i=0; in;i+)

10、 if (Place(k,i,x) xk=i; if (k=n-1) for(i=0;in;i+) coutxi ; coutendl; else NQueens(k+1,n,x); 4皇后問(wèn)題的兩個(gè)可行解 其中一個(gè)可行解的回溯過(guò)程 實(shí)際生成的樹(shù)結(jié)點(diǎn)XXXXXX 8.2.4 時(shí)間分析可通過(guò)蒙特卡羅法計(jì)算5次試驗(yàn)中實(shí)際需要生成的結(jié)點(diǎn)數(shù)的平均值為1625。8-皇后問(wèn)題狀態(tài)空間樹(shù)的結(jié)點(diǎn)總數(shù)是： 因此，需要實(shí)際生成的結(jié)點(diǎn)數(shù)目大約占總結(jié)點(diǎn)數(shù)的1.55%。 8.3 子集和數(shù) 8.3.1 問(wèn)題描述已知n個(gè)不同正數(shù)wi，0in-1，的集合，求該集合的所有滿足條件的子集，使得每個(gè)子集中的正數(shù)之和等于另一個(gè)給定的

11、正數(shù)M。例82 設(shè)有n=4個(gè)正數(shù)的集合W=w0,w1,w2,w3=(11,13,24,7)和整數(shù)M=31，求W的所有滿足條件的子集，使得子集中的正數(shù)之和等于M。 8.3.2 回溯法求解 解結(jié)構(gòu)形式：可變長(zhǎng)度元組和固定長(zhǎng)度元組?？勺冮L(zhǎng)度元組（x0,xk1,xk），0kn。元組的每個(gè)分量的取值可以是元素值，也可以是選入子集的正數(shù)的下標(biāo)。固定長(zhǎng)度n-元組（x0,x1,xn1），xi0,1, 0in。xi=0，表示wi未選入子集，xi=1，表示wi入選子集。 如同0/1背包問(wèn)題，稱這種從n個(gè)元素的集合中找出滿足某些性質(zhì)的子集的狀態(tài)空間樹(shù)為子集樹(shù)。子集樹(shù)有2n個(gè)解狀態(tài)，遍歷子集樹(shù)的時(shí)間為(2n)。 約定

12、wi為正數(shù)按升序排列，分析xk應(yīng)滿足的約束條件：w0,w1,wk-1,wk,wk+1,wn-1x0,x1,xk-1,xk,xk+1,xn-1s部分和 r剩余和xk=1xk=0s+r-wkMs+rM & s+wkM 8.3.3子集和數(shù)算法 【程序85】子集和數(shù)的回溯算法 void SumOfSub (float s, int k, float r, int* x, float m, float* w) /s部分和 r剩余和 xk=1; if (s+wk=m) /得到一個(gè)可行解 for (int j=0;j=k;j+) coutxj ; coutendl; else if (s+wk=m) ) /

13、搜索右子樹(shù) xk=0; SumOfSub(s, k+1, r-wk, x, m, w); void SumOfSub (int* x, int n, float m, float* w) float r=0; for(int i=0;i=m & w0=m) SumOfSub(0, 0, r, x, m, w); 例83 設(shè)有n=6個(gè)正數(shù)的集合W=(5,10,12,13,15,18)和整數(shù)M=30，求W的所有元素之和為M的子集。 8.4 圖的著色 8.4.1 問(wèn)題描述已知無(wú)向圖G=(V,E)和m種不同的顏色，如果只允許使用這m種顏色對(duì)圖G的結(jié)點(diǎn)著色，每個(gè)結(jié)點(diǎn)著一種顏色。問(wèn)是否存在一種著色方案，使

14、得圖中任意相鄰的兩個(gè)結(jié)點(diǎn)都有不同的顏色。這就是m-著色判定問(wèn)題（m-colorability decision problem）如：地圖著色問(wèn)題 、四色猜想 8.4.2回溯法求解 設(shè)無(wú)向圖G=(V,E)采用如下定義的鄰接矩陣a表示： 解的形式：n-元組(x0,x1,xn1), xi1，m, 0in，表示結(jié)點(diǎn)i的顏色，這就是顯式約束。xi=0表示沒(méi)有可用的顏色。因此解空間的大小為mn。隱式約束可描述為：如果邊(i,j)E，則 xixj。 約束函數(shù)：對(duì)所有i和j，0i,jk，ij，若aij=1，則xixj。 8.4.3 圖著色算法 【程序86】 圖的m著色算法 template void MGra

15、ph:NextValue(int k,int m,int *x) /確定分量xk的取值。1,m。xk初始值=0 do xk=(xk+1) % (m+1);/嘗試下一種顏色 if (!xk) return;/沒(méi)有可用顏色 for (int j=0; jk; j+) /可行判定 if (akj & xk = xj) break; if (j=k) return; /成功 while (1); template void MGraph: mColoring(int k, int m, int *x) do NextValue(k,m,x); /為xk分配顏色 if (!xk) break; if (

16、k = n-1) /得到圖G的一種m-著色方案 for (int i=0; in; i+) cout xi ; cout endl; else mColoring(k+1,m,x); /繼續(xù)深入下一個(gè)分量 while(1); template void MGraph: mColoring(int m,int *x) mColoring(0,m,x); 8.4.4 時(shí)間分析算法的計(jì)算時(shí)間上界可由狀態(tài)空間樹(shù)的結(jié)點(diǎn)數(shù)確定。每個(gè)結(jié)點(diǎn)的處理時(shí)間即NextValue的執(zhí)行時(shí)間，為O(mn)。因此總時(shí)間為 8. 5 哈密頓環(huán) 8.5.1 問(wèn)題描述已知圖G=(V,E)是一個(gè)n個(gè)結(jié)點(diǎn)的連通圖。連通圖G的一個(gè)哈密

17、頓環(huán)(Hamiltonlan cycle)是圖G的一個(gè)回路，它經(jīng)過(guò)圖中每個(gè)結(jié)點(diǎn)，且只經(jīng)過(guò)一次。一個(gè)哈密頓環(huán)是從某個(gè)結(jié)點(diǎn)v0V開(kāi)始，沿著圖G的n條邊環(huán)行的一條路徑（v0,v1,vn1,vn），其中，(vi,vi+1)E,0in，它訪問(wèn)圖中每個(gè)結(jié)點(diǎn)且只訪問(wèn)一次，最后返回開(kāi)始結(jié)點(diǎn)，即除v0=vn，路徑上其余結(jié)點(diǎn)各不相同。 8.5.2 哈密頓環(huán)算法對(duì)于n個(gè)結(jié)點(diǎn)的圖G=(V,E)的哈密頓環(huán)問(wèn)題，采用n-元組表示問(wèn)題的解 (x0,x1,xn1)。顯式約束：每個(gè)xi0,1,n-1, 0in，代表路徑上一個(gè)結(jié)點(diǎn)的編號(hào)。因此解空間的大小為nn。隱式約束：可描述為：xixj,0i,jn，ij，且（xi,xi+1）

18、E，xi,xi+1V，i=0,1,n2，又（xn1，x0）E。哈密頓環(huán)問(wèn)題的分析和求解方法與圖的m-著色問(wèn)題非常相似 【程序87】哈密頓環(huán)算法 template void MGraph:NextValue(int k,int *x) /求第k個(gè)分量的取值，結(jié)點(diǎn)從1開(kāi)始編號(hào) do xk=(xk+1)% n; /循環(huán)去下一個(gè)結(jié)點(diǎn)編號(hào) if (!xk) return; /為0值，表示無(wú)可取值 if (axk-1xk) /可行性判定 for (int j=0;jk;j+) if (xj=xk) break; if (j=k) if (kn-1)|(k=n-1) & axn-1x0) return; w

19、hile(1); template void ExtMGraph:Hamiltonian(int k,int *x) /第k個(gè)分量的遞歸處理 do NextValue(k,x); /返回下一個(gè)可取值 if (!xk) return; /無(wú)可取值，剪枝處理 if (k=n-1) for (int i=0; in; i+) coutxi ; cout 0n; else Hamiltonian(k+1,x); /深度優(yōu)先進(jìn)入下一層 while (1); template void ExtMGraph: Hamiltonian(int *x) Hamiltonian(1,x); /結(jié)點(diǎn)從1開(kāi)始編號(hào) 8

20、.6 0/1背包問(wèn)題問(wèn)題：給定M0, wi0, pi0 (0=in), 求一個(gè)n元組(x0,x1,xn-1), xi 0,1, 使得wixi=M且pixi 最大。解空間中構(gòu)成一顆子集樹(shù)，共有2n解狀態(tài)。約束條件： xi 0,1wixi=M求最優(yōu)解目標(biāo)函數(shù)： pixi 8.6 0/1背包問(wèn)題n=4的狀態(tài)空間樹(shù) 8.6 0/1背包問(wèn)題記cw表示當(dāng)前考慮k-1個(gè)物品后，已選入物品的重量記cp表示當(dāng)前考慮k-1個(gè)物品后，已選入物品的收益設(shè)計(jì)約束函數(shù)Bk(x0,x1,xk)：第k個(gè)物品要選入（xk=1）必須滿足：cw+wkM設(shè)計(jì)限界函數(shù)：剪去不含最優(yōu)解的分枝 8.6 0/1背包問(wèn)題設(shè)計(jì)限界函數(shù)：中間狀態(tài)

21、X：剩余物品k+1,k+2,n-1剩余載重為M=M-cw記Y、rp分別表示對(duì)應(yīng)一般背包問(wèn)題的最優(yōu)解和最優(yōu)解值Z表示對(duì)應(yīng)0/1背包問(wèn)題的任意可行解Y=yk+1,yk+2,yn-1Z=xk+1,xk+2,xn-1則有：因此以bp=cp+rp作為X結(jié)點(diǎn)的上界值 8.6 0/1背包問(wèn)題限界函數(shù)的實(shí)現(xiàn)通過(guò)發(fā)現(xiàn)的可行解確定當(dāng)前最優(yōu)解值L，后續(xù)的可行解收益fp，必須不小于L，也就是以L為下界任一中間狀態(tài)X：若其上界值bpL，代表其下不含最優(yōu)解，應(yīng)剪去以X為根的子樹(shù)。 限界函數(shù)作用示例M=110, n=8, W=(1,11,21,23,33,43,45,55), P=(11,21,31,33,43,53,55

22、,65) 關(guān)鍵程序上界函數(shù)值templateT Knapsack: Bound(int k,T cp, T cw) /cp是當(dāng)前收益，cw是當(dāng)前背包重量，k是當(dāng)前待考察的物品編號(hào) T b=cp, c=cw; for (int i=k+1;in; i+) c+=wi; if (cm) b+=pi; else return (b+(1- (c-m)/wi)*pi); return b; 8.7 批處理作業(yè)調(diào)度(最小平均完成時(shí)間) 8.7.1 問(wèn)題描述設(shè)有n個(gè)作業(yè)的集合0,1,n-1，每個(gè)作業(yè)有兩項(xiàng)任務(wù)要求分別在2臺(tái)設(shè)備P1和P2上完成。每個(gè)作業(yè)必須先在P1上加工，然后在P2上加工。P1和P2加工作

23、業(yè)i所需的時(shí)間分別為ai和bi。作業(yè)i的完成時(shí)間fi(S)是指在調(diào)度方案S下，該作業(yè)的所有任務(wù)得以完成的時(shí)間，則是采用調(diào)度方案S的平均完成時(shí)間。 批處理作業(yè)調(diào)度(batch job schedule)問(wèn)題要求確定這n個(gè)作業(yè)的最優(yōu)作業(yè)調(diào)度方案使其MFT最小。這等價(jià)于求使得所有作業(yè)的完成時(shí)間之和最小的調(diào)度方案。 例85 設(shè)有三個(gè)作業(yè)和兩臺(tái)設(shè)備，作業(yè)任務(wù)的處理時(shí)間為（a0,a1,a2）=(2,3,2)和（b0,b1,b2）=(1,1,3)。這三個(gè)作業(yè)有6種可能的調(diào)度方案：(0,1,2),(0,2,1),(1,0,2), (1,2,0),(2,0,1),(2,1,0)它們相應(yīng)的完成時(shí)間之和分別是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 回溯法求解對(duì)于雙機(jī)批處理作業(yè)調(diào)度問(wèn)題，其可行解是n個(gè)作業(yè)所有可能的排列，每一種排列代表一種作業(yè)調(diào)度方案S，批處理作業(yè)調(diào)度問(wèn)題