算法分析課件第08章

1、第第 八八 章章回回 溯溯8.1 一般方法一般方法8.2 8-皇后問題皇后問題入口入口8.1 一般方法一般方法什么是回溯什么是回溯回溯回溯迷宮游戲迷宮游戲什么是回溯法什么是回溯法回溯法是一種回溯法是一種搜索搜索算法算法通用通用的解題法的解題法回溯法是以回溯法是以深度優(yōu)先深度優(yōu)先的方式的方式系統(tǒng)地系統(tǒng)地搜索問題的搜索問題的解解, 它適用于解一些它適用于解一些組合數(shù)較大組合數(shù)較大的問題。的問題。尋求一組解，或求滿足某些約束條件的最優(yōu)解。尋求一組解，或求滿足某些約束條件的最優(yōu)解?；厮莼厮莩隹诔隹诨厮莼厮莼厮莼厮輕解的形式解的形式n-元組元組(x1,xn),其中其中xi取自某個有窮集取自某個有窮集Si

2、p規(guī)范函數(shù)規(guī)范函數(shù) P(x1,xn) p假設集合假設集合Si的大小是的大小是mi,滿足規(guī)范函數(shù)滿足規(guī)范函數(shù)P的可能的元的可能的元組數(shù)為組數(shù)為m=m1m2mnp硬性處理硬性處理:構(gòu)造構(gòu)造m個個n元組并依次測試是否滿足元組并依次測試是否滿足Pp回溯法回溯法 不斷地用修改過的限界函數(shù)不斷地用修改過的限界函數(shù)Pi(x1,xi)去測試正在去測試正在構(gòu)造的構(gòu)造的n元組的部分向量元組的部分向量, 看是否可能導致最優(yōu)解看是否可能導致最優(yōu)解, 如果不能如果不能, 就將可能要測試的就將可能要測試的mi+1 mn個向量略去。個向量略去。 回溯法的基本概念回溯法的基本概念回溯法的解需要滿足一組綜合的約束條件回溯法的解

3、需要滿足一組綜合的約束條件, 通常分通常分為為: 顯式約束和隱式約束顯式約束和隱式約束顯式約束條件顯式約束條件: 限定每個限定每個x只從一個給定的集合上取只從一個給定的集合上取值值, 滿足顯式約束的滿足顯式約束的所有元組所有元組確定一個可能的解空間確定一個可能的解空間 例例: xi 0 , si=所有非負實數(shù)所有非負實數(shù)隱式約束條件隱式約束條件: 描述了描述了xi必須彼此相關(guān)的情況必須彼此相關(guān)的情況 隱式約束條件指前面提到的規(guī)范函數(shù)隱式約束條件指前面提到的規(guī)范函數(shù)解空間中滿足隱式約束條件的元組稱為解空間中滿足隱式約束條件的元組稱為可行解可行解。 回溯法的基本概念回溯法的基本概念可能與問題實例有

4、可能與問題實例有關(guān)，也可能無關(guān)。關(guān)，也可能無關(guān)。與問題實例有關(guān)與問題實例有關(guān)p在一個在一個8*8棋盤上放棋盤上放8個皇后個皇后, 使每兩使每兩個皇后之間都不能互相個皇后之間都不能互相“攻擊攻擊”, 即：即：使得每兩個皇后都不能在使得每兩個皇后都不能在同一行、同一行、同一列及同一條斜角線上同一列及同一條斜角線上。p將皇后將皇后i放在行放在行i上，上，8皇后問題可以皇后問題可以表示為表示為8-元組元組(x1,x8)，其中，其中xi是皇是皇后后i被放置的列號。被放置的列號。p顯式約束條件顯式約束條件: Si=1, 2, 3, 4, 5, 6, 7, 8, 1i8p隱式約束條件隱式約束條件: 沒有兩個

