算法設(shè)計與--回溯法

1、回溯算法的應(yīng)用課程名稱： 算法設(shè)計與分析 院 系： 學(xué)生姓名： 學(xué) 號： 專業(yè)班級： 指導(dǎo)教師： 2013年12月27日回溯算法的應(yīng)用摘 要：回溯法是一個既帶有系統(tǒng)性又帶有跳躍性的的搜索算法。它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任一結(jié)點(diǎn)時，總是先判斷該結(jié)點(diǎn)是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結(jié)點(diǎn)為根的子樹的系統(tǒng)搜索，逐層向其祖先結(jié)點(diǎn)回溯。否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索?；厮莘ㄔ谟脕砬髥栴}的所有解時，要回溯到根，且根結(jié)點(diǎn)的所有子樹都已被搜索遍才結(jié)束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個

2、解就可以結(jié)束。這種以深度優(yōu)先的方式系統(tǒng)地搜索問題的解的算法稱為回溯法，它適用于解一些組合數(shù)較大的問題?；厮莘ㄔ谟脕砬髥栴}的所有解時，要回溯到根，且根結(jié)點(diǎn)的所有可行的子樹都已被搜索遍才結(jié)束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個解就可以結(jié)束。這就是以深度優(yōu)先的方式系統(tǒng)地搜索問題解的回溯算法，它適用于解決一些類似n皇后問題等求解方案問題，也可以解決一些最優(yōu)化問題。在做題時，有時會遇到這樣一類題目，它的問題可以分解，但是又不能得出明確的動態(tài)規(guī)劃或是遞歸解法，此時可以考慮用回溯法解決此類問題。回溯法的優(yōu)點(diǎn)在于其程序結(jié)構(gòu)明確，可讀性強(qiáng)，易于理解，而且通過對問題的分析可以大大提高運(yùn)行效率。

3、關(guān)鍵詞：回溯法 深度優(yōu)先搜索 遞歸目 錄第1章 緒論11.1 回溯算法的背景知識11.2 回溯法的前景意義1第2章 回溯算法的理論知識22.1 回溯算法設(shè)計過程22.2 回溯算法框架22.3 回溯算法的一般性描述4第3章 找n個數(shù)中r個數(shù)的組合問題53.1 問題描述53.2 問題分析53.3 算法設(shè)計53.4 測試結(jié)果與分析6第4章 流水作業(yè)車間調(diào)度問題84.1 問題描述84.2 問題分析84.3 算法設(shè)計84.4 測試結(jié)果與分析10第5章 結(jié)論11參考文獻(xiàn)12第1章 緒論1.1 回溯算法的背景知識 回溯算法是嘗試搜索算法中最為基本的算法，在遞歸算法中，其存在的意義是在遞歸知道可解的最小問題后

4、，逐步返回原問題的過程。實(shí)際上是一個類似于枚舉的搜索嘗試方法，他的主題思想是在搜索嘗試的過程中尋找問題的解，當(dāng)發(fā)現(xiàn)不滿足條件時就回溯返回，嘗試別的路徑。簡單的說就是：從問題的某一種初始狀態(tài)出發(fā)，依次搜尋每一種可能到達(dá)的情況，當(dāng)走到這條路的“盡頭”時，回過頭到上一個情況，看這個情況是否還有沒有走過的路，依次進(jìn)行下去，直到遍歷完所有的情況?；厮莘▽?shí)際上是一種深度優(yōu)先搜索的方式。對于回溯法解決的問題，通常將其解空間組織成圖或者樹的形式。對于用回溯法求解的問題，首先要將問題進(jìn)行適當(dāng)?shù)霓D(zhuǎn)化，得出狀態(tài)空間樹。這棵樹的每條完整路徑都代表了一種解的可能。通過深度優(yōu)先搜索這棵樹，枚舉每種可能的解的情況；從而得出

5、結(jié)果。但是，回溯法中通過構(gòu)造約束函數(shù)，可以大大提升程序效率，因?yàn)樵谏疃葍?yōu)先搜索的過程中，不斷的將每個解與約束函數(shù)進(jìn)行對照從而刪除一些不可能的解，這樣就不必繼續(xù)把解的剩余部分列出從而節(jié)省部分時間。1.2 回溯法的前景意義在做題時，有時會遇到這樣一類題目，它的問題可以分解，但是又不能得出明確的動態(tài)規(guī)劃或是遞歸解法，此時可以考慮用回溯法解決此類問題?；厮莘ǖ膬?yōu)點(diǎn)在于其程序結(jié)構(gòu)明確，可讀性強(qiáng)，易于理解，而且通過對問題的分析可以大大提高運(yùn)行效率。通過運(yùn)用回溯法，可以解決很多問題，譬如我們所熟知的“八皇后問題”、“0/1背包問題”，這只是在教學(xué)階段中的運(yùn)用，在實(shí)際運(yùn)用中回溯法也能起到很大的作用。回溯法適用

