1、算法創(chuàng)新與實踐論文沈陽理工大學算法實踐與創(chuàng)新論文題目 回溯法的分析與應用學生姓名： 學號： 學生姓名： 學號： 學生姓名： 學號： 24 摘要對于計算機科學來說，算法的概念是至關重要的，算法是一系列解決問題的清晰指令，也就是說，能夠對一定規(guī)范的輸入，在有限時間內獲得所要求的輸出。為了更加的了解算法，本篇論文中，我們先研究一個算法-回溯法。回溯法是一種常用的重要的基本設計方法。它的基本做法是在可能的范圍之內搜索，適于解一些組合數相當大的問題。圓排列描述的是在給定n個大小不等的圓 C1,C2,Cn,現要將這n個圓排進一個矩形框中，且要求各圓與矩形框的底邊相切。圓排列問題要求從n個圓的所有排列中找出

2、有最小長度的圓排列。圖著色問題用數學定義就是給定一個無向圖G=（V, E），其中V為頂點集合，E為邊集合，圖著色問題即為將V分為K個顏色組，每個組形成一個獨立集，即其中沒有相鄰的頂點。其優(yōu)化版本是希望獲得最小的K值。符號三角形問題要求對于給定的n，計算有多少個不同的符號三角形，使其所含的“+”和“-”的個數相同。在本篇論文中，我們將運用回溯法來解決著圖的著色問題，符號三角形問題，圖排列問題，將此三個問題進行深入的探討。 關鍵詞: 回溯法 圖的著色問題 符號三角形問題 圖排列問題I目錄第1章 引言1第2章 回溯法的背景2第3章 圖的著色問題43.1 問題描述43.2 四色猜想43.3 算法設計5

3、3.4 源代碼63.5 運行結果圖10第4章 符號三角形問題114.1 問題描述114.2 算法設計114.3 源代碼124.4 運行結果圖16第5章 圓的排列問題175.1 問題描述175.2 問題分析175.3 源代碼185.4 運行結果圖22結論23參考文獻24II第1章 引言在現實世界中，有相當一類問題試求問題的全部解或求問題的最優(yōu)解。最基本的方法是通過枚舉法搜索問題的解空間。但許多問題解空間的大小隨問題規(guī)模n的增長呈指數規(guī)律增長，這就使問題理論上可解而實際不可行。為了使搜索空間減少到盡可能小，就需要采用良好的搜索技術?；厮莘ň褪且环N較好的搜索技術。回溯法又稱為試探法，它是一種有效的試

4、探回溯搜索技術。即運用回溯法求解問題不是基于某種確定的法則，而是通過大量反復的試探和回溯。它的基本做法是搜索，能避免不必要搜素的窮舉式搜索?；厮莘ㄔ趩栴}的解空間樹中按深度優(yōu)先策略，從根結點出發(fā)搜索解空間樹，算法搜索至解空間樹的任意一點時，先判斷該節(jié)點是否包含問題的解，如果肯定不包含，則跳過對該結點為根的子樹的搜索，逐層向其祖先結點回溯；否則，進入該子樹，繼續(xù)按深度優(yōu)先策略搜索。簡單地說，采用回溯法求解問題的整個過程貫穿了搜索-試探決定回溯或前進這三種基本運算。通過運用回溯法，可以解決很多問題，譬如我們所熟知的“八皇后問題”，“0/1背包問題”，這只是在教學階段中的運用，在實際運用中也產生很大的

5、作用在學習過程中，我們會遇到這樣的問題，讓我們去尋找給定問題的解集或者讓我們找出滿足某些約束條件的最優(yōu)解，這時候我們就可以采用回溯法來解決這一類的問題。通過運用回溯法，可以解決很多問題，譬如我們所熟知的“八皇后問題”，“0/1背包問題”，這只是在教學階段中的運用，在實際運用中也產生很大的作用回溯法的優(yōu)點是容易理解，可行性比較強。1 原福永算法設計與分析.機械工業(yè)出版社，1998；P213-214第2章 回溯法的背景回溯法是一種窮舉類型的算法，與其說它是一種算法，倒不如說它是一種試法。回溯法并沒有什么高深的算法思想，雖然名字起的很高規(guī)格，但其實它的算法性連二分查找都比不上。這里說的算法性其實就是

