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

1、算法設(shè)計(jì)與分析DeSign and Analysis of AlgorithmsIn C+“十一五”國(guó)家級(jí)規(guī)劃教材 陳慧南 編著電子工業(yè)出版社 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月第2部分 算法設(shè)計(jì)策略 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月第8章 回溯法 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月8.1 一般方法 8.2 n-皇后 8.3 子集和數(shù) 8.4 圖的著色 8.5 哈密頓環(huán) 8.6 0/1背包 8.7 批處理作業(yè)調(diào)度 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月8.1 一般方法 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月8.1.1 基本概念 規(guī)定每個(gè)xi取值的約束條件稱(chēng)為顯式約束（explic

2、it constraint）。 對(duì)給定的一個(gè)問(wèn)題實(shí)例，顯式約束規(guī)定了所有可能的元組，它們組成問(wèn)題的候選解集，被稱(chēng)為該問(wèn)題實(shí)例的解空間（solution space）。 隱式約束（implicit constraint）給出了判定一個(gè)候選解是否為可行解的條件。 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月目標(biāo)函數(shù)，也稱(chēng)代價(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)稱(chēng)為一個(gè)問(wèn)題狀態(tài)（problem state）。如果從根到樹(shù)中某個(gè)狀態(tài)的路徑代表一個(gè)作為候選解

3、的元組，則稱(chēng)該狀態(tài)為解狀態(tài)（solution state）。如果從根到某個(gè)解狀態(tài)的路徑代表一個(gè)作為可行解的元組，則稱(chēng)該解狀態(tài)為答案狀態(tài)(answer state)。 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月8.1.2剪枝函數(shù)和回溯法 為了提高搜索效率，在搜索過(guò)程中使用約束函數(shù)（constraint function），可以避免無(wú)謂地搜索那些已知不含答案狀態(tài)的子樹(shù)。如果是最優(yōu)化問(wèn)題，還可使用限界函數(shù)（bound function）剪去那些不可能包含最優(yōu)答案結(jié)點(diǎn)的子樹(shù)。約束函數(shù)和限界函數(shù)的目的是相同的，都為了剪去不必要搜索的子樹(shù)，減少問(wèn)題求解所需實(shí)際生成的狀態(tài)結(jié)點(diǎn)數(shù)，它們統(tǒng)稱(chēng)為剪枝函數(shù)（prunin