6、于解決難以歸納一般規(guī)律解法的問題，其適用范圍廣，靈活性大，在解一些列舉方法的問題時尤其可用。但是，其缺點(diǎn)也是明顯的，即時間復(fù)雜度較大；因此在采用時我們應(yīng)該因情況的不同而做出不同的選擇。第2章 回溯算法的理論知識2.1 回溯算法設(shè)計過程 （1）確定問題的解空間應(yīng)用回溯法解問題時，首先應(yīng)明確定義問題的解空間。問題的解空間應(yīng)至少包含問題的一個（最優(yōu)）解。 （2）確定結(jié)點(diǎn)的擴(kuò)展規(guī)則，如每個皇后在一行中的不同位置移動，而象棋中的馬只能走“日”字等。 （3）搜索解空間 回溯算法從開始結(jié)點(diǎn)（根結(jié)點(diǎn)）出發(fā)，以深度優(yōu)先的方式搜索整個解空間。這個開始結(jié)點(diǎn)就成為一個活結(jié)點(diǎn)，同時也成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。在當(dāng)前的擴(kuò)展結(jié)點(diǎn)

7、處，搜索向縱深方向移至一個新結(jié)點(diǎn)。這個新結(jié)點(diǎn)就成為一個新的活結(jié)點(diǎn)，并成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。如果在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處不能再向縱深方向移動，則當(dāng)前擴(kuò)展結(jié)點(diǎn)就成為死結(jié)點(diǎn)。此時，應(yīng)往回移動（回溯）至最近的一個活結(jié)點(diǎn)處，并使這個活結(jié)點(diǎn)成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)?；厮莘匆赃@種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結(jié)點(diǎn)時為止。2.2 回溯算法框架（1）問題框架設(shè)問題的解是一個n維向量（a1,a2,.,an），約束條件是ai(i=1,2,3, .,n)之間滿足某種條件，記為f(ai)。（2） 非遞歸回溯框架 int an,i; 初始化數(shù)組a; i=1; While(i0(有路可走)）and(未

8、到達(dá)目標(biāo)) /還未回溯到頭 if（in） /搜索到葉結(jié)點(diǎn) 搜索到一個解，輸出； else /正在處理第i個元素 ai第一個可能的值； while(ai在不滿足約束條件且在搜索空間內(nèi)) ai下一個可能的值； if（ai在搜索空間內(nèi)） 標(biāo)識占用的資源； i=i+1; /擴(kuò)展下一個結(jié)點(diǎn) else 清理所占的狀態(tài)空間； /回溯 i=i-1; (3)遞歸算法框架回溯法是對解空間的深度優(yōu)先搜索，在一般情況下用遞歸函數(shù)來實(shí)現(xiàn)回溯法比較簡單，其中i為搜索深度，框架如下：int an;try(int i)if(in) 輸出結(jié)果；else for(j=下界；j=上界;j+) if(f(j) ai=j; . try

9、(i+1); 回溯前的清理工作（如ai置空值等）； 2.3 回溯算法的一般性描述回溯法的一般描述可用回溯法求解的問題P，通常要能表達(dá)為：對于已知的由n元組（x1，x2，xn）組成的一個狀態(tài)空間E=（x1，x2，xn）xiSi ，i=1，2，n，給定關(guān)于n元組中的一個分量的一個約束集D，要求E中滿足D的全部約束條件的所有n元組。其中Si是分量xi的定義域，且 |Si| 有限，i=1，2，n。我們稱E中滿足D的全部約束條件的任一n元組為問題P的一個解。解問題P的最樸素的方法就是枚舉法，即對E中的所有n元組逐一地檢測其是否滿足D的全部約束，若滿足，則為問題P的一個解。但顯然，其計算量是相當(dāng)大的。我們

10、發(fā)現(xiàn)，對于許多問題，所給定的約束集D具有完備性，即i元組（x1，x2，xi）滿足D中僅涉及到x1，x2，xi的所有約束意味著j（j=i）元組（x1，x2，xj）一定也滿足D中僅涉及到x1，x2，xj的所有約束，i=1，2，n。換句話說，只要存在0jn-1，使得（x1，x2，xj）違反D中僅涉及到x1，x2，xj的約束之一，則以（x1，x2，xj）為前綴的任何n元組（x1，x2，xj，xj+1，xn）一定也違反D中僅涉及到x1，x2，xi的一個約束，nij。因此，對于約束集D具有完備性的問題P，一旦檢測斷定某個j元組（x1，x2，xj）違反D中僅涉及x1，x2，xj的一個約束，就可以肯定，以（x

11、1，x2，xj）為前綴的任何n元組（x1，x2，xj，xj+1，xn）都不會是問題P的解，因而就不必去搜索它們、檢測它們?；厮莘ㄕ轻槍@類問題，利用這類問題的上述性質(zhì)而提出來的比枚舉法效率更高的算法。第3章 找n個數(shù)中r個數(shù)的組合問題3.1 問題描述回溯搜索解找n個數(shù)中r個數(shù)的組合問題3.2 問題分析 遞歸算法是找大規(guī)模問題和小規(guī)模問題的關(guān)系，回溯法是對問題的解空間進(jìn)行深度優(yōu)先搜索的算法。必須先確定搜索空間以及約束條件，本題采用回溯搜索算法求解找n個數(shù)中r個數(shù)的組合問題。3.3 算法設(shè)計 不同于遞歸算法，遞歸算法是找大規(guī)模問題和小規(guī)模問題的關(guān)系，回溯法是對問題的解空間進(jìn)行搜索的算法。(1)

12、問題的解空間為一組r元一維向量，（a1,a2,a3,.,ar），1=ai=n，1=i=r+1，若ri+ari 用二維數(shù)組job1002存儲作業(yè)在M1，M2上的加工時間。2 由于f1在計算中，只須當(dāng)前值，所以用變量存儲即可；而f2在計算中，還依賴前一個作業(yè)的數(shù)據(jù)，所以有必要用數(shù)組存儲。(4) 流程圖圖4-1流水作業(yè)調(diào)度主函數(shù)流程圖圖4-2流水作業(yè)調(diào)度try()函數(shù)流程圖圖4-3流水作業(yè)調(diào)度swap()函數(shù)流程圖4.4 測試結(jié)果與分析圖4-4流水作業(yè)車間調(diào)度問題的解 由流水作業(yè)調(diào)度問題分析可知，M1機(jī)器是順序加工，M2機(jī)器在加工時有可能出現(xiàn)空閑或積壓問題，因此當(dāng)數(shù)據(jù)不同時，會根據(jù)此兩種情況進(jìn)行分析

13、處理。第5章 結(jié)論在兩個實(shí)例編程中，總的算法思想都是利用回溯算法求解問題，在n個數(shù)中找出r個數(shù)實(shí)例中，利用遞歸的算法設(shè)計，使算法過程逐步遞歸地回溯，以便簡化問題，進(jìn)行求解問題。在流水作業(yè)調(diào)度問題中，也是利用回溯算法是問題得到最優(yōu)解。 在通過兩個實(shí)例編程后，對回溯算法的思想結(jié)構(gòu)以及求解問題的方法有了更深入的理解，對回溯法的解題框架更清楚了。但在另一方面，也認(rèn)識到自己的不足之處，比如在調(diào)試流水作業(yè)調(diào)度問題時，對swap()函數(shù)沒有調(diào)試，以為只是一個互換函數(shù)，但調(diào)試程序時一直出錯，最后才明白過來，有關(guān)內(nèi)容的交換，必須利用指針進(jìn)行交換。由此，通過兩個實(shí)例的編程，又使自己收獲很多，但還是需要多加學(xué)習(xí)。算

14、法問題的解空間通常是在搜索問題的解的過程中動態(tài)產(chǎn)生的，這是回溯的一個重要特性。具體來說：確定了解空間的組織結(jié)構(gòu)后，回溯法就從開始結(jié)點(diǎn)（根結(jié)點(diǎn)）出發(fā)，以深度優(yōu)先的方式搜索整個解空間。這個開始結(jié)點(diǎn)就成為一個活結(jié)點(diǎn)，同時也成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處，搜索向縱深方向移至一個新結(jié)點(diǎn)。這個新結(jié)點(diǎn)就成為一個新的活結(jié)點(diǎn)，并成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。如果在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處不能再向縱深方向移動，則當(dāng)前擴(kuò)展結(jié)點(diǎn)就成為死結(jié)點(diǎn)。此時，應(yīng)往回移動（回溯）至最近的一個活結(jié)點(diǎn)處，并使這個活結(jié)點(diǎn)成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)?；厮莘匆赃@種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結(jié)點(diǎn)時為止。 參考文獻(xiàn)1 算法設(shè)計與分析（第二版） 呂國英 主編