6、指技巧性，對問題特性了解越深入，越能創(chuàng)造出很巧妙的算法，在時間復雜度的級別上提高算法效率。這體現了算法效率與適用性之間的矛盾，二分查找效率很高，但適用性比較低，類似的還有著名的KMP算法。而窮舉法效率最低，但幾乎適用于所有問題?；厮莘ㄊ且环N試探性算法，從這一點上看，它很像窮舉法。但它終究不是窮舉法，回溯法是有組織的進行窮舉，在試探過程中不斷通過題設要求減少搜索空間，而這種減少不是一個一個解的減少，而是對搜索空間進行大規(guī)模剪枝，從而使得實際搜索空間遠遠小于問題的解空間，所以回溯法的實際運行效率還是比較高的?；厮莘ǖ膽帽尘罢f大很大，說小很小。算法大都在“不得不”的情況 下才會使用，如果有別的算法

7、，那它很有可能比回溯法高效，別忘了，回溯法是基于窮舉的。回溯法適用于解排列組合類問題，也就是說目標解是從一個候選空間中選擇出來的。從數量級上考慮，設候選空間的大小為n，如果選擇是可重復的，那生成的搜索樹為完全n叉樹，搜索空間為nn（如0-1背包問題，生成的解空間為高度為n完全二叉樹，其中n為物體個數）。如果選擇不能重復，那生成的解空間為n!(如TSP問題生成的解空間為n!,其中n為城市個數)。也就是說，當我們通過分析發(fā)現問題的解空間為nn或者n!時，那很可能要用到我們的回溯法了。要用回溯法解決問題，那首先要確定問題的狀態(tài)空間樹。這個并不是很難，就看每一步選擇有多少個可選值就可以了，第一步有8個

8、可選值，那樹第一層就有8個節(jié)點，第二步有5個可選值，那第一層每個節(jié)點都有5個分支，則第二層有8×5=40個節(jié)點，以此類推到第n層一共有m1×m2××mn個節(jié)點，其中mi為第i步的可選值的個數。2 王曉東.計算機算法設計與分析.電子工業(yè)出版社，2012；P53-54確定了狀態(tài)空間樹，那下一步就是搜索了。這時候就體現出回溯法的優(yōu)勢了，前面不是說了嘛，回溯法的特點就是有規(guī)律、有組織的進行搜索，那下面就來看一下回溯法是如何進行搜索的：在開始搜索之前，我們先來說一下我們要做的事情，我們要得到一個解向量solution，每個分量對應每一步選擇的結果，顯然這個解向量的

9、長度應該為n（我們采用c語言的標準，下標范圍為0到n-1）。好了，現在我們有了一個狀態(tài)空間樹（邏輯上的，并不用實現）和一個解向量（物理上的，要用來裝數據的）。現在可以開始搜索了，先設定一個下標r，這個r就是解向量的下標，也用于標識狀態(tài)樹的第r行。先做第一步，令r=0，選solution0，也就是從樹的第0行選擇一個值放入solution0，顯然剛開始我們應該選擇第一個，即前面提到的8個里面的第一個。然后看這個半成品解向量是否是可行的，也就是說看看剛才選擇的那個值是否滿足要求，加入那個值不滿足要求，那應該選擇第二個，以此類推直到選擇一個可行的值，放入solution0。然后r+進行第二步，選擇s

10、olution1，同樣的，我們應該從樹的第二行中選擇第一個看構成的解是否可行（此時解向量中包含兩個元素），這樣的步驟一直進行下去，直到出現這樣的情況3 毛靜華，劉麗紅.基于回溯法的案例推理方法研究.情報雜志,2015；P40-41（1）r=n-1了，也就是說我們得到了問題的一個可行解，這時候就要看題設要求了，如果只要求找到一個可行解，那此時算法就可以停止了。（2）某一層的候選值選完了，我們知道，沒一層的候選值都有一定個數，如上面提到的例子中第二層只有5個候選值，如果這五個候選值都試探完了還是沒有可行解那該怎么辦呢？這里體現的思想就是我們回溯法名字的由來，回溯。也就是令r-退回去，從新選擇上面的

