文稿案例算法

1、l采用采用深度優(yōu)先深度優(yōu)先產(chǎn)生產(chǎn)生狀態(tài)空間樹狀態(tài)空間樹的結(jié)點，并使用的結(jié)點，并使用剪枝函數(shù)剪枝函數(shù)的的方法稱為方法稱為回溯法回溯法。l回溯法的基本做法是：回溯法的基本做法是：按按深度優(yōu)先策略深度優(yōu)先策略，從根結(jié)點出發(fā)，從根結(jié)點出發(fā)搜索搜索問題的問題的狀態(tài)空間樹狀態(tài)空間樹，求問題的求問題的可行解可行解或最優(yōu)解或最優(yōu)解。算法搜索至任一結(jié)點時，先判。算法搜索至任一結(jié)點時，先判斷斷以該結(jié)點為根的子樹以該結(jié)點為根的子樹是否包含問題的解。是否包含問題的解。如果肯定如果肯定不包含不包含，則跳過對該結(jié)點為根的子樹的搜索，逐，則跳過對該結(jié)點為根的子樹的搜索，逐層向其祖先結(jié)點層向其祖先結(jié)點回溯回溯；否則否則，進(jìn)入

2、進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。該子樹，繼續(xù)按深度優(yōu)先策略搜索。回溯法回溯法適用于適用于解一些解一些組合數(shù)相當(dāng)大組合數(shù)相當(dāng)大的問題。的問題。 回溯法要求問題的解向量具有回溯法要求問題的解向量具有n-n-元組元組( (x1,x2,xn) )的形式，每個解分量的形式，每個解分量xi從一個給定的集合從一個給定的集合S Si i取值。取值。l顯式約束顯式約束：規(guī)定每個規(guī)定每個xi取值的約束條件。取值的約束條件。（顯式約束規(guī)定了問題的（顯式約束規(guī)定了問題的候選解集候選解集解空間解空間）解空間：解空間：對于問題的一個實例，解向量滿足對于問題的一個實例，解向量滿足顯式約束條件顯式約束條件的所有多元組，構(gòu)

3、成了該實例的一個解空間。的所有多元組，構(gòu)成了該實例的一個解空間。通常情況下通常情況下,回溯法的回溯法的求解目標(biāo)求解目標(biāo)是在狀態(tài)空間樹上找出滿足是在狀態(tài)空間樹上找出滿足約束條件的約束條件的所有可行解所有可行解.l隱式約束隱式約束：給出了判定一個候選解是否為給出了判定一個候選解是否為可行解可行解的條件。的條件。為滿足問題的解而對不同分量之間施加的約束。為滿足問題的解而對不同分量之間施加的約束。例例8-1 ii+1xxaa一種方法：一種方法：l顯式約束顯式約束解空間大小為解空間大小為nnl隱式約束隱式約束ii+1xxaa另一種方法：另一種方法：l顯式約束顯式約束 解空解空間大小為間大小為n!l隱式約

4、束隱式約束ii+1xxaa注意：注意：同一個問題可以有多種表示同一個問題可以有多種表示，有些表示方法更簡單，有些表示方法更簡單，所需表示的狀態(tài)空間更小，搜索方法更簡單。所需表示的狀態(tài)空間更小，搜索方法更簡單。狀態(tài)空間樹狀態(tài)空間樹：描述描述問題問題解空間解空間的樹形結(jié)構(gòu)。的樹形結(jié)構(gòu)。樹中每個結(jié)點稱為一個樹中每個結(jié)點稱為一個問題狀態(tài)問題狀態(tài)；若從根到樹中某個狀態(tài)的路徑代表一個若從根到樹中某個狀態(tài)的路徑代表一個候選解候選解元組，則該元組，則該狀態(tài)為狀態(tài)為解狀態(tài)解狀態(tài)；若從根到某個解狀態(tài)的路徑代表一個若從根到某個解狀態(tài)的路徑代表一個可行解可行解元組，則該解元組，則該解狀態(tài)為狀態(tài)為答案狀態(tài)答案狀態(tài)；如果

