算法設(shè)計(jì)與分析--回溯法

《算法設(shè)計(jì)與分析--回溯法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、回溯算法的應(yīng)用課程名稱：算法設(shè)計(jì)與分析院系：計(jì)算機(jī)科學(xué)與信息工程學(xué)院學(xué)生姓名：學(xué)號(hào)：201003010079專業(yè)班級(jí)：計(jì)算機(jī)科學(xué)與技術(shù)（信息技術(shù)）11-1指導(dǎo)教師：馮慧玲2013年12月27口回溯算法的應(yīng)用扌商要：回溯法是一個(gè)既帶有系統(tǒng)性又帶有跳躍性的的搜索算法。它在包含問題的所有解的解空間樹屮，按照深度優(yōu)先的策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任一結(jié)點(diǎn)時(shí)，總是先判斷該結(jié)點(diǎn)是否肯定不包含問題的解。如果肯定不包含，則跳過對(duì)以該結(jié)點(diǎn)為根的子樹的系統(tǒng)搜索，逐層向其祖先結(jié)點(diǎn)回溯。否則，進(jìn)入該子樹,繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索。回溯法在用來

2、求問題的所有解時(shí)，要回溯到根，且根結(jié)點(diǎn)的所有子樹都已被搜索遍才結(jié)束。而回溯法在用來求問題的任一解時(shí)，只要搜索到問題的一個(gè)解就可以結(jié)束。這種以深度優(yōu)先的方式系統(tǒng)地搜索問題的解的算法稱為回溯法，它適用于解一些組合數(shù)較大的問題。在做題吋，有時(shí)會(huì)遇到這樣一?類題目，它的問題可以分解，但是又不能得出明確的動(dòng)態(tài)規(guī)劃或是遞歸解法，此時(shí)可以考慮用回溯法解決此類問題?；厮莘ǖ膬?yōu)點(diǎn)在于其程序結(jié)構(gòu)明確，可讀性強(qiáng)，易于理解，而且通過對(duì)問題的分析可以大大提高運(yùn)行效率。0/1背包問題是一個(gè)經(jīng)典的問題，我們可以采用多種算法去求解0/1背包問題，比如動(dòng)態(tài)規(guī)劃法、分支限界法、貪心

3、算法、回溯法。在這里我們采用回溯法解決這個(gè)問題。關(guān)鍵詞：回溯法0/1背包問題深度優(yōu)先搜索節(jié)點(diǎn)第1章緒論41.1回溯算法的背景知識(shí)41.2回溯法的前景意義4第2章回溯算法的理論知識(shí)52.1問題的解空間樹52.2回溯算法的一般性描述6第3章0/1背包問題73.1問題描述73.2問題分析73.3算法設(shè)計(jì)83.4測(cè)試結(jié)果與分析io第4章n皇后問題114.1問題描述114.2問題分析114.3算法設(shè)計(jì)124.4測(cè)試結(jié)果與分析13第5章結(jié)論14參考文獻(xiàn)15附件15第1章緒論1.1回溯算法的背景知識(shí)回溯算法是嘗試搜索算法中最為基本的算法，在遞歸算法中，其存在的

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

5、徑都代表了一種解的可能。通過深度優(yōu)先搜索這棵樹，枚舉每種可能的解的情況；從而得岀結(jié)果。但是，回溯法中通過構(gòu)造約束函數(shù)，可以大大提升程序效率，因?yàn)樵谏疃葍?yōu)先搜索的過程中，不斷的將每個(gè)解與約束函數(shù)進(jìn)行對(duì)照從而刪除一些不可能的解，這樣就不必繼續(xù)把解的剩余部分列出從而節(jié)省部分時(shí)間。1.2回溯法的前景意義在做題時(shí)，有時(shí)會(huì)遇到這樣一類題口，它的問題可以分解，但是又不能得出明確的動(dòng)態(tài)規(guī)劃或是遞歸解法，此吋可以考慮用冋溯法解決此類問題。冋溯法的優(yōu)點(diǎn)在于其程序結(jié)構(gòu)明確，可讀性強(qiáng)，易于理解，而H通過對(duì)問題的分析可以大大提高運(yùn)行效率。通過運(yùn)用回溯法，可以解決很多問題，

6、譬如我們所熟知的“八皇后問題”、“0/1背包問題”，這只是在教學(xué)階段中的運(yùn)用，在實(shí)際運(yùn)用中回溯法也能起到很大的作用?；厮莘ㄟm用于解決難以歸納一般規(guī)律解法的問題，其適用范圍廣，靈活性大，在解一些列舉方法的問題吋尤其可用。但是，其缺點(diǎn)也是明顯的，即吋間復(fù)雜度較大；因此在采用時(shí)我們應(yīng)該因情況的不同而做出不同的選擇。第2章回溯算法的理論知識(shí)2.1問題的解空間樹對(duì)于0-1背包問題。給定n個(gè)物品，一個(gè)容量為w的背包，每個(gè)物品由重量叫和價(jià)值百描述(1=1,2,3,?n),每個(gè)物品可以選擇放入或不放入背包，試求最佳方案：充分(不要求全部)利用背包的容量，盡可能裝

7、入總價(jià)值量大的物品。n件物品的取舍數(shù)字化為：取標(biāo)識(shí)為1,不取標(biāo)識(shí)為0。則搜索的空間為n元一維數(shù)組(x,x,x,…，x,x),其值從(0,0,0,…，0,0)、(0,0,0,…，0,1)、(0,0,0,…，1,0)、(0,0,0,…，1,1)、…、(1,1,1,…，1,1)o這就是一棵子集數(shù)。例如：當(dāng)n二3吋，其解空間可由2彳個(gè)長(zhǎng)度為3的有序序列組成：{(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)}其中，0表示不裝入，1表示裝入。上述解空間可以利用如下圖所示的完全二叉

8、樹表示：圖2.1完全二叉樹冋溯法是在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根節(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任一