回溯法的效率分析(共6頁(yè))

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

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

3、，就回溯，退一步另找線路，這樣可省去大量的無(wú)效操作。因此，回溯與窮舉相比，回溯更適宜于量比較大，候選解比較多的問(wèn)題。5.1.2 回溯描述 1回溯的一般方法下面簡(jiǎn)要闡述回溯的一般方法。回溯求解的問(wèn)題P，通常要能表達(dá)為：對(duì)于已知的由n元組(x1,x2,xn)組成的一個(gè)狀態(tài)空間E=(x1,x2,xn)|xisi,i=1,2,n，給定關(guān)于n元組中的一個(gè)分量的一個(gè)約束集D，要求E中滿足D的全部約束條件的所有n元組。其中si是分量xi的定義域，且|si|有限，i=1,2,n。稱E中滿足D的全部約束條件的任一n元組為問(wèn)題P的一個(gè)解。解問(wèn)題P的最樸素的方法就是窮舉法，上面已經(jīng)作了介紹，即對(duì)E中的所有n元組逐一

4、地檢驗(yàn)其是否滿足D的全部約束，若滿足，則為問(wèn)題P的一個(gè)解。顯然，其計(jì)算量是相當(dāng)大的。對(duì)于許多問(wèn)題，所給定的約束集D具有完備性，即i元組(x1,x2,xi)滿足D中僅涉及到x1,x2,xi的所有約束，意味著j(j<i)元組(x1,x2,xj)一定也滿足D中僅涉及到x1,x2,xj的所有約束，i=1,2,n。換句話說(shuō)，只要存在0jn-1，使得(x1,x2,xj)違反D中僅涉及到x1,x2,xj的約束之一，則以(x1,x2,xj)為前綴的任何n元組(x1,x2,xj,xj+1,xn)也一定違反D中僅涉及到x1,x2,xj的一個(gè)約束，nij。因此，對(duì)于約束集D具有完備性的問(wèn)題P，一旦檢測(cè)斷定某個(gè)

5、j元組(x1,x2,xj)違反D中僅涉及x1,x2,xj的一個(gè)約束，就可以肯定，以(x1,x2,xj)為前綴的任何n元組(x1,x2,xj,xj+1,xn)都不會(huì)是問(wèn)題P的解，因而就不必去搜索它們，即省略了對(duì)部分元素(xj+1,xn)的操作與測(cè)試?；厮莘ㄕ轻槍?duì)這類問(wèn)題，利用這類問(wèn)題的上述性質(zhì)而提出來(lái)的比窮舉法效率更高的算法。2. 4皇后問(wèn)題的回溯實(shí)施為了具體說(shuō)明回溯的實(shí)施過(guò)程，先看一個(gè)簡(jiǎn)單實(shí)例。如何在4×4的方格棋盤(pán)上放置4個(gè)皇后，使它們互不攻擊，即任意兩個(gè)皇后不允許處在同一橫排，同一縱列，也不允許處在同一與棋盤(pán)邊框成45°角的斜線上。圖5-1所示為應(yīng)用回溯的實(shí)施過(guò)程，其

6、中方格中的×表示試圖在該方格放置一個(gè)皇后,但由于受前面已放置的皇后的攻擊而放棄的位置。圖5-1 4皇后問(wèn)題回溯實(shí)施求解圖（a）為在第1行第1列放置一個(gè)皇后的初始狀態(tài)。圖（b）中，第2個(gè)皇后不能放在第1、2列，因而放置在第3列上。圖（c）中，表示第3行的所有各列均不能放置皇后，則返回第2行，第2個(gè)皇后需后移。圖（d）中，第2個(gè)皇后后移到第4列，第3個(gè)皇后放置在第2列。圖（e）中，第4行的所有各列均不能放置皇后，則返回第3行；第3個(gè)皇后后移的所有位置均不能放置皇后，則返回第2行；第2個(gè)皇后已無(wú)位可退，則返回第1行；第1個(gè)皇后需后移。圖（f）中，第1個(gè)皇后后移至第2格。圖（g）中，第2個(gè)皇