5、求解的是如果求解的是最優(yōu)化問題最優(yōu)化問題，還要用目標(biāo)函數(shù)衡量每個答案，還要用目標(biāo)函數(shù)衡量每個答案結(jié)點，找出其中結(jié)點，找出其中目標(biāo)函數(shù)目標(biāo)函數(shù)取取最優(yōu)值最優(yōu)值的的最優(yōu)答案結(jié)點最優(yōu)答案結(jié)點。有有n!個葉結(jié)點（解狀態(tài)）個葉結(jié)點（解狀態(tài)）01211220022011012738510151349611161412如：（例如：（例8-18-1）n n個元素排序問題。個元素排序問題。若若n=3則則狀態(tài)空間樹狀態(tài)空間樹為：為：排序問題一般不排序問題一般不用回溯法求解用回溯法求解又如：又如：0-10-1背包問題。背包問題。若若n=3則則狀態(tài)空間樹狀態(tài)空間樹為一個完全二叉樹：為一個完全二叉樹：有有2n個解狀態(tài)個

6、解狀態(tài)101101012364570111101091013812 14015窮舉搜索法窮舉搜索法:l使用某種搜索方法，檢查狀態(tài)空間樹中使用某種搜索方法，檢查狀態(tài)空間樹中每個每個問題狀態(tài)問題狀態(tài)；l如果是如果是解狀態(tài)解狀態(tài)則用則用判定函數(shù)判定函數(shù)判定它是否是判定它是否是答案結(jié)點答案結(jié)點；l對于對于最優(yōu)化問題最優(yōu)化問題，搜索過程中還需對每個答案結(jié)點計算其，搜索過程中還需對每個答案結(jié)點計算其目標(biāo)函數(shù)值，記錄下其中最優(yōu)者。目標(biāo)函數(shù)值，記錄下其中最優(yōu)者?；厮莘ɑ厮莘ǎ簂在在求解的過程中求解的過程中，隨著搜索算法的進(jìn)展，以，隨著搜索算法的進(jìn)展，以深度優(yōu)先深度優(yōu)先方式，方式，逐個生成逐個生成狀態(tài)空間樹中結(jié)

7、點；狀態(tài)空間樹中結(jié)點；l為提高搜索效率，在搜索過程中用為提高搜索效率，在搜索過程中用約束函數(shù)約束函數(shù)和和限界函數(shù)限界函數(shù)（統(tǒng)稱（統(tǒng)稱剪枝函數(shù)剪枝函數(shù)）來剪去不必要搜索的子樹，減少問題求）來剪去不必要搜索的子樹，減少問題求解所需解所需實際生成的實際生成的狀態(tài)空間樹結(jié)點數(shù)，從而避免無效搜索。狀態(tài)空間樹結(jié)點數(shù)，從而避免無效搜索。常用的常用的剪枝函數(shù)剪枝函數(shù)：用用約束函數(shù)約束函數(shù)剪去已知不含剪去已知不含答案狀態(tài)（答案狀態(tài)（可行解可行解）的子樹；的子樹；用用限界函數(shù)限界函數(shù)剪去得不到剪去得不到最優(yōu)答案結(jié)點（最優(yōu)答案結(jié)點（最優(yōu)解最優(yōu)解）的子樹。的子樹。回溯法解題的一個回溯法解題的一個顯著特征顯著特征是：在

