回溯法的效率分析

1、回溯法概述與窮舉的“笨拙”搜索相比，回溯法則是一種“聰明”的求解效益更高的搜索法。下面介紹回溯設(shè)計(jì)及其應(yīng)用，體會(huì)回溯法相對于窮舉的特點(diǎn)與優(yōu)勢?；厮莸母拍钣性S多問題，當(dāng)需要找出它的解集或者要求回答什么解是滿足某些約束條件的最佳解時(shí)，往往使用回溯法?；厮莘ㄊ且环N試探求解的方法：通過對問題的歸納分析，找出求解問題的一個(gè)線索，沿著這一線索往前試探，若試探成功，即得到解；若試探失敗，就逐步往回退，換其他路線再往前試探。因此，回溯法可以形象地概括為

2、“向前走，碰壁回頭”?；厮莘ǖ幕咀龇ㄊ窃囂剿阉?，是一種組織得井井有條的、能避免一些不必要搜索的窮舉式搜索法?；厮莘ㄔ趩栴}的解空間樹中，從根結(jié)點(diǎn)出發(fā)搜索解空間樹，搜索至解空間樹的任意一點(diǎn)，先判斷該結(jié)點(diǎn)是否包含問題的解；如果肯定不包含，則跳過對該結(jié)點(diǎn)為根的子樹的搜索，逐層向其父結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)搜索。從解的角度理解，回溯法將問題的候選解按某種順序進(jìn)行枚舉和檢驗(yàn)。當(dāng)發(fā)現(xiàn)當(dāng)前候選解不可能是解時(shí)，就選擇下一個(gè)候選解。在回溯法中，放

3、棄當(dāng)前候選解，尋找下一個(gè)候選解的過程稱為回溯。倘若當(dāng)前候選解除了不滿足問題規(guī)模要求外，滿足所有其他要求時(shí)，繼續(xù)擴(kuò)大當(dāng)前候選解的規(guī)模，并繼續(xù)試探。如果當(dāng)前候選解滿足包括問題規(guī)模在內(nèi)的所有要求時(shí)，該候選解就是問題的一個(gè)解。與窮舉法相比，回溯法的“聰明”之處在于能適時(shí)“回頭”，若再往前走不可能得到解，就回溯，退一步另找線路，這樣可省去大量的無效操作。因此，回溯與窮舉相比，回溯更適宜于量比較大，候選解比較多的問題。5.1.2回溯描述1回溯的一般

4、方法下面簡要闡述回溯的一般方法?；厮萸蠼獾膯栴}P，通常要能表達(dá)為：對于已知的由n元組(x1x2…xn)組成的一個(gè)狀態(tài)空間E=(x1x2…xn)|xi∈sii=12…n，給定關(guān)于n元組中的一個(gè)分量的一個(gè)約束集D，要求E中滿足D的全部約束條件的所有n元組。其中si是分量xi的定義域，且|si|有限，i=12…n。稱E中滿足D的全部約束條件的任一n元組為問題P的一個(gè)解。解問題P的最樸素的方法就是窮舉法，上面已經(jīng)作了介紹，即對E中的所有n元組逐

5、一地檢驗(yàn)其是否滿足D的全部約束，若滿足，則為問題P的一個(gè)解。顯然，其計(jì)算量圖（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回溯算法框架描述(1)回溯描述對于一般含參量mn的搜索問題，回溯法框架描述如下：輸入正整數(shù)nm(n≥m)i=1a

6、[i]=while(1)f(g=1k=i1k=1k)if()g=0檢測約束條件不滿足則返回if(g輸出一個(gè)解if(icontinuewhile(a[i]==向前回溯if(a[i]==n退出循環(huán)，結(jié)束elsea[i]=a[i]1具體求解問題的試探搜索范圍與要求不同，在應(yīng)用回溯設(shè)計(jì)時(shí)，需根據(jù)問題的具體實(shí)際確定數(shù)組元素的初值、取值點(diǎn)與回溯點(diǎn)，同時(shí)需把問題中的約束條件進(jìn)行必要的分解，以適應(yīng)上述回溯流程。其中實(shí)施向前回溯的循環(huán)while(a[i]