1、算法設(shè)計(jì)課程論文 題 目： 回 溯 法 班級(jí): 10計(jì)算機(jī)科學(xué)與技術(shù) 姓 名: 鄭云紅 日 期: 2012年5月20日星期日 回 溯 法鄭云紅(溫州大學(xué)物理與電子信息工程學(xué)院，10計(jì)算機(jī)科學(xué)與技術(shù))摘要：在許多真實(shí)世界的問(wèn)題中，像大多數(shù)NP難題一樣，通過(guò)徹底的搜索有有限多個(gè)可能性的一個(gè)很大得數(shù)可以得到一個(gè)解決方案。而且，實(shí)際上所有的這些問(wèn)題都不存在除窮盡搜索法之外的解決這些問(wèn)題的算法。因此，產(chǎn)生了開(kāi)發(fā)系統(tǒng)式的搜索技術(shù)的需要，希望把搜索空間減到盡可能的小?；厮莘梢员幻枋鰹橐粋€(gè)有組織的窮盡搜索，他常?？赡鼙苊馑阉魉械目赡苄?，它一般適合解決那些數(shù)據(jù)量比較大，但是有有限個(gè)解的問(wèn)題。關(guān)鍵詞：回溯法，

2、3著色問(wèn)題，8皇后問(wèn)題，一般回溯方法，剪枝。BacktrackingZheng Yun Hong(School of computer science and engineering, WenZhou University)( 10 Computer Science and Technology)Abstract: In many real world problems, as in most of the NP-hard problems, a solution can be obtained by exhaustively searching through a large but fin

3、ite number of possibilities. Moreover, for virtually all there problems, there does not exit an algorithm that uses a methods other than exhaustive search. Hence, the need arose for developing systematic techniques of searching, with the hope of cutting down the search space to possibility a much sm

4、aller space. Backtracking is described as an organized exhaustive search which often avoids searching all possibilities. It is generally suitable for solving problems where a potentially large but finite number of solutions have to be inspected.Keywords: backtracking, the 3-Coloring problem, the 8-Q

5、ueens problem, the general backtracking problem, Branch and Bound.前言：在許多問(wèn)題中，當(dāng)需要找出它的解集或者要求回答什么解是滿足某些約束條件的最佳解時(shí)，往往是要使用回溯法，回溯法的基本做法是搜索，或是一種組織的井井有條的，能避免不必要搜索的窮舉式搜索法，這種方法適用于解一些組合數(shù)相當(dāng)大的問(wèn)題。對(duì)于回溯法，其中最經(jīng)典的幾個(gè)問(wèn)題就是著色問(wèn)題和八皇后問(wèn)題，這篇文章主要以講解3著色問(wèn)題和八皇后問(wèn)題來(lái)幫助理解回溯法?；厮莘ㄖ饕前凑丈疃葍?yōu)先的策略，在搜索過(guò)程中通過(guò)一些基本的剪枝方法可以提高算法的效率。在這篇文章當(dāng)中也會(huì)介紹一些基本的剪枝方

6、法。一、3著色問(wèn)題：3著色問(wèn)題描述：給出一個(gè)無(wú)向圖G=(V,E)，需要用三種顏色之一為V中的每一個(gè)頂點(diǎn)著色，三種顏色分別是1,2,3，使得鄰接的兩個(gè)點(diǎn)的顏色不同，我們把這樣的著色成為是合法的。否則，就是非法的，一種著色可以用n元組（c1 , c2 , cn）來(lái)表示，使ci1,2,3,1<=i<=n.例如，（1,2,2,3,1）表示一個(gè)有5個(gè)頂點(diǎn)的圖的著色。一個(gè)n個(gè)頂點(diǎn)的圖共有3n種可能的著色（合法的和非法的），所有可能的著色的集合可以用一顆完全的三叉樹(shù)來(lái)表示，成為搜索樹(shù)。在這棵樹(shù)中，從根到葉節(jié)點(diǎn)的每一條路徑代表一種著色指派。圖1顯示了有三個(gè)頂點(diǎn)的這樣的一棵樹(shù)。 圖1，如果沒(méi)有兩個(gè)鄰

