回溯法的效率分析

1、回溯法概述與窮舉的 “笨拙 ”搜索相比，回溯法則是一種 “聰明 ”的求解效益更高的搜索 法。下面介紹回溯設計及其應用，體會回溯法相對于窮舉的特點與優(yōu)勢?；厮莸母拍钣性S多問題，當需要找出它的解集或者要求回答什么解是滿足某些約束條 件的最佳解時，往往使用回溯法?；厮莘ㄊ且环N試探求解的方法：通過對問題的歸納分析，找出求解問題的 一個線索，沿著這一線索往前試探，若試探成功，即得到解；若試探失敗，就 逐步往回退，換其他路線再往前試探。因此，回溯法可以形象地概括為 “向前 走，碰壁回頭 ”?；厮莘ǖ幕咀龇ㄊ窃囂剿阉?，是一種組織得井井有條的、能避免一些不 必要搜索的窮舉式搜索法?；厮莘ㄔ趩栴}的解空間樹中，

2、從根結(jié)點出發(fā)搜索解 空間樹，搜索至解空間樹的任意一點，先判斷該結(jié)點是否包含問題的解；如果 肯定不包含，則跳過對該結(jié)點為根的子樹的搜索，逐層向其父結(jié)點回溯；否 則，進入該子樹，繼續(xù)搜索。從解的角度理解，回溯法將問題的候選解按某種順序進行枚舉和檢驗。當 發(fā)現(xiàn)當前候選解不可能是解時，就選擇下一個候選解。在回溯法中，放棄當前 候選解，尋找下一個候選解的過程稱為回溯。倘若當前候選解除了不滿足問題 規(guī)模要求外，滿足所有其他要求時，繼續(xù)擴大當前候選解的規(guī)模，并繼續(xù)試 探。如果當前候選解滿足包括問題規(guī)模在內(nèi)的所有要求時，該候選解就是問題 的一個解。與窮舉法相比，回溯法的 “聰明 ”之處在于能適時 “回頭 ”，

3、若再往前走不可能 得到解，就回溯，退一步另找線路，這樣可省去大量的無效操作。因此，回溯 與窮舉相比，回溯更適宜于量比較大，候選解比較多的問題?；厮菝枋?回溯的一般方法面簡要闡述回溯的一般方法?；厮萸蠼獾膯栴}P,通常要能表達為：對于已知的由n元組(x1,x2, ,xn)組成的一個狀態(tài)空間E=(x1,x2, ,xn)|xi si,i=1,2,n，給定關(guān)于n元組中的一個分量的一個約束集 D,要求E中滿足 D的全部約束條件的所有n元組。其中si 是分量 xi 的定義域，且 |si|有限，i=1,2,n。稱E中滿足D的全部約束條件的任一 n元組為問題P的 一個解。解問題P的最樸素的方法就是窮舉法，上面已

4、經(jīng)作了介紹，即對E中的所有n元組逐一地檢驗其是否滿足 D的全部約束，若滿足，則為問題 P的一個 解。顯然，其計算量是相當大的。對于許多問題，所給定的約束集D具有完備性，即i元組(x1,x2, ,xi)滿足D中僅涉及到x1,x2, ,xi的所有約束，意味著j(j<i)元組(x1,x2, ,xj)一定也滿足D中僅涉及到x1,x2, ,xj £ n使得（xj 的所有約束， i=1,2,n 。換句話說，只要存在1,x2, ,xj)違反D中僅涉及到x1,x2, ,xj 的約束之一，則以 (x1,x2, ,xj)為前綴的任何n元組(x1,x2, ,xj,xj+1,xn)也一定違反D中僅涉及

