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

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

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

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

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

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

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

12、。 迭代回溯算法在算法3-COLOITER中給出。這個算法的主要部分由兩個嵌套的while循環組成，內層的while循環實現前進(生成新節點)，而外層的while循環實現回溯的過程(即回到先前生成的節點)，這個算法的運作與前面遞歸形式的算法相似。算法2：輸入：無向圖 G=(V,E)。輸出：G的頂點的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循環退出10. else if c 是部分解then k ß k+1 前進11. End while12. Ck ß 013. K ß k-1回溯14. End while15. If flag then output c16. Else output “no solution”對于這兩種算法的時間復雜性，我們注意到在最壞情況下生成了0(3n)個節點。對于每個生成的節點，如果當前著色是合法的、部分的，或者二者都不是，這需要O(n)的工作來檢查。因此，在最壞情況下

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

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

16、i=xj時處在同一列上，不難看出兩個皇后處在同一條對角線上當且僅當xi xj=i一j或xi xj=j-i。 算法13.3 4-QUEENS輸入：空。輸出：對應于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循環退出 10. else if c是部分解then k

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

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

19、,x2xn和整數y，找出和等于y的X的子集Y。比如說，如果X=10,20,30,40,50,60，和y=60，則有三種不同長度的解，他們分別是10,20,30，20，40，60，設計出一個求解這個問題的回溯算法并不難，注意這個問題可以用另一種方法明確表達，使得解是一種明顯長度為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繼續，如果（x1，x2）是一個部分解，那么就包括X3中最小的元素，否則x2被置為X2中的下一個元素。一般的，假定算法已經檢測到部分解為（x1，x2，xj），它然后再去考慮向量v=（x1，x2，xj，xj+1）,我們有下面的情況。(1) 如果v表示問題的最后解，算法記錄下它作為一個解，在僅希望獲得一個解時終止，或者繼續去找出其他解。(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循環退出8. Else if v是部分解 then k ß k+1 前進9. End while10. 重置 Xk 使得下一個元素排在第一位11. k ß k-1 回溯12. End while13. If flag then output v14. Else output “no solution”四、資料與課本進行比較 相同點：對于回溯法，都提及到了有關解空間樹的概念；都用到了著色問題和8皇后問題這兩個經典的回溯算法的例子；都通過迭代法和遞歸兩種方法來描述回溯法。不同點：書本上所舉的例子很多，更有助于

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

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