4、g function）。 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月使用剪枝函數(shù)的深度優(yōu)先生成狀態(tài)空間樹(shù)中結(jié)點(diǎn)的求解方法稱(chēng)為回溯法（backtracking）；廣度優(yōu)先生成結(jié)點(diǎn)，并使用剪枝函數(shù)的方法稱(chēng)為分枝限界法（branch-and-bound）。 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月【程序81】遞歸回溯法Void RBacktrack(int k)/應(yīng)以Rbacktrack(0)調(diào)用本函數(shù) for (每個(gè)xk,使得 xkT(x0,xk-1) &(Bk(x0,xk) if ( (x0,x1,xk)是一個(gè)可行解) 輸出 (x0,x1,xk); RBacktrack(k+1); 南京郵電大學(xué)計(jì)算機(jī)

5、學(xué)院 2008年3月【程序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-; 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月8.1.3回溯法的效率分析 回溯算法的最壞情況時(shí)間復(fù)雜度可達(dá)O(p(n)n!)（或O(p(n)2n)或O(p(n)nn)），這里p(n)是n的多項(xiàng)式，是生成一個(gè)結(jié)點(diǎn)所需的時(shí)間。 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月蒙特卡羅方法（Monte

6、Carlo）。這種估計(jì)方法的基本思想是在狀態(tài)空間樹(shù)中隨機(jī)選擇一條路徑(x0, x1, xn1)。設(shè)X是這條隨機(jī)路徑上，代表部分向量(x0, x1, xk1)的結(jié)點(diǎn)，如果在X處不受限制的孩子數(shù)目是mk，則認(rèn)為與X同層的其他結(jié)點(diǎn)不受限制的孩子數(shù)目也都是mk。整個(gè)狀態(tài)空間樹(shù)上將實(shí)際生成的結(jié)點(diǎn)數(shù)估計(jì)為 m = 1+m0+m0m1+m0m1m2+ 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月【程序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

7、(S) return m; r=r*Size(S);m=m+r; xk=Choose(S);k+; while(1); 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月8.2 n-皇后 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月8.2.1 問(wèn)題描述 n-皇后問(wèn)題要求在一個(gè)nn的棋盤(pán)上放置n個(gè)皇后，使得它們彼此不受“攻擊”。n-皇后問(wèn)題要求尋找在棋盤(pán)上放置這n個(gè)皇后的方案，使得它們中任何兩個(gè)都不在同一行、同一列或同一斜線(xiàn)上。 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月8.2.2 回溯法求解 皇后問(wèn)題可用n-元組（x0, x1, xn1）表示n-皇后問(wèn)題的解，其中xi表示第i行的皇后所處的列號(hào)(0 xin)。顯式約

8、束的一種觀點(diǎn)是：Si=0, 1, , n1，0in。相應(yīng)的隱式約束為：對(duì)任意0i, jn，當(dāng)ij時(shí)，xixj且。此時(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!。 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月皇后問(wèn)題的狀態(tài)空間樹(shù)是一棵排列樹(shù)。排列樹(shù)有n!個(gè)葉結(jié)點(diǎn)，遍歷排列樹(shù)的時(shí)間為(n!)。 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月8.2.3 n-皇后算法 【程序8-4】 n-皇后問(wèn)題的回溯算法bool Plac

9、e(int k, int i,int* x)/判定兩個(gè)皇后是否在同一列或在同一斜線(xiàn)上 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); 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月void NQueens(int k,int n,int *x) for (int i=0; in;i+) if (Place(k,i,x) xk=i; if (k=n-1) for(i=0;in;i+)coutxi ; coute

10、ndl; else NQueens(k+1,n,x); 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月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%。 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月8.3 子集和數(shù) 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月8.3.1 問(wèn)題描述已知n個(gè)不同正數(shù)wi，0in-1，的集合，求該集合

11、的所有滿(mǎn)足條件的子集，使得每個(gè)子集中的正數(shù)之和等于另一個(gè)給定的正數(shù)M。例82 設(shè)有n=4個(gè)正數(shù)的集合W=w0,w1,w2,w3=(11,13,24,7)和整數(shù)M=31，求W的所有滿(mǎn)足條件的子集，使得子集中的正數(shù)之和等于M。 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月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入選子集。 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月 南京

12、郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月稱(chēng)這種從n個(gè)元素的集合中找出滿(mǎn)足某些性質(zhì)的子集的狀態(tài)空間樹(shù)為子集樹(shù)。子集樹(shù)有2n個(gè)解狀態(tài)，遍歷子集樹(shù)的時(shí)間為(2n)。 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月約束函數(shù)：Bk(x0,x1,xk) 為true，當(dāng)且僅當(dāng) 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月8.3.3子集和數(shù)算法 【程序85】子集和數(shù)的回溯算法 void SumOfSub (float s,int k,float r,int* x,float m,float* w) xk=1; if (s+wk=m) for (int j=0;j=k;j+) coutxj

13、; coutendl; 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月 else if (s+wk+wk+1=m)&(s+wk+1=m) 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); 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月例83 設(shè)有n=6個(gè)正數(shù)的集合W=(5,10,12,13,15,18)和整數(shù)M=30，求W的所有元素之和為M的子集。 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月

14、8.4 圖的著色 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月8.4.1 問(wèn)題描述已知無(wú)向圖G=(V,E)和m種不同的顏色，如果只允許使用這m種顏色對(duì)圖G的結(jié)點(diǎn)著色，每個(gè)結(jié)點(diǎn)著一種顏色。問(wèn)是否存在一種著色方案，使得圖中任意相鄰的兩個(gè)結(jié)點(diǎn)都有不同的顏色。這就是m-著色判定問(wèn)題（m-colorability decision problem） 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月8.4.2回溯法求解 設(shè)無(wú)向圖G=(V,E)采用如下定義的鄰接矩陣a表示： 解的形式：n-元組(x0,x1,xn1), xi1，m, 0in，表示結(jié)點(diǎn)i的顏色，這就是顯式約束。xi=0表

15、示沒(méi)有可用的顏色。因此解空間的大小為mn。隱式約束可描述為：如果邊(i,j)E，則 xixj。 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月約束函數(shù)：對(duì)所有i和j，0i,jk，ij，若aij=1，則xixj。 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月8.4.3 圖著色算法 【程序86】 圖的m著色算法 template void MGraph:NextValue(int k,int m,int *x) do xk=(xk+1) % (m+1); if (!xk) return; for (int j=0; jk; j+) if (akj & xk = xj) break; if (j=k) retur

16、n; while (1); 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月 template void MGraph: mColoring(int k,int m,int *x) do NextValue(k,m,x); if (!xk) break; if (k = n-1) for (int i=0; in; i+) cout xi ; cout endl; else mColoring(k+1,m,x); while(1); 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月template void MGraph: mColoring(int m,int *x) mColoring(0,m,x); 南京郵

17、電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月8.4.4 時(shí)間分析算法的計(jì)算時(shí)間上界可由狀態(tài)空間樹(shù)的結(jié)點(diǎn)數(shù)確定。每個(gè)結(jié)點(diǎn)的處理時(shí)間即NextValue的執(zhí)行時(shí)間，為O(mn)。因此總時(shí)間為 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月8. 5 哈密頓環(huán) 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月8.5.1 問(wèn)題描述已知圖G=(V,E)是一個(gè)n個(gè)結(jié)點(diǎn)的連通圖。連通圖G的一個(gè)哈密頓環(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，它訪(fǎng)問(wèn)圖中每個(gè)結(jié)點(diǎn)且

18、只訪(fǎng)問(wèn)一次，最后返回開(kāi)始結(jié)點(diǎn)，即除v0=vn，路徑上其余結(jié)點(diǎn)各不相同。 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月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）E，xi,xi+1V，i=0,1,n2，又（xn1，x0）E。哈密頓環(huán)問(wèn)題的分析和求解方法與圖的m-著色問(wèn)題非常相似 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月【程

19、序87】哈密頓環(huán)算法 template void MGraph:NextValue(int k,int *x) do xk=(xk+1)% n; if (!xk) return; 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; while(1); 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月template void ExtMGraph:Hamiltonian(int k,int *x) do NextValue(k,x); if (!xk) return

20、; if (k=n-1) for (int i=0; in; i+) coutxi ; cout 0n; else Hamiltonian(k+1,x); while (1); 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月template void ExtMGraph: Hamiltonian(int *x) Hamiltonian(1,x); 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月8.7 批處理作業(yè)調(diào)度 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月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

21、和P2加工作業(yè)i所需的時(shí)間分別為ai和bi。作業(yè)i的完成時(shí)間fi(S)是指在調(diào)度方案S下，該作業(yè)的所有任務(wù)得以完成的時(shí)間，則是采用調(diào)度方案S的平均完成時(shí)間。 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月批處理作業(yè)調(diào)度(batch job schedule)問(wèn)題要求確定這n個(gè)作業(yè)的最優(yōu)作業(yè)調(diào)度方案使其MFT最小。這等價(jià)于求使得所有作業(yè)的完成時(shí)間之和最小的調(diào)度方案。 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月例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,

22、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。 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月8.7.2 回溯法求解對(duì)于雙機(jī)批處理作業(yè)調(diào)度問(wèn)題，其可行解是n個(gè)作業(yè)所有可能的排列，每一種排列代表一種作業(yè)調(diào)度方案S，其目標(biāo)函數(shù)是使FT(S)具有最小值的調(diào)度方案或作業(yè)排列是問(wèn)題的最優(yōu)解。對(duì)于雙機(jī)作業(yè)調(diào)度，存在一個(gè)最優(yōu)非搶先調(diào)度方案，使得在P1和P2上的作業(yè)完全以相同次序處理。 批處理作業(yè)調(diào)度問(wèn)題的狀態(tài)空間樹(shù)解空間的大小為 n！。 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2008年3月