11、解。比如上面的例子先選擇8個中的第一個作為解的一部分，然后發(fā)現后面的5個和前面這個都不能組成可行解，那這就說明前面那個選擇是不可行的，和后面是不搭配的。所以應該返回去選擇8個中的第二個，然后再對5個進行選擇，看哪個與這個第二個想匹配。（3）最后一種情況，因為我們這個過程中有回溯過程，即r-的過程，那可能最后r小于0了，這說明整個樹都搜索完了，也就是問題沒有可行解。回溯法一般有兩種代碼實現方案，遞歸方法和非遞歸方法。相比之下，遞歸設計方法比較簡單，用前面提到的r作為遞歸變量即可，如果滿足搜索條件，則遞歸調用r+1對應函數，如果不滿足，則遞歸調用r-1對應的函數?；A步為當r0或r=n-1分別對應

12、無解和得到可行解，這個就不多說了。非遞歸方法，也就是循環(huán)方法設計細節(jié)比較多，但只要掌握了其特點，對不同問題的適用性很強（即代碼只通過很少的修改就可以應用到不同問題），加之其效率高于遞歸算法（循環(huán)的優(yōu)勢），所以這里我們著重講一下回溯的非遞歸代碼實現。第3章 圖的著色問題3.1 問題描述 給定一個無向連通圖G和m>0種顏色，在只準使用者m中顏色對G的結點重色的情況下，是否能使途中任何相鄰的兩個結點都具有不同的顏色嗎?3.2 四色猜想四色問題是m圖著色問題的一個特例，根據四色原理，證明平面或球面上的任何地圖的所有區(qū)域都至多可用四種、顏色來著色，并使任何兩個有一段公共邊界的相鄰區(qū)域沒有相同的顏色

13、。這個問題可轉換成對一平面圖的著色判定問題(平面圖是一個能畫于平面上而邊無任何交叉的圖)。將地圖的每個區(qū)域變成一個結點，若兩個區(qū)域相鄰，則相應的結點用一條邊連接起來。4352112345多年來，雖然已證明用5種顏色足以對任一幅地圖著色，但是一直找不到一定要求多于4種顏色的地圖。直到1976年這個問題才由愛普爾，黑肯和考西利用電子計算機的幫助得以解決。他們證明了4種顏色足以對任何地圖著色。4 馮俊.算法與程序設計基礎教程.清華大學出版社，2010；P252-256圖圖3-13.3 算法設計 考慮所有的圖，討論在至多使用m種顏色的情況下，可對一給定的圖著色的所有不同方法。通過回溯的方法，不斷的為每

14、一個節(jié)點著色，在前面n-1個節(jié)點都合法的著色之后，開始對第n個節(jié)點進行著色，這時候枚舉可用的m個顏色，通過和第n個節(jié)點相鄰的節(jié)點的顏色，來判斷這個顏色是否合法，如果找到那么一種顏色使得第n個節(jié)點能夠著色，那么說明m種顏色的方案是可行的。用m種顏色為無向圖G=(V,E)著色，其中，V的頂點個數為n，可以用一個n元組x=(x1,x2,xn)來描述圖的一種可能著色，其中，xi1, 2, , m，(1in)表示賦予頂點i的顏色。例如，5元組(1, 2, 2, 3, 1)表示對具有5個頂點的無向圖（a）的一種著色，頂點A著顏色1，頂點B著顏色2，頂點C著顏色2，如此等等。如果在n元組X中，所有相鄰頂點都

15、不會著相同顏色，就稱此n元組為可行解，否則為無效解。容易看出，每個頂點可著顏色有m種選擇，n個頂點就有mn種不同的著色方案，問題的解空間是一棵高度為n的完全m叉樹，這里樹高度的定義為從根節(jié)點到葉子節(jié)點的路徑的長度。每個分支結點，都有m個兒子結點。最底層有mn個葉子結點。 圖3-23.4 源代碼 #include <iostream>#include <fstream>using namespace std;const int N = 5;const int M = 3;ifstream fin("5d8.txt"); class Color frie