8、是：在搜索過程中搜索過程中動態(tài)動態(tài)產(chǎn)生問題的解空間。產(chǎn)生問題的解空間。回溯法對解空間作深度優(yōu)先搜索，因此，在一般情況下用遞回溯法對解空間作深度優(yōu)先搜索，因此，在一般情況下用遞歸方法實現(xiàn)回溯法。歸方法實現(xiàn)回溯法。程序程序8-1 遞歸回溯算法框架遞歸回溯算法框架void RBacktrack (int k) for (每個每個xk,使得使得xk T(x0,.,xk-1)&(Bk(x0,.,xk) / T(x0,x1,.,xk-1)表示沿路徑表示沿路徑(x0,x1,.,xk-1)從根到某個問題狀態(tài)從根到某個問題狀態(tài)時，時，孩子結(jié)點孩子結(jié)點xk可取值的集合可取值的集合。/ Bk(x0,x1,.

9、,xk)為約束函數(shù)。若子樹上不含任何答案狀態(tài)，則為約束函數(shù)。若子樹上不含任何答案狀態(tài)，則為為false；否則；否則,為為true。if (x0,x1,.,xk)是一個可行解是一個可行解)/判斷是否可行解判斷是否可行解輸出輸出(x0,x1,.,xk); /輸出可行解輸出可行解RBacktrack(k+1);/深度優(yōu)先進(jìn)入下一層深度優(yōu)先進(jìn)入下一層 由于葉結(jié)點的孩子集合由于葉結(jié)點的孩子集合T( )為空集合，因此對于有限狀態(tài)空為空集合，因此對于有限狀態(tài)空間樹，算法必能終止。間樹，算法必能終止。采用樹的非遞歸深度優(yōu)先遍歷算法，可將回溯法表示為一個采用樹的非遞歸深度優(yōu)先遍歷算法，可將回溯法表示為一個非遞歸

10、迭代過程。非遞歸迭代過程。程序程序8-2 迭代回溯算法框架迭代回溯算法框架void IBacktrack(int n) int k=0; while (k=0) if (還剩下尚未檢測的還剩下尚未檢測的xk,使得使得xk T(x0,.,xk-1)&Bk(x0,.,xk) if (x0,x1,.,xk)是一個可行解是一個可行解) 輸出輸出(x0,x1,.,xk);/輸出可行解輸出可行解 k+;/深度優(yōu)先進(jìn)入下一層深度優(yōu)先進(jìn)入下一層 else k-;/回溯到上一層回溯到上一層 用用蒙特卡羅（蒙特卡羅（Monte Carlo）方法）方法估計回溯法處理實例時，估計回溯法處理實例時，實際生成的結(jié)

11、點數(shù)：實際生成的結(jié)點數(shù)：l在狀態(tài)空間樹中在狀態(tài)空間樹中,從根開始從根開始隨機(jī)隨機(jī)選擇一條路徑選擇一條路徑(x0,x1,.,xn-1);l假定搜索樹中這條假定搜索樹中這條隨機(jī)選出的路徑上隨機(jī)選出的路徑上，代表部分向量，代表部分向量(x0,x1,.,xk-1)的結(jié)點處不受限制的的結(jié)點處不受限制的孩子數(shù)目孩子數(shù)目，與，與同層的其他同層的其他路徑上路徑上的結(jié)點不受限制的的結(jié)點不受限制的孩子數(shù)目孩子數(shù)目一樣，都是一樣，都是mk;l則可以估計整個狀態(tài)空間樹上則可以估計整個狀態(tài)空間樹上實際生成的結(jié)點數(shù)實際生成的結(jié)點數(shù)為為: m=1+m0+m0m1+m0m1m2+.回溯法的時間通常取決于：狀態(tài)空間樹上回溯法的

12、時間通常取決于：狀態(tài)空間樹上實際生成的實際生成的那部分那部分問題狀態(tài)的數(shù)目（即：問題狀態(tài)的數(shù)目（即：結(jié)點總數(shù)結(jié)點總數(shù)）。）。程序程序8-3 蒙特卡羅算法蒙特卡羅算法do SetType S= xk | xk T(x1,.,xk-1)& Bk(x1,.,xk)=true; if (!Size(S) return m; r=r*Size(S);/r為第為第k層中未受限結(jié)點數(shù)的估計值層中未受限結(jié)點數(shù)的估計值 m=m+r;/m為狀態(tài)空間樹中結(jié)點總數(shù)的估計值為狀態(tài)空間樹中結(jié)點總數(shù)的估計值 xk=Choose(S); /從集合從集合S S中為中為xk隨機(jī)選擇一個值，向下生成隨機(jī)路徑隨機(jī)選擇一個值，

13、向下生成隨機(jī)路徑 k+;while (1);在nn格的棋盤上放置彼此不受攻擊的n個皇后。按照國際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。n后問題等價于在nn格的棋盤上放置n個皇后，任何2個皇后不放在同一行或同一列或同一斜線上。1 2 3 4 5 6 7 812345678QQQQQQQQ 第一種顯式約束觀點：第一種顯式約束觀點：l顯式約束：顯式約束：xi=0,1,2, ,n-1l隱式約束：當(dāng)隱式約束：當(dāng)i j時，時， 1)不同列：不同列：xi xj 2)不處于同一正、反對角線：不處于同一正、反對角線：|i-j| |xi-xj|對應(yīng)的解空間大小為：對應(yīng)的解空間大小為：n

