回溯法的效率分析

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

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

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

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

5、一地檢驗其是否滿足D的全部約束，若滿足，則為問題P的一個解。顯然，其計算量圖（g）中，第2個皇后不能放在第1，2，3列，因而放置在第4列上。圖（h）中，第3個皇后放在第1列；第4個皇后不能放置1，2列，于是放置在第3列。這樣經(jīng)以上回溯，得到4皇后問題的一個解：2413。繼續(xù)以上的回溯探索，可得4皇后問題的另一個解：3142。3回溯算法框架描述(1)回溯描述對于一般含參量mn的搜索問題，回溯法框架描述如下：輸入正整數(shù)nm(n≥m)i=1a

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