7、接點(diǎn)的顏色相同，圖的一個(gè)不完全著色部分稱為部分解?；厮莘ㄍㄟ^(guò)每次一個(gè)節(jié)點(diǎn)地生成基底樹(shù)來(lái)工作。如果從根到當(dāng)前節(jié)點(diǎn)的路徑對(duì)應(yīng)于一個(gè)合法的著色，過(guò)程就終止（除非想找到不止一種的著色）。如果這條路徑的長(zhǎng)度小于n，并且相應(yīng)的著色是部分的，那么就生成現(xiàn)結(jié)點(diǎn)的一個(gè)子節(jié)點(diǎn)，并將它標(biāo)記為現(xiàn)結(jié)點(diǎn)。另一方面，如果對(duì)應(yīng)的路徑不是部分的，那么現(xiàn)結(jié)點(diǎn)標(biāo)示為四節(jié)點(diǎn)并生成對(duì)應(yīng)于另一種顏色的新節(jié)點(diǎn)。如果所有三種顏色都已經(jīng)試過(guò)且沒(méi)有成功，搜索就回到父節(jié)點(diǎn)，它的顏色被改變，以此類推。例如：考慮圖a中所示的圖，我們用顏色1,2,3對(duì)其頂點(diǎn)著色，圖b所示的是在搜索一個(gè)合法的著色的過(guò)程中生成的搜索樹(shù)的一部分。首先，在生成第三個(gè)節(jié)點(diǎn)之后，

8、發(fā)現(xiàn)著色（1,1）不是部分的，因此這個(gè)節(jié)點(diǎn)被標(biāo)記為死節(jié)點(diǎn)，在圖中用x表示。然后，b被指派為顏色2，并可以看到著色（1,2）是部分的，因此，生成對(duì)應(yīng)于頂點(diǎn)c的一個(gè)新的子節(jié)點(diǎn)，賦予初始顏色值1，重復(fù)上述過(guò)程，忽略死節(jié)點(diǎn)和拓展那些相應(yīng)的部分著色，我們最終到達(dá)合法的著色（1,2,2,1,3）。在圖中注意兩個(gè)重要的觀察結(jié)論，它們概括出所有回溯算法的基本特征。首先，節(jié)點(diǎn)是用深度優(yōu)先搜索的方法生成的；第二，不需要存儲(chǔ)整棵搜索樹(shù)，我們只需要存儲(chǔ)根到當(dāng)前活動(dòng)節(jié)點(diǎn)的路徑。事實(shí)上，根本沒(méi)有生成有形的節(jié)點(diǎn)，整棵樹(shù)是隱含的。在上面的例子中，我們只需要保存顏色指派的蹤跡就可以了。算法：現(xiàn)在給出用回溯法求解3著色問(wèn)題的兩種

9、算法，一種是遞歸的，另一種是迭代的。在兩種算法中，為了簡(jiǎn)單起見(jiàn)，都假定頂點(diǎn)集合為1，2，n，遞歸算法見(jiàn)算法3- COLORREC。算法3-COLORREC 輸入：無(wú)向圖G=(V，E)。 輸出：G的頂點(diǎn)的3著色cln，其中每個(gè)cj為1，2或3。 1For k ß 1 to n 2 ck ß O 3end for 4Flag ß false 5. Graphcolor (1) 6If flag then output c7.else output “no solution”過(guò)程graphcolor(k) l for color= 1 to 3 2.ck ß

10、color 3 .if c為合法著色 then set flag ß true and exit 4.Else if c是部分的then graplwolor(k+1) 5end for 初始時(shí)沒(méi)有頂點(diǎn)被著色，這由第l步中置所有顏色值為O指示。調(diào)用graphcolor(1)使得第一個(gè)頂點(diǎn)著色為l，很明顯，(1)是部分著色，因此就以k=2遞歸調(diào)用過(guò)程，賦值語(yǔ)句使得第二個(gè)頂點(diǎn)也用l著色，得到的著色是(1，1)。如果頂點(diǎn)l和2沒(méi)有邊連接，那么這個(gè)著色就是部分的，否則，著色不是部分的，并且因此第二個(gè)頂點(diǎn)將用2來(lái)著色，得到的著色是(1,2)。第二個(gè)頂點(diǎn)著色之后，也就是說(shuō)，如果當(dāng)前的著色是部分的