5、到x1,x2, ,xj的一個約束，n»jo因此，對于約束集D具有完備性的問題P, 旦檢 測斷定某個 j 元組 (x1,x2, ,xj)違反D中僅涉及x1,x2, ,xj 的一個約束，就可以肯定，以 (x1,x2, ,xj)為前綴的任何n元組(x1,x2, ,xj,xj+1,xn)都不會是問題P的解，因而就不必去搜索它們，即省略了對部分元素(xj+1,xn）的操作與測試。回溯法正是針對這類問題，利用這類問題的上述性質(zhì)而 提出來的比窮舉法效率更高的算法。2. 4皇后問題的回溯實施為了具體說明回溯的實施過程，先看一個簡單實例。如何在4X4的方格棋盤上放置4個皇后，使它們互不攻擊，即任意兩個

6、皇 后不允許處在同一橫排，同一縱列，也不允許處在同一與棋盤邊框成45°角的斜線上。圖5-1所示為應用回溯的實施過程，其中方格中的 表示試圖在該方格放置 一個皇后 ,但由于受前面已放置的皇后的攻擊而放棄的位置。圖 5-14 皇后問題回溯實施求解圖（a）為在第1行第1列放置一個皇后的初始狀態(tài)。圖（b）中，第2個皇后不能放在第1、2列，因而放置在第3列上。圖（c）中，表示第3行的所有各列均不能放置皇后，則返回第 2行，第2 個皇后需后移。圖（d）中，第2個皇后后移到第4列，第3個皇后放置在第2列。圖（e）中，第4行的所有各列均不能放置皇后，則返回第 3行；第3個皇 后后移的所有位置均不能放

7、置皇后，則返回第 2行；第 2個皇后已無位可退， 則返回第 1 行；第 1 個皇后需后移。圖（f）中，第1個皇后后移至第2格。圖（g）中，第2個皇后不能放在第1, 2, 3列，因而放置在第4列上。圖 （h）中，第3個皇后放在第1列；第4個皇后不能放置1, 2列，于是放置在 第 3 列。這樣經(jīng)以上回溯，得到 4皇后問題的一個解： 2413。繼續(xù)以上的回溯探索，可得 4皇后問題的另一個解： 3142。3回溯算法框架描述(1)回溯描述對于一般含參量 m,n 的搜索問題，回溯法框架描述如下：輸入正整數(shù)n,m,(n > m)i=1;ai=v元素初值>while (1)for(g=1,k=i-

8、1;k>=1;k-)if( <約束條件1> ) g=0;檢測約束條件，不滿足則返回if(g && <約束條件 2>)printf(a1-m);/ 輸出一個解if(i<n && g) i+;ai=<取值點 >continue;while(ai=< 回溯點 > && i>1) i-; 向前回溯if(ai=n && i=1) break;/ 退出循環(huán)，結(jié)束else ai=ai+1;具體求解問題的試探搜索范圍與要求不同，在應用回溯設計時，需根據(jù)問 題的具體實際確定數(shù)組元素的

9、初值、取值點與回溯點，同時需把問題中的約束 條件進行必要的分解，以適應上述回溯流程。其中實施向前回溯的循環(huán)while(ai=v 回溯點 > && i>1) i-;是向前回溯一步，還是回溯兩步或更多步，完全根據(jù)ai是否達到回溯點來確定。例如，回溯點是n，i=6，當a6=n時回溯到i=5;若a5=n時回溯到 i=4;依此類推，到ai達到回溯點則停止。圖 5-1所示的 4皇后問題迭代回溯過程描述為：n=4;i=1;ai=1;while (1)g=1;for(k=i-1;k>=1;k-)if(ai=ak && abs(ai-ak)=i-k)g=0;/

10、檢測約束條件 ,不滿足則返回if(g && i=4)printf(a1-4);/ 輸出一個解if(i<n && g) i+;ai=1;continue;while(ai=n && i>1) i-;/ 向前回溯if(ai=n && i=1) break;/ 退出循環(huán)結(jié)束else ai=ai+1;以上回溯體現(xiàn)在迭代式i=i-1，因而又稱為迭代回溯。此外，遞歸也能實現(xiàn)回溯。(2)遞歸回溯int put(int k) int i,j,u;if( k二問題規(guī)模) u=0;if( 約束條件 )u=1;/ 當 k 時不可操作if(u

11、=0)/ 當 k 時可操作 if(k=規(guī)模)/ 若已滿足規(guī)模，則打印出一個解printf( 一個解 );else put(k+1);/ 調(diào)用 put(k+1)在調(diào)用put(k)時，當檢測約束條件知不可操作(記 u=1)，即再往前不可能 得解，此時當然不可能輸出解，也不調(diào)用 put(k+1)，而是回溯，返回調(diào)用put(k) 之處。這就是遞歸回溯的機理。如果是主程序調(diào)用put(1)，最后返回到主程序調(diào)用put(1)的后續(xù)語句，完成 遞歸。圖 5.1 所示的 4 皇后問題迭代回溯過程描述為：int put(int k) int i,j,u;if(k=4) for(i=1;i<=4;i+)/ 探

12、索第 k 行從第 1 格開始放皇后 ak=i;for(u=0,j=1;j<=k-1;j+)if(ak=aj | abs(ak-aj)=k-j )u=1; / 若第 k 行第 i 格放不下 ,則置 u=1if(u=O)/若第k行第i格可放，則檢測是否滿4行 if(k=4)/若已放滿到 4 行時，則打印出一個解 s+; printf(" ");for (j=1;j<=4;j+)printf("%d",aj);else put(k+1); / 若沒放滿 4 行,則放下一行 put(k+1)4.回溯法的效益分析應用回溯設計求解實際問題，由于解空間的結(jié)

13、構(gòu)差異，很難精確計算與估 計回溯產(chǎn)生的結(jié)點數(shù)，因此回溯法的復雜度是分析回溯法效率時遇到的主要困 難?；厮莘óa(chǎn)生的結(jié)點數(shù)通常只有解空間結(jié)點數(shù)的一小部分，這也是回溯法的 計算效率大大高于窮舉法的原因所在?；厮萸蠼膺^程實質(zhì)上是一個遍歷一棵 “狀態(tài)樹 ”的過程，只是這棵樹不是遍 歷前預先建立的?；厮菟惴ㄔ谒阉鬟^程中，只要所激活的狀態(tài)結(jié)點滿足終結(jié)條 件，應該把它輸出或保存。由于在回溯法求解問題時，一般要求輸出問題的所有解，因此在得到結(jié)點 后，同時也要進行回溯，以便得到問題的其他解，直至回溯到狀態(tài)樹的根且根 的所有子結(jié)點均已被搜索過為止。組織解空間便于算法在求解集時更易于搜索，典型的組織方法是圖或樹。 一

14、旦定義了解空間的組織方法，這個空間即可從開始結(jié)點進行搜索?；厮莘ǖ臅r間通常取決于狀態(tài)空間樹上實際生成的那部分問題狀態(tài)的數(shù)目。對于元組長度為n的問題，若其狀態(tài)空間樹中結(jié)點總數(shù)為n!，則回溯算法的最壞情形的時間復雜度可達 0(p(n)n!);若其狀態(tài)空間樹中結(jié)點總數(shù)為2,貝卩回溯算法的最壞情形的時間復雜度可達0(p(n)2),其中p(n)為n的多項式。對于不同的實例，回溯法的計算時間有很大的差異。對于很多具有大n的求解實例,應用回溯法一般可在很短的時間內(nèi)求得其解,可見回溯法不失為一 種快速有效的算法。對于某一具體實際問題的回溯求解,常通過計算實際生成結(jié)點數(shù)的方法即 蒙特卡羅方法(Monte car

15、lo)來評估其計算效率。蒙特卡羅方法的基本思想是 在狀態(tài)空間樹上隨機選擇一條路徑 (x0,x1, ,xn-1)，設X是這一路徑上部分向量(x0,x1, ,xk-1)的結(jié)點，如果在X處不受限制的子向量數(shù)是mk，則認為與X同一層的其他結(jié)點不受限制的子向量數(shù)也都是mk。也就是說，若不受限制的x0 取值有 m0個，則該層上有m0個結(jié)點；若不受限制的x1取值有m1個，則該層上有m0m1個結(jié)點；依此類推。由于認為在同一層上不受限制的結(jié)點數(shù)相同，因此, 該路徑上實際生成的結(jié)點數(shù)估計為m 1 m0 m0m1 m0m1m2 計算路徑上結(jié)點數(shù)m的蒙特卡羅算法描述如下：/已知隨機路徑上取值數(shù)據(jù)m0,m1, ,mk-

16、1m=1;t=1;for(j=0;jv二k-1;j+) t=t*mj;m=m+t;printf( “ %ld” ,m);把所求得的隨機路徑上的結(jié)點數(shù)(或若干條隨機路徑的結(jié)點數(shù)的平均值) 與狀態(tài)空間樹 nn上的總結(jié)點數(shù)進行比較，由其比值可以初步看出回溯設計的效益。在下面 的 n 皇后問題的回溯求解時將具體應用以上蒙特卡羅算法估計回溯設計的效5.8 回溯應用小結(jié)本章應用回溯設計求解了逐位整除數(shù)與橋本分數(shù)式等涉及數(shù)與數(shù)式的典型 案例、求解了新穎的素數(shù)環(huán)與德布魯金環(huán)等環(huán)序列，求解了直尺刻度分布與數(shù) 碼串珠等趣題，也求解了伯努利裝錯信封問題與別出心裁的情侶拍照等難度較 大的組合案例。可見回溯法的應用是非常廣闊的。回溯法有 “通用解題法 ”之稱，是一種比窮舉 “聰明 ”的搜索技術(shù)，在搜索過程 中動態(tài)地產(chǎn)生問題的解空間，系統(tǒng)地搜索問題的所有解。當搜索到解空間樹的 任一結(jié)點時，判斷該結(jié)點是否包含問題的解。如果該結(jié)點肯定不