資源描述：
《回溯法的效率分析》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、回溯法概述與窮舉的“笨拙”搜索相比，回溯法則是一種“聰明”的求解效益更高的搜索法。下面介紹回溯設(shè)計(jì)及其應(yīng)用，體會(huì)回溯法相對(duì)于窮舉的特點(diǎn)與優(yōu)勢。回溯的概念有許多問題，當(dāng)需要找出它的解集或者要求回答什么解是滿足某些約束條件的最佳解時(shí)，往往使用回溯法?；厮莘ㄊ且环N試探求解的方法：通過對(duì)問題的歸納分析，找出求解問題的一個(gè)線索，沿著這一線索往前試探，若試探成功，即得到解；若試探失敗，就逐步往回退，換其他路線再往前試探。因此，回溯法可以形象地概括為“向前走，碰壁回頭”。回溯法的基本做法是試探搜索，是一種組織得井井有條的、能避免一些不必要搜索的窮舉式搜索法。回溯
2、法在問題的解空間樹中，從根結(jié)點(diǎn)出發(fā)搜索解空間樹，搜索至解空間樹的任意一點(diǎn)，先判斷該結(jié)點(diǎn)是否包含問題的解；如果肯定不包含，則跳過對(duì)該結(jié)點(diǎn)為根的子樹的搜索，逐層向其父結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)搜索。從解的角度理解，回溯法將問題的候選解按某種順序進(jìn)行枚舉和檢驗(yàn)。當(dāng)發(fā)現(xiàn)當(dāng)前候選解不可能是解時(shí)，就選擇下一個(gè)候選解。在回溯法中，放棄當(dāng)前候選解，尋找下一個(gè)候選解的過程稱為回溯。倘若當(dāng)前候選解除了不滿足問題規(guī)模要求外，滿足所有其他要求時(shí)，繼續(xù)擴(kuò)大當(dāng)前候選解的規(guī)模，并繼續(xù)試探。如果當(dāng)前候選解滿足包括問題規(guī)模在內(nèi)的所有要求時(shí)，該候選解就是問題的一個(gè)解。與窮舉法相
3、比，回溯法的“聰明”之處在于能適時(shí)“回頭”，若再往前走不可能得到解，就回溯，退一步另找線路，這樣可省去大量的無效操作。因此，回溯與窮舉相比，回溯更適宜于量比較大，候選解比較多的問題。5.1.2回溯描述1．回溯的一般方法下面簡要闡述回溯的一般方法?；厮萸蠼獾膯栴}P，通常要能表達(dá)為：對(duì)于已知的由n元組(x1,x2,…,xn)組成的一個(gè)狀態(tài)空間E={(x1,x2,…,xn)
4、xi∈si,i=1,2,…,n}，給定關(guān)于n元組中的一個(gè)分量的一個(gè)約束集D，要求E中滿足D的全部約束條件的所有n元組。其中si是分量xi的定義域，且
5、si
6、有限，i=1,2,…,n。
7、稱E中滿足D的全部約束條件的任一n元組為問題P的一個(gè)解。解問題P的最樸素的方法就是窮舉法，上面已經(jīng)作了介紹，即對(duì)E中的所有n元組逐一地檢驗(yàn)其是否滿足D的全部約束，若滿足，則為問題P的一個(gè)解。顯然，其計(jì)算量是相當(dāng)大的。對(duì)于許多問題，所給定的約束集D具有完備性，即i元組(x1,x2,…,xi)滿足D中僅涉及到x1,x2,…,xi的所有約束，意味著j(j8、j的約束之一，則以(x1,x2,…,xj)為前綴的任何n元組(x1,x2,…,xj,xj+1,…,xn)也一定違反D中僅涉及到x1,x2,…,xj的一個(gè)約束，n≥i＞j。因此，對(duì)于約束集D具有完備性的問題P，一旦檢測斷定某個(gè)j元組(x1,x2,…,xj)違反D中僅涉及x1,x2,…,xj的一個(gè)約束，就可以肯定，以(x1,x2,…,xj)為前綴的任何n元組(x1,x2,…,xj,xj+1,…,xn)都不會(huì)是問題P的解，因而就不必去搜索它們，即省略了對(duì)部分元素(xj+1,…,xn)的操作與測試?；厮莘ㄕ轻槍?duì)這類問題，利用這類問題的上述性質(zhì)而提出來的比
9、窮舉法效率更高的算法。2.4皇后問題的回溯實(shí)施為了具體說明回溯的實(shí)施過程，先看一個(gè)簡單實(shí)例。如何在4×4的方格棋盤上放置4個(gè)皇后，使它們互不攻擊，即任意兩個(gè)皇后不允許處在同一橫排，同一縱列，也不允許處在同一與棋盤邊框成45°角的斜線上。圖5-1所示為應(yīng)用回溯的實(shí)施過程，其中方格中的×表示試圖在該方格放置一個(gè)皇后,但由于受前面已放置的皇后的攻擊而放棄的位置。圖5-14皇后問題回溯實(shí)施求解圖（a）為在第1行第1列放置一個(gè)皇后的初始狀態(tài)。圖（b）中，第2個(gè)皇后不能放在第1、2列，因而放置在第3列上。圖（c）中，表示第3行的所有各列均不能放置皇后，則返回第
10、2行，第2個(gè)皇后需后移。圖（d）中，第2個(gè)皇后后移到第4列，第3個(gè)皇后放置在第2列。圖（e）中，第4行的所有各列均不能放置皇后，則返回第3行；第3個(gè)皇后后移的所有位置均不能放置皇后，則返回第2行；第2個(gè)皇后已無位可退，則返回第1行；第1個(gè)皇后需后移。圖（f）中，第1個(gè)皇后后移至第2格。圖（g）中，第2個(gè)皇后不能放在第1，2，3列，因而放置在第4列上。圖（h）中，第3個(gè)皇后放在第1列；第4個(gè)皇后不能放置1，2列，于是放置在第3列。這樣經(jīng)以上回溯，得到4皇后問題的一個(gè)解：2413。繼續(xù)以上的回溯探索，可得4皇后問題的另一個(gè)解：3142。3．回溯算法框架
11、描述(1)回溯描述對(duì)于一般含參量m,n的搜索問題，回溯法框架描述如下：輸入正整數(shù)n,m,(n≥m)i=1;a[i]=<元素