16、nd int mColoring(int, int, int *); private: bool Ok(int k); void Backtrack(int t); int n, m, *a, *x; long sum; ;int mColoring(int n,int m,int *a);int main() int *a = new int *N+1; for(int i=1;i<=N;i+) ai = new intN+1; cout<<"圖G的鄰接矩陣為:"<<endl; for(int i=1; i<=N; i+) for(in

17、t j=1; j<=N; j+) fin>>aij; cout<<aij<<" " cout<<endl; cout<<"圖G的著色方案如下："<<endl; cout<<"當m="<<M<<"時，圖G的可行著色方案數目為："<<mColoring(N,M,a)<<endl; for(int i=1;i<=N;i+) delete ai; delete a;void Col

18、or:Backtrack(int t) if (t>n) sum+; for (int i=1; i<=n; i+) cout << xi << " " cout << endl; else for (int i=1;i<=m;i+) xt=i; if (Ok(t) Backtrack(t+1); bool Color:Ok(int k) for (int j=1;j<=n;j+) if (akj=1)&&(xj=xk) return false; return true;int mColoring

19、(int n,int m,int *a) Color X; X.n = n; X.m = m; X.a = a; X.sum = 0; int *p = new intn+1; for(int i=0; i<=n; i+) pi = 0; X.x = p; X.Backtrack(1); delete p; return X.sum;圖m可著色問題的解空間樹中內結點個數是。對于每一個內結點，在最壞情況下，用ok檢查當前擴展結點的每一個兒子所相應的顏色可用性需耗時O(mn)。因此，回溯法總的時間耗費是：3.5 運行結果圖圖3-3第4章 符號三角形問題4.1 問題描述下圖是由14個“+”和1

20、4個“-”組成的符號三角形。2個同號下面都是“+”，2個異號下面都是“-”。+ + - + - + + - - - - +- + + + - + + - + - -+圖4-1在一般情況下，符號三角形的第一行有n個符號。符號三角形問題要求對于給定的n，計算有多少個不同的符號三角形，使其所含的“+”和“-”的個數同。5 馮學軍，石冰.算法設計與分析.安慶師范學院學報，2012年第18卷；P23-324.2 算法設計符號三角形問題用n元組1:n表示符號三角形的第一行的n個字符。Xi=1表示第一行第i個符號為“+”，Xi=0表示第一行第i個符號為“-”；1<=i<=n。由于Xi是2值的，所

21、以在用回溯法解符號三角形問題時，可以用完全二叉樹來表示其解空間?？尚行约s束函數，當前符號三角形所包含的“+”個數與“-”個數均不超過n*（n+1）/4。 在算法中遞歸方法backtrack（1）實現對整個解空間的回溯搜索。Backtrack（i）搜索整個解空間中第i層子樹。類Triangles的數據成員記錄解空間中間點信息，以減少傳給backtrack的參數。Sum記錄當前已找到的“+”的個數與“-”個數相同的符號三角形數。 在算法backtrack中，當i>n時，算法搜索至葉節(jié)點，得到一個新的“+”個數與“-”個數相同的符號三角形，當前已找到的符號三角形數sum增1。當I<=n時

22、，當前擴展節(jié)點Z是解空間中的內部結點。該結點有Xi=1和Xi=0兩個兒子結點。對當前擴展結點Z的每一個兒子結點，計算其相應的符號三角形中的“+”個數count與“-”個數，并以深度優(yōu)先的方式遞歸的對可行子樹搜索，或減去不可行子樹。6 未知.計算機算法設計與分析.百度文庫，2011； 無解的判斷，n*(n+1)/2為奇數。4.3 源代碼#include <iostream>using namespace std; class Triangle friend int Compute(int); private: void Backtrack(int i); int n, half, c

23、ount, *p; long sum; ; int Compute(int n);int main() for(int n=1;n<=10;n+) cout<<"n="<<n<<"時，共有"<<Compute(n); cout<<"個不同的符號三角形。"<<endl; return 0;void Triangle:Backtrack(int t) if (count>half)|(t*(t-1)/2-count>half) return; if

24、(t>n) sum+; else for (int i=0;i<2;i+) p1t=i; count+=i; for(int j=2;j<=t;j+) pjt-j+1=pj-1t-j+1pj-1t-j+2; count+=pjt-j+1; Backtrack(t+1); for (int j=2;j<=t;j+) count-=pjt-j+1; count-=i; int Compute(int n) Triangle X; X.n=n; X.count=0; X.sum=0; X.half=n*(n+1)/2; if(X.half%2=1)return 0; X.ha

25、lf=X.half/2; int*p=new int*n+1; for(int i=0;i<=n;i+) pi=new intn+1; for(int i=0;i<=n;i+) for(int j=0;j<=n;j+) pij=0; X.p=p; X.Backtrack(1); for(int i=0;i<=n;i+) delete pi; delete p; p=0; return X.sum;計算可行性約束需要O(n)時間，在最壞情況下有 O(2n)個結點需要計算可行性約束，故解符號三角形問題的回溯算法所需的計算時間為 O(n2n)。 4.4 運行結果圖 圖4-2第

26、5章 圓的排列問題5.1 問題描述給定n個大小不等的圓c1,c2,cn，現要將這n個圓排進一個矩形框中，且要求各圓與矩形框的底邊相切。圓排列問題要求從n個圓的所有排列中找出有最小長度的圓排列。例如，當n=3，且所給的3個圓的半徑分別為1，1，2時，這3個圓的最小長度的圓排列如圖所示。其最小長度為 2+4。7 楊金勇等. 圓排列包裝問題最優(yōu)解解析.華僑大學學報，2013年2期；P58-62圖4-12+45.2 問題分析 圓排列問題的解空間是一棵排列樹。按照回溯法搜索排列樹的算法框架，設開始時a=r1,r2,rn是所給的n個元的半徑，則相應的排列樹由a1:n的所有排列構成。解圓排列問題的回溯算法中

27、，CirclePerm(n,a)返回找到的最小的圓排列長度。初始時，數組a是輸入的n個圓的半徑，計算結束后返回相應于最優(yōu)解的圓排列。center計算圓在當前圓排列中的橫坐標，由x2= sqrt(r1+r2)2-(r1-r2)2)推導出x = 2*sqrt(r1*r2)。 Compoute計算當前圓排列的長度。變量min記錄當前最小圓排列長度。數組r表示當前圓排列。數組x則記錄當前圓排列中各圓的圓心橫坐標。在遞歸算法Backtrack中，當i>n時，算法搜索至葉節(jié)點，得到新的圓排列方案。此時算法調用Compute計算當前圓排列的長度，適時更新當前最優(yōu)值。當i<n時，當前擴展節(jié)點位于排