5、沒有兩個xi可以相同可以相同, 且沒有兩個皇后可以在同一條斜角且沒有兩個皇后可以在同一條斜角線上線上。QQQQQQQQ解空間：解空間：88解空間：解空間：8！(4,6,8,2,7,1,3,5)例例8.1（8-皇后問題）皇后問題）例例8.2 子集和數(shù)問題子集和數(shù)問題p已知已知n+1個正數(shù)：個正數(shù)：wi, 1 i n, 和和M。要求找出要求找出wi 的的所有子集所有子集使得使得子集中元素之和等于子集中元素之和等于M。p例如：例如：n=4, (w1,w2,w3,w4)=(11,13,24,7)，M=31。 則滿足要求的子集是則滿足要求的子集是(11,13,7) 和和(24,7) 可表示為可表示為(1

6、,2,4) 和和 (3,4)子集和數(shù)問題的描述子集和數(shù)問題的描述p解是解是k-元組元組(x1,xk) ，1 k n p顯示約束條件顯示約束條件 xi j|j是整數(shù)是整數(shù),wj的下標且的下標且1 j np隱式約束條件隱式約束條件 xi互不相同互不相同且相應的且相應的wk的和數(shù)的和數(shù)是是M, k=xi，xi0) do if ( 還剩有沒檢驗的還剩有沒檢驗的X(k)使得使得X(k)T(X(1)X(k-1) and B(X(1)X(k)=TRUE ) then if (X(1) X(k)是一條抵達答案結(jié)點的路徑是一條抵達答案結(jié)點的路徑) then print ( X(1)X(k) ); endif k

7、k+1; else kk-1; endifrepeatend BACKTRACK/回溯回溯/打印數(shù)組打印數(shù)組X/考慮下一個集合考慮下一個集合在在X(1)X(k-1)已經(jīng)被確定已經(jīng)被確定的情況下的情況下, T(X(1)X(k-1)給出給出X(k)的所有可能的取值的所有可能的取值,限界函數(shù)限界函數(shù)B(X(1)X(k)判斷判斷哪些哪些X(k)滿足隱式約束條件滿足隱式約束條件131513211981416procedure BACKTRACK(n) int k, n local X(1: n) k 1 while (k0) do if (還剩有沒檢驗的還剩有沒檢驗的X(k) 使得使得X(k)T(X(1

8、)X(k-1) and B(X(1)X(k)=TRUE) then if (X(1) X(k)是一條是一條 抵達答案結(jié)點的路徑抵達答案結(jié)點的路徑) then print ( X(1)X(k) endif k k+1 else k k-1 endif repeatend BACKTRACKk=2k=3k=4若只需要一個解若只需要一個解,怎樣修改算法？怎樣修改算法？procedure RBACKTRACK(k)global X(1:n); int k, n;for ( 滿足下式的每個滿足下式的每個X(k), X(k) T(X(1)X(k-1) and B(X(1),B(k)=true) do if

9、 (X(1),X(k)是一條抵達答案結(jié)點的路徑是一條抵達答案結(jié)點的路徑 then print (X(1)X(k); call RBACKTRACK(k+1); end RBACKTRACK 回溯算法的遞歸描述回溯算法的遞歸描述進入算法時進入算法時, 解向量解向量X中的中的前前k-1個個分量分量X(1) X(k-1)已經(jīng)被賦值已經(jīng)被賦值對于所有可以由根結(jié)點對于所有可以由根結(jié)點到達到達, 并可能使限界函數(shù)并可能使限界函數(shù)B為真的結(jié)點為真的結(jié)點X(k), 判斷判斷(X(1)X(k)是否是一條是否是一條能抵達答案結(jié)點的路徑能抵達答案結(jié)點的路徑效率估計效率估計 回溯法的效率主要取決于四種因素回溯法的效率

10、主要取決于四種因素: 生成下一個生成下一個X(k)的時間的時間 滿足顯示約束條件的滿足顯示約束條件的X(k)的數(shù)目的數(shù)目 限界函數(shù)限界函數(shù)Bi的計算時間的計算時間 滿足滿足Bi的的X(k)的數(shù)目的數(shù)目 限界函數(shù)限界函數(shù)：減少結(jié)點數(shù)，本身的計算時間減少結(jié)點數(shù)，本身的計算時間生成節(jié)點的時間生成節(jié)點的時間子節(jié)點的數(shù)量子節(jié)點的數(shù)量檢驗節(jié)點的時間檢驗節(jié)點的時間通過檢驗的節(jié)點數(shù)量通過檢驗的節(jié)點數(shù)量在計算時間和減少節(jié)點數(shù)量上進行折中在計算時間和減少節(jié)點數(shù)量上進行折中p一旦選定了一種狀態(tài)空間樹結(jié)構(gòu)一旦選定了一種狀態(tài)空間樹結(jié)構(gòu), 前三種因素對于所前三種因素對于所要解決的實例沒有多大的關(guān)系要解決的實例沒有多大的關(guān)

11、系, 只有只有第四種因素第四種因素,對于對于問題的不同實例問題的不同實例, 生成的結(jié)點數(shù)是不相同的生成的結(jié)點數(shù)是不相同的。p易知，回溯算法最壞情況下的時間復雜度為易知，回溯算法最壞情況下的時間復雜度為O(p(n)2n)或或O(q(n)n!)，其中，其中p(n)和和q(n)為為n的多項式。的多項式。p由于回溯法對同一問題不同實例在計算時間上出現(xiàn)巨由于回溯法對同一問題不同實例在計算時間上出現(xiàn)巨大差異，大差異，在在n很大時，對某些實例仍然十分有效很大時，對某些實例仍然十分有效。p用回溯算法處理一棵樹所要生成的節(jié)點數(shù)，可以用用回溯算法處理一棵樹所要生成的節(jié)點數(shù)，可以用蒙蒙特卡羅方法特卡羅方法估算出來。

12、估算出來。效率估計效率估計效率估計效率估計-估計滿足估計滿足Bi的的X(k)的數(shù)目的數(shù)目p蒙特卡羅方法蒙特卡羅方法在狀態(tài)空間樹中生成一條在狀態(tài)空間樹中生成一條隨機路徑隨機路徑。設設X是這條路徑上是這條路徑上第第i級級的一個結(jié)點。的一個結(jié)點。在結(jié)點在結(jié)點X處處用限界函數(shù)確定用限界函數(shù)確定沒受限界的兒子結(jié)點沒受限界的兒子結(jié)點數(shù)目數(shù)目mi，在這，在這mi個兒子結(jié)點中個兒子結(jié)點中隨機選擇隨機選擇一個結(jié)點一個結(jié)點作為這條路徑上的下一個結(jié)點。作為這條路徑上的下一個結(jié)點。這條路徑在以下結(jié)點處結(jié)束：或者它是一個這條路徑在以下結(jié)點處結(jié)束：或者它是一個葉子葉子結(jié)點結(jié)點，或者該結(jié)點的，或者該結(jié)點的所有兒子結(jié)點都已被

13、限界所有兒子結(jié)點都已被限界。用這些用這些mi可以估算出這棵狀態(tài)空間樹中不受限界可以估算出這棵狀態(tài)空間樹中不受限界結(jié)點的總數(shù)結(jié)點的總數(shù)m。效率估計效率估計-估計滿足估計滿足Bi的的X(k)的數(shù)目的數(shù)目p蒙特卡羅方法蒙特卡羅方法優(yōu)點：優(yōu)點： 找到找到所有答案結(jié)點所有答案結(jié)點的情況非常有用，的情況非常有用， 限界函數(shù)固定不變限界函數(shù)固定不變，計算方便，對狀態(tài)空間樹中同一，計算方便，對狀態(tài)空間樹中同一級結(jié)點都適用。級結(jié)點都適用。缺點：缺點： 只求只求一個解一個解時，生成的結(jié)點數(shù)遠小于時，生成的結(jié)點數(shù)遠小于m， 隨著檢索的進行，限界函數(shù)應該更強，使得隨著檢索的進行，限界函數(shù)應該更強，使得m的值更的值更小

14、。小。 效率估計效率估計Procedure ESTIMATE /程序沿著狀態(tài)空間樹中一條隨機路徑產(chǎn)生這棵樹中不受限界結(jié)點的估計數(shù)程序沿著狀態(tài)空間樹中一條隨機路徑產(chǎn)生這棵樹中不受限界結(jié)點的估計數(shù)/ m 1; r 1; k 1 loop Tk X(k):X(k) T(X(1), ,X(k-1) ) and Bk (X(1), ,X(k-1) if SIZE(Tk)=0 then exit endif r r SIZE(Tk) m m+r X(k) CHOOSE(Tk) k k+1 repeat return(m)end ESTIMATE/第第k級的結(jié)點數(shù)級的結(jié)點數(shù)/從從Tk中隨機地挑選一個元素中隨

15、機地挑選一個元素/前第前第k級的結(jié)點總數(shù)級的結(jié)點總數(shù)返回集合返回集合Tk的大小的大小回溯法求解問題的基本步驟回溯法求解問題的基本步驟p 為所求問題定義解空間，使其包含所有為所求問題定義解空間，使其包含所有 解；解；p 確定適于搜索的解空間結(jié)構(gòu)；確定適于搜索的解空間結(jié)構(gòu)；p 用深度優(yōu)先方法搜索該解空間，在搜索用深度優(yōu)先方法搜索該解空間，在搜索 過程中利用限界函數(shù)避免無效搜索。過程中利用限界函數(shù)避免無效搜索。8.2 8-皇后問題皇后問題p問題描述及分析問題描述及分析p限界函數(shù)限界函數(shù)p求求n-皇后問題的所有解皇后問題的所有解p效率分析效率分析8.2 8-皇后問題皇后問題問題描述問題描述:在一個在一

16、個8*8棋盤上放置棋盤上放置8個皇后個皇后, 使得每兩個皇后之間使得每兩個皇后之間都不能互相都不能互相“攻擊攻擊”, 即每兩個皇后都不能在同一行、即每兩個皇后都不能在同一行、同一列及同一條斜角線上同一列及同一條斜角線上Q1Q2Q3Q4Q5Q6Q7Q88皇后問題可以表示皇后問題可以表示為為8- -元組元組(x1, , x8) ,其中其中xi是放置皇后是放置皇后i所所在的列號在的列號圖中的可行解表示為圖中的可行解表示為一個一個8- -元組元組即即(4, 6, 8, 2, 7, 1, 3, 5)a11a12a13a14a15a16a17a18a21a22a23a24a25a26a27a28a31a3

17、2a33a34a35a36a37a38a41a42a43a44a45a46a47a48a51a52a53a54a55a56a57a58a61A62a63a64a65a66a67a68a71a72a73a74a75a76a77a78a81a82a83a84a85a86a87a88用二維數(shù)組用二維數(shù)組A(1:8,1:8)的的下標來標記每個皇后的下標來標記每個皇后的位置，那么可以看到位置，那么可以看到: 對于在對于在由左到右由左到右的同一的同一條斜角線上的每個元素條斜角線上的每個元素具有具有相同的相同的“行行- -列列”值值;對于在對于在由右到左由右到左的同一的同一條斜角線上的每個元素條斜角線上的每

18、個元素則具有則具有相同的相同的“行行+列列”值值設有兩個皇后被放置在設有兩個皇后被放置在(i, j )和和(k, l )位置上位置上, 那么當且僅當那么當且僅當 i-j = k-l 或或 i+j = k+l 時時, 它們才在同一條斜角線上。它們才在同一條斜角線上。將這兩個等式分別變換成將這兩個等式分別變換成: j-l = i-k 或或 j-l = k-i因此當且僅當因此當且僅當 |j-l| = |i-k| 時時( 即兩個皇后所在位置的行差距即兩個皇后所在位置的行差距等于列差距時等于列差距時), 兩個皇后在同一條斜角線上兩個皇后在同一條斜角線上限界函數(shù)限界函數(shù)pPLACE(k)： 令令X(k)與

19、與X(i)逐個逐個比較，比較，i=1.k-1。 若存在若存在X(k)=X(i)或者或者|X(i)-X(k)|=|i-k| 則返回則返回false； 否則返回否則返回true。對對X(k)的限定的限定procedure PLACE(k)int i , k;i1;while ( i0) do X(k)X(k)+1; while ( X(k) n and Not PLACE(k) ) do X(k)X(k)+1; repeat if (X(k) n) then if (k=n) then print (X); else kk+1; X(k)0; endif else kk-1; endifrepea

20、tend NQUEENS/若是一個完整的解則打印數(shù)組若是一個完整的解則打印數(shù)組X/ k是當前行是當前行; X(k)是當前列是當前列 / 對所有的行執(zhí)行循環(huán)語句對所有的行執(zhí)行循環(huán)語句/移到下一列移到下一列當該位置不當該位置不能放皇后時能放皇后時轉(zhuǎn)到下一列轉(zhuǎn)到下一列/找到一個位置找到一個位置/否則轉(zhuǎn)到下一行否則轉(zhuǎn)到下一行/ 沒有合適的位置沒有合適的位置, 回溯回溯1234X001Q1PLACE(1)i=1;while ( ik ) do 10) do X(k)=X(k)+1; while (X(k) n and Not PLACE(k) do1 n and Not true , 循環(huán)不執(zhí)行循環(huán)不執(zhí)

21、行if (X(k) n) then if (kn) then 不執(zhí)行不執(zhí)行 else k=k+1=2; X(2)=0; end whilek=2; while (k0) do X(k)=X(k)+1; while ( X(k) n and Not PLACE(k) ) do1 n and Not false , X(k)=X(k)+1=2; 2 n and Not false , X(k)=X(k)+1=3; 3 n and Not true , 循環(huán)不執(zhí)行循環(huán)不執(zhí)行1 2 3if (X(k) n) then if (kn) then 不執(zhí)行不執(zhí)行 else k=k+1=3; X(3)=0;

22、0 end whileQ2PLACE(2)i=1;while ( ik ) do if (X(i)=X(k) then return (false);PLACE(2)i=1;while ( ik ) do if (|X(i)- -X(k)|=|i- -k|) then return (false);PLACE(2)i=1;while ( i0) do X(k)=X(k)+1; while (X(k) n and Not PLACE(k) doif (X(k) n) then 不執(zhí)行不執(zhí)行 else k=k- -1=2; /回溯回溯 end whilek=2; while (k0) do X(k

23、)=X(k)+1=3+1=4; while ( X(k) n and Not PLACE(k) ) do1 n and Not false , X(k)=X(k)+1=2; 2 n and Not false , X(k)=X(k)+1=3; 4 n and Not true , 循環(huán)不執(zhí)行循環(huán)不執(zhí)行if (X(k) n) then if (kn) then 不執(zhí)行不執(zhí)行 else k=k+1=3; X(3)=0; end whileQ213 n and Not false , X(k)=X(k)+1=4; 4 n and Not false , X(k)=X(k)+1=5; 2 3 4 54

24、05 n , 循環(huán)不執(zhí)行循環(huán)不執(zhí)行1234X140Q1Q2k=3; while (k0) do X(k)=X(k)+1; while (X(k) n and Not PLACE(k) doif (X(k)0) do X(k)=X(k)+1=1; while ( X(k) n and Not PLACE(k) ) do1 n and Not false , X(k)=X(k)+1=2; 2 n and Not true , 循環(huán)不執(zhí)行循環(huán)不執(zhí)行; end whileQ21 20Q31 n and Not false , X(k)=X(k)+1=2; 1 2 32 n and Not true ,

25、 X(k)=X(k)+1=3; 43 n and Not true , X(k)=X(k)+1=4; 54 n and Not true , X(k)=X(k)+1=5;5 n , 循環(huán)不執(zhí)行循環(huán)不執(zhí)行if (X(k) n) then 不執(zhí)行不執(zhí)行 else k=k- -1=3; /回溯回溯 1234X142Q1k=3; while (k0) do X(k)=X(k)+1; while (X(k) n and Not PLACE(k) doif (X(k) n) then 不執(zhí)行不執(zhí)行 else k=k- -1=2; /回溯回溯 end whilek=2; while (k0) do X(k)

26、=X(k)+1=4+1=5; while ( X(k) n and Not PLACE(k) ) do end whileQ23 n and Not false , X(k)=X(k)+1=4; 4 n and Not false , X(k)=X(k)+1=5; 3 4 55 n , 循環(huán)不執(zhí)行循環(huán)不執(zhí)行55 n , 循環(huán)不執(zhí)行循環(huán)不執(zhí)行if (X(k) n) then 不執(zhí)行不執(zhí)行 else k=k- -1=1; /回溯回溯 1234X1Q2k=1; while (k0) do X(k)=X(k)+1; while (X(k) n and Not PLACE(k) do end while

27、k=2; while (k0) do X(k)=X(k)+1; while ( X(k) n and Not PLACE(k) ) do2 n and Not true , 循環(huán)不執(zhí)行循環(huán)不執(zhí)行; 1 n and Not false , X(k)=X(k)+1;if (X(k) n) then if (kn) then 不執(zhí)行不執(zhí)行 else k=k+1=3; X(3)=0; end whileif (X(k) n) then if (kn) then 不執(zhí)行不執(zhí)行 else k=k+1=2; X(2)=0; 2 n and Not false , X(k)=X(k)+1;3 n and Not false , X(k)=X(k)+1;4 n and Not true , 循環(huán)不執(zhí)行循環(huán)不執(zhí)行;20Q1Q21 2 3 41234X240Q1Q2k