7、后不能放在第1，2，3列，因而放置在第4列上。圖（h）中，第3個(gè)皇后放在第1列；第4個(gè)皇后不能放置1，2列，于是放置在第3列。這樣經(jīng)以上回溯，得到4皇后問(wèn)題的一個(gè)解：2413。繼續(xù)以上的回溯探索，可得4皇后問(wèn)題的另一個(gè)解：3142。3回溯算法框架描述(1) 回溯描述對(duì)于一般含參量m,n的搜索問(wèn)題，回溯法框架描述如下： 輸入正整數(shù)n,m,(nm) i=1;ai=<元素初值> while (1) for(g=1,k=i-1;k>=1;k-) if( <約束條件1> ) g=0; / 檢測(cè)約束條件,不滿足則返回 if(g && <約束條件2>

8、) printf(a1-m); / 輸出一個(gè)解 if(i<n && g) i+;ai=<取值點(diǎn)>continue; while(ai=<回溯點(diǎn)> && i>1) i-; / 向前回溯 if(ai=n && i=1) break; / 退出循環(huán)，結(jié)束 else ai=ai+1; 具體求解問(wèn)題的試探搜索范圍與要求不同，在應(yīng)用回溯設(shè)計(jì)時(shí)，需根據(jù)問(wèn)題的具體實(shí)際確定數(shù)組元素的初值、取值點(diǎn)與回溯點(diǎn)，同時(shí)需把問(wèn)題中的約束條件進(jìn)行必要的分解，以適應(yīng)上述回溯流程。其中實(shí)施向前回溯的循環(huán)while(ai=<回溯點(diǎn)> &

9、amp;& i>1) i-;是向前回溯一步，還是回溯兩步或更多步，完全根據(jù)ai是否達(dá)到回溯點(diǎn)來(lái)確定。例如，回溯點(diǎn)是n，i=6，當(dāng)a6=n時(shí)回溯到i=5；若a5=n時(shí)回溯到i=4；依此類推，到ai達(dá)到回溯點(diǎn)則停止。圖5-1所示的4皇后問(wèn)題迭代回溯過(guò)程描述為：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; / 檢測(cè)約束條件,不滿足則返回 if(g && i=4) printf(a1-4); / 輸出一個(gè)解 if(i<n &

10、& 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，因而又稱為迭代回溯。此外，遞歸也能實(shí)現(xiàn)回溯。（2） 遞歸回溯int put(int k) int i,j,u; if( k<=問(wèn)題規(guī)模 ) u=0;if( <約束條件> ) u=1; / 當(dāng)k時(shí)不可操作 if(u=0) / 當(dāng)k時(shí)可操作 if(k=規(guī)模) / 若已滿足規(guī)模，則打印出一個(gè)解 printf(

11、<一個(gè)解> ); else put(k+1); / 調(diào)用 put(k+1) 在調(diào)用put(k)時(shí)，當(dāng)檢測(cè)約束條件知不可操作（記u=1），即再往前不可能得解，此時(shí)當(dāng)然不可能輸出解，也不調(diào)用put(k+1)，而是回溯，返回調(diào)用put(k)之處。這就是遞歸回溯的機(jī)理。如果是主程序調(diào)用put(1)，最后返回到主程序調(diào)用put(1)的后續(xù)語(yǔ)句，完成遞歸。圖5.1所示的4皇后問(wèn)題迭代回溯過(guò)程描述為：int put(int k) int i,j,u; if(k<=4) for(i=1;i<=4;i+) / 探索第k行從第1格開(kāi)始放皇后 ak=i; for(u=0,j=1;j<=

12、k-1;j+) if(ak=aj | abs(ak-aj)=k-j ) u=1; / 若第k行第i格放不下,則置u=1 if(u=0) / 若第k行第i格可放,則檢測(cè)是否滿4行 if(k=4) / 若已放滿到4行時(shí)，則打印出一個(gè)解 s+; printf(" "); for (j=1;j<=4;j+) printf("%d",aj); else put(k+1); / 若沒(méi)放滿4行,則放下一行 put(k+1) 4. 回溯法的效益分析應(yīng)用回溯設(shè)計(jì)求解實(shí)際問(wèn)題，由于解空間的結(jié)構(gòu)差異，很難精確計(jì)算與估計(jì)回溯產(chǎn)生的結(jié)點(diǎn)數(shù)，因此回溯法的復(fù)雜度是分析回溯法效率

13、時(shí)遇到的主要困難?；厮莘óa(chǎn)生的結(jié)點(diǎn)數(shù)通常只有解空間結(jié)點(diǎn)數(shù)的一小部分，這也是回溯法的計(jì)算效率大大高于窮舉法的原因所在?；厮萸蠼膺^(guò)程實(shí)質(zhì)上是一個(gè)遍歷一棵“狀態(tài)樹(shù)”的過(guò)程，只是這棵樹(shù)不是遍歷前預(yù)先建立的?；厮菟惴ㄔ谒阉鬟^(guò)程中，只要所激活的狀態(tài)結(jié)點(diǎn)滿足終結(jié)條件，應(yīng)該把它輸出或保存。由于在回溯法求解問(wèn)題時(shí)，一般要求輸出問(wèn)題的所有解，因此在得到結(jié)點(diǎn)后，同時(shí)也要進(jìn)行回溯，以便得到問(wèn)題的其他解，直至回溯到狀態(tài)樹(shù)的根且根的所有子結(jié)點(diǎn)均已被搜索過(guò)為止。組織解空間便于算法在求解集時(shí)更易于搜索，典型的組織方法是圖或樹(shù)。一旦定義了解空間的組織方法，這個(gè)空間即可從開(kāi)始結(jié)點(diǎn)進(jìn)行搜索?；厮莘ǖ臅r(shí)間通常取決于狀態(tài)空間樹(shù)上實(shí)際生

14、成的那部分問(wèn)題狀態(tài)的數(shù)目。對(duì)于元組長(zhǎng)度為n的問(wèn)題，若其狀態(tài)空間樹(shù)中結(jié)點(diǎn)總數(shù)為n!，則回溯算法的最壞情形的時(shí)間復(fù)雜度可達(dá)O(p(n)n!)；若其狀態(tài)空間樹(shù)中結(jié)點(diǎn)總數(shù)為2n，則回溯算法的最壞情形的時(shí)間復(fù)雜度可達(dá)O(p(n)2n)，其中p(n)為n的多項(xiàng)式。對(duì)于不同的實(shí)例，回溯法的計(jì)算時(shí)間有很大的差異。對(duì)于很多具有大n的求解實(shí)例，應(yīng)用回溯法一般可在很短的時(shí)間內(nèi)求得其解，可見(jiàn)回溯法不失為一種快速有效的算法。對(duì)于某一具體實(shí)際問(wèn)題的回溯求解，常通過(guò)計(jì)算實(shí)際生成結(jié)點(diǎn)數(shù)的方法即蒙特卡羅方法（Monte carlo）來(lái)評(píng)估其計(jì)算效率。蒙特卡羅方法的基本思想是在狀態(tài)空間樹(shù)上隨機(jī)選擇一條路徑(x0,x1,xn-1)

15、，設(shè)X是這一路徑上部分向量(x0,x1,xk-1)的結(jié)點(diǎn)，如果在處不受限制的子向量數(shù)是mk，則認(rèn)為與X同一層的其他結(jié)點(diǎn)不受限制的子向量數(shù)也都是mk。也就是說(shuō)，若不受限制的x0取值有m0個(gè)，則該層上有m0個(gè)結(jié)點(diǎn)；若不受限制的x1取值有m1個(gè)，則該層上有m0m1個(gè)結(jié)點(diǎn)；依此類推。由于認(rèn)為在同一層上不受限制的結(jié)點(diǎn)數(shù)相同，因此，該路徑上實(shí)際生成的結(jié)點(diǎn)數(shù)估計(jì)為計(jì)算路徑上結(jié)點(diǎn)數(shù)m的蒙特卡羅算法描述如下：/ 已知隨機(jī)路徑上取值數(shù)據(jù)m0,m1,mk-1 m=1;t=1;for(j=0;j<=k-1;j+) t=t*mj; m=m+t; printf(“%ld”,m);把所求得的隨機(jī)路徑上的結(jié)點(diǎn)數(shù)（或若干

16、條隨機(jī)路徑的結(jié)點(diǎn)數(shù)的平均值）與狀態(tài)空間樹(shù)上的總結(jié)點(diǎn)數(shù)進(jìn)行比較，由其比值可以初步看出回溯設(shè)計(jì)的效益。在下面的n皇后問(wèn)題的回溯求解時(shí)將具體應(yīng)用以上蒙特卡羅算法估計(jì)回溯設(shè)計(jì)的效益。5.8 回溯應(yīng)用小結(jié)本章應(yīng)用回溯設(shè)計(jì)求解了逐位整除數(shù)與橋本分?jǐn)?shù)式等涉及數(shù)與數(shù)式的典型案例、求解了新穎的素?cái)?shù)環(huán)與德布魯金環(huán)等環(huán)序列，求解了直尺刻度分布與數(shù)碼串珠等趣題，也求解了伯努利裝錯(cuò)信封問(wèn)題與別出心裁的情侶拍照等難度較大的組合案例。可見(jiàn)回溯法的應(yīng)用是非常廣闊的?；厮莘ㄓ小巴ㄓ媒忸}法”之稱，是一種比窮舉“聰明”的搜索技術(shù)，在搜索過(guò)程中動(dòng)態(tài)地產(chǎn)生問(wèn)題的解空間，系統(tǒng)地搜索問(wèn)題的所有解。當(dāng)搜索到解空間樹(shù)的任一結(jié)點(diǎn)時(shí)，判斷該結(jié)點(diǎn)是否包含問(wèn)題的解。如果該結(jié)點(diǎn)肯定不包含，則“見(jiàn)