11、，就用：3繼續(xù)調(diào)用過(guò)程。依次類推。假定過(guò)程對(duì)于某個(gè)頂點(diǎn)，j>=3著色失敗，這種情況在for循環(huán)執(zhí)行三次而沒(méi)有找到合法的或部分著色時(shí)將發(fā)生。在這種情況下，前一次遞歸調(diào)用被激活，并嘗試將頂點(diǎn)j-1置為另一種顏色如果再一次出現(xiàn)三種顏色都沒(méi)能導(dǎo)致一個(gè)部分著色的情況，那么最后遞歸調(diào)用的前一個(gè)被激活。這就是發(fā)生回溯的情況。前進(jìn)與回溯的過(guò)程進(jìn)行直到圖或者著色，或者所有可能性都已經(jīng)試過(guò)卻找不到合法著色時(shí)才結(jié)束。檢查著色是否是部分的可以遞進(jìn)地完成：如果著色向量c包含m個(gè)非0數(shù)，而且對(duì)于任何其他的顏色cm沒(méi)有引起沖突，則它是部分的；否則它不是部分的。檢查著色是否合法就是檢查顏色向量是否由無(wú)矛盾的n種顏色組成

12、。 迭代回溯算法在算法3-COLOITER中給出。這個(gè)算法的主要部分由兩個(gè)嵌套的while循環(huán)組成，內(nèi)層的while循環(huán)實(shí)現(xiàn)前進(jìn)(生成新節(jié)點(diǎn))，而外層的while循環(huán)實(shí)現(xiàn)回溯的過(guò)程(即回到先前生成的節(jié)點(diǎn))，這個(gè)算法的運(yùn)作與前面遞歸形式的算法相似。算法2：輸入：無(wú)向圖 G=(V,E)。輸出：G的頂點(diǎn)的3著色c1n，其中每個(gè)cj為1,2,3。1. for k ß 1 to n2. ck ß 03. end for4. flag ß false5. k ß 16. while k>=17. while ck <= 28. Ck ß ck

13、+ 19. If c 為合法著色 then set flag ß true 且從兩個(gè)while循環(huán)退出10. else if c 是部分解then k ß k+1 前進(jìn)11. End while12. Ck ß 013. K ß k-1回溯14. End while15. If flag then output c16. Else output “no solution”對(duì)于這兩種算法的時(shí)間復(fù)雜性，我們注意到在最壞情況下生成了0(3n)個(gè)節(jié)點(diǎn)。對(duì)于每個(gè)生成的節(jié)點(diǎn)，如果當(dāng)前著色是合法的、部分的，或者二者都不是，這需要O(n)的工作來(lái)檢查。因此，在最壞情況下

14、，全部的運(yùn)行時(shí)間是O( n3n)。 二、8皇后問(wèn)題 經(jīng)典的8皇后問(wèn)題可以陳述如下：如何在8x8的國(guó)際象棋棋盤(pán)上安排8個(gè)皇后，使得沒(méi)有兩個(gè)皇后能互相攻擊？如果兩個(gè)皇后處在同一行、同一列或同一條對(duì)角線上，則她們能互相攻擊。凡皇后問(wèn)題類似地定義。在這樣的情況下，有n個(gè)皇后和一個(gè)n*n的棋盤(pán)，n為任意值且n1。為了簡(jiǎn)化討論，我們將研究4皇后問(wèn)題，而且可以簡(jiǎn)單而直接地將其推廣到n為任意值的情況。 考慮一個(gè)4*4的棋盤(pán)，由于沒(méi)有兩個(gè)皇后能處在同一行，所以每個(gè)皇后都在不同的行上。又因?yàn)槊啃杏?個(gè)位置，就有44種可能的布局，每種可能的布局可以用一個(gè)有4個(gè)分量的向量x= xl，X2，X3，X4來(lái)描述。例如，向量