14、n 第二種顯式約束觀點：第二種顯式約束觀點：l顯式約束：顯式約束： 1)xi=0,1,2, ,n-1 2)不同列：不同列：xi xj (i j)l隱式約束：不處于同一正、反對角線：隱式約束：不處于同一正、反對角線：|i-j| |xi-xj| (i j)對應(yīng)的解空間大小為：對應(yīng)的解空間大小為：n!解向量：解向量：(x0, x1, , xn-1),其中其中xi表示第表示第i行的皇后所處的列號。行的皇后所處的列號。（采用第一種顯式約束觀點）設(shè)計約束函數(shù)：（采用第一種顯式約束觀點）設(shè)計約束函數(shù)： 對對0i,jk,當(dāng)當(dāng)i j時，要求時，要求xi xj且且|i-j| |xi-xj| 可得可得程序程序8-4

15、 求求n-皇后問題的全部可行解（見下頁）：皇后問題的全部可行解（見下頁）：一般稱這種用于確定一般稱這種用于確定n個元素的排列滿足某些性質(zhì)的狀態(tài)空間樹個元素的排列滿足某些性質(zhì)的狀態(tài)空間樹為為排列樹排列樹。（采用第二種顯式約束觀點的）（采用第二種顯式約束觀點的）4-皇后問題狀態(tài)空間樹皇后問題狀態(tài)空間樹見見P180 圖圖8-3程序程序8-4 n-8-4 n-皇后問題的回溯算法皇后問題的回溯算法bool Place(int k,int i,int *x)/約束函數(shù)（隱式）約束函數(shù)（隱式）/判斷兩皇后是否在同一列或斜線上判斷兩皇后是否在同一列或斜線上 for (int j=1;jk;j+) if (xj

16、=i)|(abs(xj-i)=abs(j-k) return false;/i為當(dāng)前第為當(dāng)前第k行皇后的列數(shù)行皇后的列數(shù)/xj為已選定的前面為已選定的前面 0k-1 行皇后的列數(shù)行皇后的列數(shù) return true; void NQueens(int k,int n,int *x) for (int i=0;in;i+) /顯式約束顯式約束 if (Place(k,I,x)/約束函數(shù)（隱式）約束函數(shù)（隱式） xk=i; if (k=n-1) for (i=0;in;i+) coutxi“ ”; /輸出一個可行解輸出一個可行解 coutendl;else NQueens(k+1,n,x);/深度

17、優(yōu)先進(jìn)入下一層深度優(yōu)先進(jìn)入下一層 可求得可求得n-皇后問皇后問題的所有可行解題的所有可行解圖圖8-5 顯示了顯示了4-皇后問題得到第一個解的步驟皇后問題得到第一個解的步驟:QQQQQQQQQQQQQQQQQQ圖圖8-6 顯示了顯示了4-皇后問題在得到第一個答案狀態(tài)時，實皇后問題在得到第一個答案狀態(tài)時，實際生成的那部分狀態(tài)空間樹際生成的那部分狀態(tài)空間樹:（對比對比 圖圖8-3的狀態(tài)空間樹）的狀態(tài)空間樹）011131312313911142192030218242916313022158BBBBBBBans10ikxiwM圖圖8-8 子集和數(shù)問題（可變元組解）狀態(tài)空間樹子集和數(shù)問題（可變元組解）狀

18、態(tài)空間樹03123331239813431022313161415612112357每個問題狀態(tài)都是一個解狀每個問題狀態(tài)都是一個解狀態(tài)，代表一個候選解元組。態(tài)，代表一個候選解元組。10niiiw xM圖圖8-9 子集和數(shù)問題（固定長度元組解）狀態(tài)空間樹子集和數(shù)問題（固定長度元組解）狀態(tài)空間樹每個葉結(jié)點是一個解狀態(tài)，每個葉結(jié)點是一個解狀態(tài)，代表一個候選解元組。代表一個候選解元組。非葉結(jié)點代表部分向量。非葉結(jié)點代表部分向量。一般稱這種從一般稱這種從n個元素的集合中找出滿足某些性質(zhì)的子集的狀態(tài)個元素的集合中找出滿足某些性質(zhì)的子集的狀態(tài)空間樹為空間樹為子集樹子集樹。101101021826273031

19、 2601611010412132917 14015101101056711809110101920212425 22023103101程序程序8-5（見下頁見下頁）的）的前置條件前置條件： （若（若wi已按非減次序排列已按非減次序排列)和和后置條件后置條件：在以在以(x0,x1,.,xk)為根的子樹上搜索答案結(jié)點。為根的子樹上搜索答案結(jié)點。11100knkiiiiikii kiw xwMw xwM且110&(,MM)kniiiii kkw xwsrswsr（采用固定長度元組解采用固定長度元組解）每次選擇）每次選擇xk之前應(yīng)判斷是否滿足之前應(yīng)判斷是否滿足約束函數(shù)約束函數(shù)Bk(x0,x1

20、,.,xk)：程序程序8-5 子集和數(shù)的回溯算法子集和數(shù)的回溯算法void SumOfSub(float s,int k,float r,int *x,float m,float *w)/s為已選擇的元素和，為已選擇的元素和，r為剩余元素和，為剩余元素和，k為當(dāng)前層數(shù)（即將選擇的元素下標(biāo)）為當(dāng)前層數(shù)（即將選擇的元素下標(biāo)）/m為子集數(shù)和，為子集數(shù)和，w為權(quán)值元組，為權(quán)值元組，x為解元組為解元組xk=1; if (s+wk=m) /xk=1若得到一個可行解若得到一個可行解 for (int j=0;j=k;j+) coutxj ;coutendl; else if (s+wk+wk+1=m)&am

21、p;(s+wk+1=m) /xk=0，同時約束函數(shù)，同時約束函數(shù)Bk+1為真為真 xk=0; SumOfSub(s,k+1,r-wk,x,m,w);/則沿右子樹向第則沿右子樹向第k+1層搜索層搜索 因因(s+wk)+(r-wk)=s+r值未變，因此省略判斷。值未變，因此省略判斷。由于進(jìn)入第由于進(jìn)入第k層之前，總滿足前置條件：層之前，總滿足前置條件：s+wk-1m且且s+rm。 而而進(jìn)入第進(jìn)入第n-1層（最后一層）又有層（最后一層）又有r=wn-1。因此必有。因此必有s+wn-1=s+r=m。所以，只要進(jìn)入第所以，只要進(jìn)入第n-1層，層，函數(shù)總能終止函數(shù)總能終止；否則不可能進(jìn)入第；否則不可能進(jìn)入

22、第n-1層。層。（例例8-3） 設(shè)有設(shè)有n=6個正數(shù)的集合個正數(shù)的集合W=5,10,12,13,15,18和和整數(shù)整數(shù)M=30，求，求W的所有元素之和為的所有元素之和為M的子集。的子集。10000011000101A010100,0,735,1,6815,2,585,2,5815,3,4615,4,3317,3,461B5,3,465,4,330,1,6810,2,580,2,5810,3,4610,4,3312,3,4612,4,3312,5,1801C0,3,4613,4,330,4,33A、B、C為三個答案狀態(tài)（可行解）為三個答案狀態(tài)（可行解）l設(shè)有n個作業(yè)的集合0,1,n-1，每個作業(yè)

23、有兩項任務(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的。 1n0ii)S(fn1)S(MFT(batch job schedule)(batch job schedule)問題要求確問題要求確定這定這n n個作業(yè)的最優(yōu)作業(yè)調(diào)度方案使其個作業(yè)的最優(yōu)作業(yè)調(diào)度方案使其MFTMFT最小。這最小。這等價于求使得所有作業(yè)的完成時間之和等價于求使得所有作業(yè)的完成時間之和最小的調(diào)度方案。最小的調(diào)度方案。 1n0ii)S(f)S(

24、FT 設(shè)有三個作業(yè)和兩臺設(shè)備，作業(yè)任務(wù)的處理時間為設(shè)有三個作業(yè)和兩臺設(shè)備，作業(yè)任務(wù)的處理時間為（a0,a1,a2）=(2,3,2)和（和（b0,b1,b2）=(1,1,3)。這三個作。這三個作業(yè)有業(yè)有6種可能的調(diào)度方案：種可能的調(diào)度方案：(0,1,2),(0,2,1),(1,0,2), (1,2,0),(2,0,1),(2,1,0),它們相應(yīng)的完成時間之和分別是它們相應(yīng)的完成時間之和分別是19,18,20,21,19,19。其中，最佳調(diào)度方案。其中，最佳調(diào)度方案S=(0,2,1)。在這一調(diào)度方案下，在這一調(diào)度方案下，f0(S)=3，f1(S)=7，f2(S)=8，F(xiàn)T=3+7+8=18。對于雙機(jī)批處理作業(yè)調(diào)度問題，其可行解是n個作業(yè)所有可能的排列，每一種排列代表一種作業(yè)調(diào)度方案S，其目標(biāo)函數(shù)是使FT