資源描述：
《算法設(shè)計與分析--回溯法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、回溯算法的應(yīng)用課程名稱：算法設(shè)計與分析院系：計算機(jī)科學(xué)與信息工程學(xué)院學(xué)生姓名：學(xué)號：201003010079專業(yè)班級：計算機(jī)科學(xué)與技術(shù)（信息技術(shù)）11-1指導(dǎo)教師：馮慧玲2013年12月27口回溯算法的應(yīng)用扌商要：回溯法是一個既帶有系統(tǒng)性又帶有跳躍性的的搜索算法。它在包含問題的所有解的解空間樹屮，按照深度優(yōu)先的策略，從根結(jié)點出發(fā)搜索解空間樹。算法搜索至解空間樹的任一結(jié)點時，總是先判斷該結(jié)點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結(jié)點為根的子樹的系統(tǒng)搜索，逐層向其祖先結(jié)點回溯。否則，進(jìn)入該子樹,繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索。回溯法在用來
2、求問題的所有解時，要回溯到根，且根結(jié)點的所有子樹都已被搜索遍才結(jié)束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個解就可以結(jié)束。這種以深度優(yōu)先的方式系統(tǒng)地搜索問題的解的算法稱為回溯法，它適用于解一些組合數(shù)較大的問題。在做題吋，有時會遇到這樣一?類題目，它的問題可以分解，但是又不能得出明確的動態(tài)規(guī)劃或是遞歸解法，此時可以考慮用回溯法解決此類問題?；厮莘ǖ膬?yōu)點在于其程序結(jié)構(gòu)明確，可讀性強(qiáng)，易于理解，而且通過對問題的分析可以大大提高運行效率。0/1背包問題是一個經(jīng)典的問題，我們可以采用多種算法去求解0/1背包問題，比如動態(tài)規(guī)劃法、分支限界法、貪心
3、算法、回溯法。在這里我們采用回溯法解決這個問題。關(guān)鍵詞：回溯法0/1背包問題深度優(yōu)先搜索節(jié)點第1章緒論41.1回溯算法的背景知識41.2回溯法的前景意義4第2章回溯算法的理論知識52.1問題的解空間樹52.2回溯算法的一般性描述6第3章0/1背包問題73.1問題描述73.2問題分析73.3算法設(shè)計83.4測試結(jié)果與分析io第4章n皇后問題114.1問題描述114.2問題分析114.3算法設(shè)計124.4測試結(jié)果與分析13第5章結(jié)論14參考文獻(xiàn)15附件15第1章緒論1.1回溯算法的背景知識回溯算法是嘗試搜索算法中最為基本的算法，在遞歸算法中，其存在的
4、意義是在遞歸知道可解的最小問題后，逐步返回原問題的過程。實際上是一個類似于枚舉的搜索嘗試方法，他的主題思想是在搜索嘗試的過程中尋找問題的解，當(dāng)發(fā)現(xiàn)不滿足條件時就回溯返冋，嘗試別的路徑。簡單的說就是：從問題的某一種初始狀態(tài)出發(fā)，依次搜尋每一種可能到達(dá)的情況，當(dāng)走到這條路的“盡頭”時，回過頭到上一個情況，看這個情況是否還有沒有走過的路,依次進(jìn)行下去，直到遍歷完所有的情況?；厮莘▽嶋H上是一種深度優(yōu)先搜索的方式。對于回溯法解決的問題，通常將其解空間組織成圖或者樹的形式。對于用冋溯法求解的問題，首先要將問題進(jìn)行適當(dāng)?shù)霓D(zhuǎn)化，得出狀態(tài)空間樹。這棵樹的每條完整路
5、徑都代表了一種解的可能。通過深度優(yōu)先搜索這棵樹，枚舉每種可能的解的情況；從而得岀結(jié)果。但是，回溯法中通過構(gòu)造約束函數(shù)，可以大大提升程序效率，因為在深度優(yōu)先搜索的過程中，不斷的將每個解與約束函數(shù)進(jìn)行對照從而刪除一些不可能的解，這樣就不必繼續(xù)把解的剩余部分列出從而節(jié)省部分時間。1.2回溯法的前景意義在做題時，有時會遇到這樣一類題口，它的問題可以分解，但是又不能得出明確的動態(tài)規(guī)劃或是遞歸解法，此吋可以考慮用冋溯法解決此類問題。冋溯法的優(yōu)點在于其程序結(jié)構(gòu)明確，可讀性強(qiáng)，易于理解，而H通過對問題的分析可以大大提高運行效率。通過運用回溯法，可以解決很多問題，
6、譬如我們所熟知的“八皇后問題”、“0/1背包問題”，這只是在教學(xué)階段中的運用，在實際運用中回溯法也能起到很大的作用。回溯法適用于解決難以歸納一般規(guī)律解法的問題，其適用范圍廣，靈活性大，在解一些列舉方法的問題吋尤其可用。但是，其缺點也是明顯的，即吋間復(fù)雜度較大；因此在采用時我們應(yīng)該因情況的不同而做出不同的選擇。第2章回溯算法的理論知識2.1問題的解空間樹對于0-1背包問題。給定n個物品，一個容量為w的背包，每個物品由重量叫和價值百描述(1=1,2,3,?n),每個物品可以選擇放入或不放入背包，試求最佳方案：充分(不要求全部)利用背包的容量，盡可能裝
7、入總價值量大的物品。n件物品的取舍數(shù)字化為：取標(biāo)識為1,不取標(biāo)識為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彳個長度為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é)點出發(fā)搜索解空間樹。算法搜索至解空間樹的任一
