計(jì)算機(jī)算法設(shè)計(jì)與分析：第8章 回溯

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

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

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

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

5、同一條斜角且沒有兩個(gè)皇后可以在同一條斜角線上線上。QQQQQQQQ解空間：解空間：88解空間：解空間：8！(4,6,8,2,7,1,3,5)例例8.1（8-皇后問題）皇后問題）例例8.2 子集和數(shù)問題子集和數(shù)問題p已知已知n+1個(gè)正數(shù)：個(gè)正數(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,2,4) 和和 (3,4)子集和數(shù)問題的描述子集和

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

7、tend BACKTRACK/回溯回溯/打印數(shù)組打印數(shù)組X/考慮下一個(gè)集合考慮下一個(gè)集合在在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 (還剩有沒檢驗(yàn)的還剩有沒檢驗(yàn)的X(k) 使得使得X(k)T(X(1)X(k-1) and B(X(1)X(k)=TRU

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

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

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

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

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

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

14、MATE /程序沿著狀態(tài)空間樹中一條隨機(jī)路徑產(chǎn)生這棵樹中不受限界結(jié)點(diǎn)的估計(jì)數(shù)程序沿著狀態(tài)空間樹中一條隨機(jī)路徑產(chǎn)生這棵樹中不受限界結(jié)點(diǎn)的估計(jì)數(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級(jí)的結(jié)點(diǎn)數(shù)級(jí)的結(jié)點(diǎn)數(shù)/從從Tk中隨機(jī)地挑選一個(gè)元素中隨機(jī)地挑選一個(gè)元素/前第前第k級(jí)的結(jié)點(diǎn)總數(shù)級(jí)的結(jié)點(diǎn)總數(shù)

15、返回集合返回集合Tk的大小的大小回溯法求解問題的基本步驟回溯法求解問題的基本步驟p 為所求問題定義解空間，使其包含所有為所求問題定義解空間，使其包含所有 解；解；p 確定適于搜索的解空間結(jié)構(gòu)；確定適于搜索的解空間結(jié)構(gòu)；p 用深度優(yōu)先方法搜索該解空間，在搜索用深度優(yōu)先方法搜索該解空間，在搜索 過程中利用限界函數(shù)避免無效搜索。過程中利用限界函數(shù)避免無效搜索。8.2 8-皇后問題皇后問題問題描述問題描述:在一個(gè)在一個(gè)8*8棋盤上放置棋盤上放置8個(gè)皇后個(gè)皇后, 使得每兩個(gè)皇后之間使得每兩個(gè)皇后之間都不能互相都不能互相“攻擊攻擊”, 即每兩個(gè)皇后都不能在同一行、即每兩個(gè)皇后都不能在同一行、同一列及同一條

16、斜角線上同一列及同一條斜角線上Q1Q2Q3Q4Q5Q6Q7Q88皇后問題可以表示皇后問題可以表示為為8- -元組元組(x1, , x8) ,其中其中xi是放置皇后是放置皇后i所所在的列號(hào)在的列號(hào)圖中的可行解表示為圖中的可行解表示為一個(gè)一個(gè)8- -元組元組即即(4, 6, 8, 2, 7, 1, 3, 5)a11a12a13a14a15a16a17a18a21a22a23a24a25a26a27a28a31a32a33a34a35a36a37a38a41a42a43a44a45a46a47a48a51a52a53a54a55a56a57a58a61A62a63a64a65a66a67a68a71

17、a72a73a74a75a76a77a78a81a82a83a84a85a86a87a88用二維數(shù)組用二維數(shù)組A(1:8,1:8)的的下標(biāo)來標(biāo)記每個(gè)皇后的下標(biāo)來標(biāo)記每個(gè)皇后的位置，那么可以看到位置，那么可以看到: 對(duì)于在對(duì)于在由左到右由左到右的同一的同一條斜角線上的每個(gè)元素條斜角線上的每個(gè)元素具有具有相同的相同的“行行- -列列”值值;對(duì)于在對(duì)于在由右到左由右到左的同一的同一條斜角線上的每個(gè)元素條斜角線上的每個(gè)元素則具有則具有相同的相同的“行行+列列”值值設(shè)有兩個(gè)皇后被放置在設(shè)有兩個(gè)皇后被放置在(i, j )和和(k, l )位置上位置上, 那么當(dāng)且僅當(dāng)那么當(dāng)且僅當(dāng) i-j = k-l 或或

18、i+j = k+l 時(shí)時(shí), 它們才在同一條斜角線上。它們才在同一條斜角線上。將這兩個(gè)等式分別變換成將這兩個(gè)等式分別變換成: j-l = i-k 或或 j-l = k-i因此當(dāng)且僅當(dāng)因此當(dāng)且僅當(dāng) |j-l| = |i-k| 時(shí)時(shí)( 即兩個(gè)皇后所在位置的行差距即兩個(gè)皇后所在位置的行差距等于列差距時(shí)等于列差距時(shí)), 兩個(gè)皇后在同一條斜角線上兩個(gè)皇后在同一條斜角線上限界函數(shù)限界函數(shù)pPLACE(k)： 令令X(k)與與X(i)逐個(gè)逐個(gè)比較，比較，i=1.k-1。 若存在若存在X(k)=X(i)或者或者|X(i)-X(k)|=|i-k| 則返回則返回false； 否則返回否則返回true。對(duì)對(duì)X(k)的

19、限定的限定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; endifrepeatend NQUEENS/若是一個(gè)完整的解則打印數(shù)組若是一個(gè)完整的解則打印數(shù)組X/ k是當(dāng)前行是當(dāng)前行; X(k)是當(dāng)前列是當(dāng)前列 / 對(duì)所有的行執(zhí)行循環(huán)語句對(duì)所有的行執(zhí)行循環(huán)語句/移到下

20、一列移到下一列當(dāng)該位置不當(dāng)該位置不能放皇后時(shí)能放皇后時(shí)轉(zhuǎn)到下一列轉(zhuǎn)到下一列/找到一個(gè)位置找到一個(gè)位置/否則轉(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í)行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

21、(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; 0 end whileQ2PLACE(2)i=1;while ( ik ) do if (X(i)=X(k) then return (false);PLACE(2)i=1;while (

22、 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)=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

23、 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 5405 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) do

24、if (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 , 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)不

25、執(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)=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

26、=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 whilek=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=3; while