15、(2，3，4，1)對(duì)應(yīng)于圖a中所示的布局。如果在某行上沒(méi)有皇后，則相應(yīng)的分量為O（因此并不明確地包括在向量中）。例如，部分向量(3，1)對(duì)應(yīng)于圖b中的布局。 算法 為了用回溯法求解8皇后問(wèn)題，算法嘗試生成并以深度優(yōu)先方式搜索一棵完全四叉有根樹(shù)，樹(shù)的根對(duì)應(yīng)于沒(méi)有放置皇后的情況。第一層的節(jié)點(diǎn)對(duì)應(yīng)于皇后在第一行的可能放置情況，第二層的節(jié)點(diǎn)對(duì)應(yīng)于皇后在第二行的可能放置情況，依次類推。求解這個(gè)問(wèn)題的回溯算法如算法4- QUEENS給出。在算法中，我們用術(shù)語(yǔ)“合法”來(lái)表示一個(gè)不互相攻擊的4個(gè)皇后的放置，用術(shù)語(yǔ)“部分”來(lái)表示一個(gè)不互相攻擊的少于4個(gè)皇后的放置。顯而易見(jiàn)，放在位置xi和xj的兩個(gè)皇后當(dāng)且僅當(dāng)x

16、i=xj時(shí)處在同一列上，不難看出兩個(gè)皇后處在同一條對(duì)角線上當(dāng)且僅當(dāng)xi xj=i一j或xi xj=j-i。 算法13.3 4-QUEENS輸入：空。輸出：對(duì)應(yīng)于4皇后問(wèn)題的解的向量cl4。 1For k ß 1 to 4 2 ck ß 0 沒(méi)有皇后放置在棋盤(pán)上 3end for 4Flag ß false 5. k ß 1 6While k>= 1 7while ck3 8 ck ß ck+l 9 If c為合法著色then set flag ß true且從兩個(gè)while循環(huán)退出 10. else if c是部分解then k

17、 ß k+l 前進(jìn) 11end while 12. ck ß 0 13. k ß k-l回溯 14end while 15If flag then output c16. else output “no solution”現(xiàn)在考慮一個(gè)求解一般的n皇后問(wèn)題的蠻力方法。如前所述，由于沒(méi)有兩個(gè)皇后能放在同一列上則解向量必須是數(shù)1，2,n的一個(gè)排列。這樣，蠻力方法可以改進(jìn)為測(cè)n!種布局而不是nn種。然而，下面的論據(jù)說(shuō)明回溯法極大地減少了測(cè)試的次數(shù)?？紤](n-2)!個(gè)向量，它們對(duì)應(yīng)于前兩個(gè)皇后放在第一列的那些布局，蠻力方法要盲目地測(cè)試所有這些向量而在回溯法中用O(1)次測(cè)試

18、就可以避免這些測(cè)試。盡管回溯法在最壞情況下要用O(nn)時(shí)間來(lái)求解n皇后問(wèn)題，根據(jù)經(jīng)驗(yàn)它在有效性上遠(yuǎn)遠(yuǎn)超過(guò)蠻力方法的O(n!)時(shí)間，作為它的可期望運(yùn)行時(shí)間通常要快得多。三、一般的回溯法一般的回溯方法可以作為一種系統(tǒng)的搜索方法應(yīng)用到一類搜索問(wèn)題當(dāng)中，這類問(wèn)題的解由滿足事先定義好的某個(gè)約束的向量（x1,x2,.,xi）組成。這里i是0到n之間的某個(gè)整數(shù)，其中n是一個(gè)取決于問(wèn)題闡述的常量。在已經(jīng)提到的兩種算法3著色算法和8皇后問(wèn)題當(dāng)中，i是固定不變的。然而在一些問(wèn)題中，i可以像下面的例子展開(kāi)的那樣，對(duì)于不同的解可能有所不同?？紤]如下定義的PARTTION問(wèn)題中的一個(gè)變形，給定一個(gè)n個(gè)整數(shù)集合X=x1

