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

2、3著色問題，8皇后問題，一般回溯方法，剪枝。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.前言：在許多問題中，當(dāng)需要找出它的解集或者要求回答什么解是滿足某些約束條件的最佳解時，往往是要使用回溯法，回溯法的基本做法是搜索，或是一種組織的井井有條的，能避免不必要搜索的窮舉式搜索法，這種方法適用于解一些組合數(shù)相當(dāng)大的問題。對于回溯法，其中最經(jīng)典的幾個問題就是著色問題和八皇后問題，這篇文章主要以講解3著色問題和八皇后問題來幫助理解回溯法。回溯法主要是按照深度優(yōu)先的策略，在搜索過程中通過一些基本的剪枝方法可以提高算法的效率。在這篇文章當(dāng)中也會介紹一些基本的剪枝方

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

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

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

9、算法，一種是遞歸的，另一種是迭代的。在兩種算法中，為了簡單起見，都假定頂點(diǎn)集合為1，2，n，遞歸算法見算法3- COLORREC。算法3-COLORREC 輸入：無向圖G=(V，E)。 輸出：G的頂點(diǎn)的3著色cln，其中每個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”過程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 初始時沒有頂點(diǎn)被著色，這由第l步中置所有顏色值為O指示。調(diào)用graphcolor(1)使得第一個頂點(diǎn)著色為l，很明顯，(1)是部分著色，因此就以k=2遞歸調(diào)用過程，賦值語句使得第二個頂點(diǎn)也用l著色，得到的著色是(1，1)。如果頂點(diǎn)l和2沒有邊連接，那么這個著色就是部分的，否則，著色不是部分的，并且因此第二個頂點(diǎn)將用2來著色，得到的著色是(1,2)。第二個頂點(diǎn)著色之后，也就是說，如果當(dāng)前的著色是部分的

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

12、。 迭代回溯算法在算法3-COLOITER中給出。這個算法的主要部分由兩個嵌套的while循環(huán)組成，內(nèi)層的while循環(huán)實(shí)現(xiàn)前進(jìn)(生成新節(jié)點(diǎn))，而外層的while循環(huán)實(shí)現(xiàn)回溯的過程(即回到先前生成的節(jié)點(diǎn))，這個算法的運(yùn)作與前面遞歸形式的算法相似。算法2：輸入：無向圖 G=(V,E)。輸出：G的頂點(diǎn)的3著色c1n，其中每個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 且從兩個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”對于這兩種算法的時間復(fù)雜性，我們注意到在最壞情況下生成了0(3n)個節(jié)點(diǎn)。對于每個生成的節(jié)點(diǎn)，如果當(dāng)前著色是合法的、部分的，或者二者都不是，這需要O(n)的工作來檢查。因此，在最壞情況下

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

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

16、i=xj時處在同一列上，不難看出兩個皇后處在同一條對角線上當(dāng)且僅當(dāng)xi xj=i一j或xi xj=j-i。 算法13.3 4-QUEENS輸入：空。輸出：對應(yīng)于4皇后問題的解的向量cl4。 1For k ß 1 to 4 2 ck ß 0 沒有皇后放置在棋盤上 3end for 4Flag ß false 5. k ß 1 6While k>= 1 7while ck3 8 ck ß ck+l 9 If c為合法著色then set flag ß true且從兩個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)在考慮一個求解一般的n皇后問題的蠻力方法。如前所述，由于沒有兩個皇后能放在同一列上則解向量必須是數(shù)1，2,n的一個排列。這樣，蠻力方法可以改進(jìn)為測n!種布局而不是nn種。然而，下面的論據(jù)說明回溯法極大地減少了測試的次數(shù)。考慮(n-2)!個向量，它們對應(yīng)于前兩個皇后放在第一列的那些布局，蠻力方法要盲目地測試所有這些向量而在回溯法中用O(1)次測試

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

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

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

21、1中的下一個元素 2、（回溯步驟）。如果從集合Xj+1 中沒有更多的元素可選擇，算法通過將xj置為Xj中的下一個元素回溯；如果從集合Xj中任然沒有其他的元素可選擇，算法通過將xj-1置為Xj-1中的下一個元素回溯，以此類推。遞歸描述回溯算法：輸入：集合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”過程Advance(k)1. For每個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沒有被窮舉6. xk ß Xk 中的下一個元素，將xk 加入v7. If v 為最終解th

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

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

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