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

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

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

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

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

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

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

6、譬如我們所熟知的“八皇后問(wèn)題”、“0/1背包問(wèn)題”，這只是在教學(xué)階段中的運(yùn)用，在實(shí)際運(yùn)用中回溯法也能起到很大的作用?；厮莘ㄟm用于解決難以歸納一般規(guī)律解法的問(wèn)題，其適用范圍廣，靈活性大，在解一些列舉方法的問(wèn)題吋尤其可用。但是，其缺點(diǎn)也是明顯的，即吋間復(fù)雜度較大；因此在采用時(shí)我們應(yīng)該因情況的不同而做出不同的選擇。第2章回溯算法的理論知識(shí)2.1問(wèn)題的解空間樹(shù)對(duì)于0-1背包問(wèn)題。給定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、樹(shù)表示：圖2.1完全二叉樹(shù)冋溯法是在包含問(wèn)題的所有解的解空間樹(shù)中，按照深度優(yōu)先的策略，從根節(jié)點(diǎn)出發(fā)搜索解空間樹(shù)。算法搜索至解空間樹(shù)的任一