19、,x2xn和整數(shù)y，找出和等于y的X的子集Y。比如說(shuō)，如果X=10,20,30,40,50,60，和y=60，則有三種不同長(zhǎng)度的解，他們分別是10,20,30，20，40，60，設(shè)計(jì)出一個(gè)求解這個(gè)問(wèn)題的回溯算法并不難，注意這個(gè)問(wèn)題可以用另一種方法明確表達(dá)，使得解是一種明顯長(zhǎng)度為n的布爾向量，于是上面的三個(gè)解可以用布爾向量表示為1,1,1,0,0,0，0,1,0,1，0，0和0,0,0,0，0,1在回溯法中，解向量中每個(gè)xi都屬于一個(gè)有限的線序集Xi,因此，回溯算法按詞典序考察笛卡爾積X1* X2* * Xn中的元素。算法最初從空間向量開(kāi)始，然后選擇X 1中最小的元素作為x1，如果（x1）是一個(gè)

20、部分解，算法通過(guò)從X2中選擇最小的元素作為x2繼續(xù)，如果（x1，x2）是一個(gè)部分解，那么就包括X3中最小的元素，否則x2被置為X2中的下一個(gè)元素。一般的，假定算法已經(jīng)檢測(cè)到部分解為（x1，x2，xj），它然后再去考慮向量v=（x1，x2，xj，xj+1）,我們有下面的情況。(1) 如果v表示問(wèn)題的最后解，算法記錄下它作為一個(gè)解，在僅希望獲得一個(gè)解時(shí)終止，或者繼續(xù)去找出其他解。(2) (向前步驟)。如果v表示一個(gè)部分解，算法通過(guò)選擇集合X j+2中的最小元素向前。(3) 如果v既不是最終解，也不是部分解，則有兩種子情況 1、如果從集合Xj+1中還有其他的元素可選擇，算法將x j+1 置為X j+

21、1中的下一個(gè)元素 2、（回溯步驟）。如果從集合Xj+1 中沒(méi)有更多的元素可選擇，算法通過(guò)將xj置為Xj中的下一個(gè)元素回溯；如果從集合Xj中任然沒(méi)有其他的元素可選擇，算法通過(guò)將xj-1置為Xj-1中的下一個(gè)元素回溯，以此類推。遞歸描述回溯算法：輸入：集合X1，X2，Xn的清楚和隱含描述。輸出：解向量v=（x1，x2，xi），0<=i<=n。1. V ß ()2. Flag ß false3. Advance(1)4. If flag then outout v5. Else output “no solution”過(guò)程Advance(k)1. For每個(gè)xXk2.

22、 xk ß x;將xk加入v3. If v 為最終解 then set flag ß true and exit4. Else if v 是部分解then Advance(k+1)5. End for迭代法描述回溯算法輸入：集合X1，X2，Xn的清楚和隱含描述。輸出：解向量v=（x1，x2，xi），0<=i<=n。1. V ß ()2. Flag ß false3. K ß 14. While k >= 15. While Xk沒(méi)有被窮舉6. xk ß Xk 中的下一個(gè)元素，將xk 加入v7. If v 為最終解th

23、en set flag ß true , 且從兩個(gè)while循環(huán)退出8. Else if v是部分解 then k ß k+1 前進(jìn)9. End while10. 重置 Xk 使得下一個(gè)元素排在第一位11. k ß k-1 回溯12. End while13. If flag then output v14. Else output “no solution”四、資料與課本進(jìn)行比較 相同點(diǎn)：對(duì)于回溯法，都提及到了有關(guān)解空間樹(shù)的概念；都用到了著色問(wèn)題和8皇后問(wèn)題這兩個(gè)經(jīng)典的回溯算法的例子；都通過(guò)迭代法和遞歸兩種方法來(lái)描述回溯法。不同點(diǎn)：書(shū)本上所舉的例子很多，更有助于