28、列樹的i-1層。此時算法選擇下一個要排列的圓，并計算相應的下界函數。5.3 源代碼#include <iostream>#include <cmath>using namespace std;float CirclePerm(int n,float *a);template <class Type>inline void Swap(Type &a, Type &b);int main() float *a = new float4; a1 = 1,a2 = 1,a3 = 2; cout<<"圓排列中各圓的半徑分別為：&q

29、uot;<<endl; for(int i=1; i<4; i+) cout<<ai<<" " cout<<endl; cout<<"最小圓排列長度為：" cout<<CirclePerm(3,a)<<endl; return 0;class Circle friend float CirclePerm(int,float *); private: float Center(int t); void Compute(); void Backtrack(int t);

30、 float min, *x, *r; int n; ;float Circle:Center(int t) float temp=0; for (int j=1;j<t;j+) float valuex=xj+2.0*sqrt(rt*rj); if (valuex>temp) temp=valuex; return temp;void Circle:Compute(void) float low=0,high=0; for (int i=1;i<=n;i+) if (xi-ri<low) low=xi-ri; if (xi+ri>high) high=xi+ri

31、; if (high-low<min) min=high-low; void Circle:Backtrack(int t) if (t>n) Compute(); else for (int j = t; j <= n; j+) Swap(rt, rj); float centerx=Center(t); if (centerx+rt+r1<min) xt=centerx; Backtrack(t+1); Swap(rt, rj); float CirclePerm(int n,float *a) Circle X; X.n = n; X.r = a; X.min = 100000; float *x = new floatn+1; X.x = x; X.Backtrack(1); delete x; return X.min;template <c