24、更深層次的理解回溯法，對(duì)于每一種實(shí)現(xiàn)方法，書(shū)本上對(duì)其復(fù)雜度及其算法效率都進(jìn)行了分析，而該資料在這方面做的比較少。而且對(duì)于一些概念上的問(wèn)題，書(shū)上講得比資料上要詳細(xì)，對(duì)于解空間樹(shù)，書(shū)上講得比較全面和清楚。而對(duì)于所舉的例子，著色問(wèn)題和8皇后問(wèn)題。對(duì)于著色問(wèn)題，對(duì)于資料上所述的僅僅只是m著色問(wèn)題的一個(gè)特例3著色問(wèn)題，而課本上則是比較有拓展性的展開(kāi)了m著色問(wèn)題。相對(duì)于課本上，單單介紹3著色問(wèn)題更有助于對(duì)算法的理解，但是拓展性不強(qiáng)，在對(duì)算法的復(fù)雜度分析上，課本上說(shuō)的相對(duì)較為詳細(xì)，對(duì)于m著色問(wèn)題，其算法的復(fù)雜度為：O(nmn)，在算法分析上，課本上給的代碼較多，但是比較詳細(xì)，資料上給的代碼少，但是綜合兩種方

25、式來(lái)說(shuō)，都方便理解回溯法，兩種描述方法各有千秋。課本上綜合m著色問(wèn)題，詳細(xì)分析了著色問(wèn)題的過(guò)程，比較豐富。對(duì)于8皇后問(wèn)題，資料上通過(guò)簡(jiǎn)單的介紹8皇后問(wèn)題，然后引出n后問(wèn)題，而且僅僅簡(jiǎn)單的介紹了一下n后問(wèn)題，對(duì)于很多回溯法的問(wèn)題都沒(méi)有進(jìn)行描述，比如說(shuō)用什么解空間樹(shù)解決問(wèn)題，怎么樣對(duì)在搜索過(guò)程中，對(duì)于不滿足行，列和斜線約束的子樹(shù)進(jìn)行剪枝，但是課本上描述得很清楚；對(duì)于n后問(wèn)題，通過(guò)迭代回溯方法比通過(guò)遞歸回溯方法效率要高，但是在資料中并沒(méi)有闡述迭代回溯解決n后問(wèn)題，但是在教材中對(duì)其進(jìn)行了詳細(xì)的描述。綜合教材和資料，總體上來(lái)說(shuō)資料上講得比較淺，但是比較容易理解，教材上內(nèi)容比較全面，案例多，拓展性強(qiáng)。五、自己對(duì)回溯法的理解與看法在我們所遇到的很多問(wèn)題當(dāng)中，我們既不能通過(guò)數(shù)學(xué)模型解決，也沒(méi)有現(xiàn)成的算法可以用，或許必須通過(guò)遍歷所有情況才能找出正確的結(jié)果，比如說(shuō)迷宮問(wèn)題，推箱子問(wèn)題，紅與黑問(wèn)題，連連看問(wèn)題等都要通過(guò)搜索才能找出結(jié)果，在搜索問(wèn)題當(dāng)中，主要分為深度優(yōu)先和廣度優(yōu)先兩種，在大多數(shù)深度優(yōu)先搜索當(dāng)中，都要用到遞歸與回溯的思想，運(yùn)用回溯，主要是在搜索過(guò)程當(dāng)中，當(dāng)前點(diǎn)沒(méi)有搜索過(guò)，走到當(dāng)前點(diǎn)，發(fā)現(xiàn)當(dāng)前點(diǎn)不合法，回到上一個(gè)點(diǎn)，另尋一條可行的路，當(dāng)找不到可行解時(shí)繼續(xù)向上回溯，依次類推，直到找到出口。對(duì)于回溯法，在搜索過(guò)程中比較常用，雖然對(duì)其進(jìn)行了很多的優(yōu)化，但是其效率還是比較低，搜索