回溯法回溯法的分析與應(yīng)用大學(xué)論文.doc

《回溯法回溯法的分析與應(yīng)用大學(xué)論文.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、算法創(chuàng)新與實(shí)踐論文沈陽理工大學(xué)算法實(shí)踐與創(chuàng)新論文題目回溯法的分析與應(yīng)用學(xué)生姓名：學(xué)號(hào)：學(xué)生姓名：學(xué)號(hào)：學(xué)生姓名：學(xué)號(hào)：24算法創(chuàng)新與實(shí)踐論文摘要對(duì)于計(jì)算機(jī)科學(xué)來說，算法的概念是至關(guān)重要的，算法是一系列解決問題的清晰指令，也就是說，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時(shí)間內(nèi)獲得所要求的輸出。為了更加的了解算法，本篇論文中，我們先研究一個(gè)算法---回溯法?；厮莘ㄊ且环N常用的重要的基本設(shè)計(jì)方法。它的基本做法是在可能的范圍之內(nèi)搜索，適于解一些組合數(shù)相當(dāng)大的問題。圓排列描述的是在給定n個(gè)大小不等的圓C1,C2,?,Cn,現(xiàn)要將這n個(gè)圓排進(jìn)一個(gè)矩形

2、框中，且要求各圓與矩形框的底邊相切。圓排列問題要求從n個(gè)圓的所有排列中找出有最小長(zhǎng)度的圓排列。圖著色問題用數(shù)學(xué)定義就是給定一個(gè)無向圖G=（V,E），其中V為頂點(diǎn)集合，E為邊集合，圖著色問題即為將V分為K個(gè)顏色組，每個(gè)組形成一個(gè)獨(dú)立集，即其中沒有相鄰的頂點(diǎn)。其優(yōu)化版本是希望獲得最小的K值。符號(hào)三角形問題要求對(duì)于給定的n，計(jì)算有多少個(gè)不同的符號(hào)三角形，使其所含的“+”和“-”的個(gè)數(shù)相同。在本篇論文中，我們將運(yùn)用回溯法來解決著圖的著色問題，符號(hào)三角形問題，圖排列問題，將此三個(gè)問題進(jìn)行深入的探討。關(guān)鍵詞:回溯法圖的著色問題符號(hào)三角形問題

3、圖排列問題I24算法創(chuàng)新與實(shí)踐論文目錄第1章引言1第2章回溯法的背景2第3章圖的著色問題43.1問題描述43.2四色猜想43.3算法設(shè)計(jì)53.4源代碼63.5運(yùn)行結(jié)果圖10第4章符號(hào)三角形問題114.1問題描述114.2算法設(shè)計(jì)114.3源代碼124.4運(yùn)行結(jié)果圖16第5章圓的排列問題175.1問題描述175.2問題分析175.3源代碼185.4運(yùn)行結(jié)果圖22結(jié)論23參考文獻(xiàn)24II24算法創(chuàng)新與實(shí)踐論文第1章引言在現(xiàn)實(shí)世界中，有相當(dāng)一類問題試求問題的全部解或求問題的最優(yōu)解。最基本的方法是通過枚舉法搜索問題的解空間。但許多問題解

4、空間的大小隨問題規(guī)模n的增長(zhǎng)呈指數(shù)規(guī)律增長(zhǎng)，這就使問題理論上可解而實(shí)際不可行。為了使搜索空間減少到盡可能小，就需要采用良好的搜索技術(shù)。回溯法就是一種較好的搜索技術(shù)。回溯法又稱為試探法，它是一種有效的試探回溯搜索技術(shù)。即運(yùn)用回溯法求解問題不是基于某種確定的法則，而是通過大量反復(fù)的試探和回溯。它的基本做法是搜索，能避免不必要搜素的窮舉式搜索?；厮莘ㄔ趩栴}的解空間樹中按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹，算法搜索至解空間樹的任意一點(diǎn)時(shí)，先判斷該節(jié)點(diǎn)是否包含問題的解，如果肯定不包含，則跳過對(duì)該結(jié)點(diǎn)為根的子樹的搜索，逐層向其祖先結(jié)點(diǎn)回

5、溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。簡(jiǎn)單地說，采用回溯法求解問題的整個(gè)過程貫穿了搜索---試探—決定回溯或前進(jìn)這三種基本運(yùn)算。通過運(yùn)用回溯法，可以解決很多問題，譬如我們所熟知的“八皇后問題”，“0/1背包問題”，這只是在教學(xué)階段中的運(yùn)用，在實(shí)際運(yùn)用中也產(chǎn)生很大的作用在學(xué)習(xí)過程中，我們會(huì)遇到這樣的問題，讓我們?nèi)ふ医o定問題的解集或者讓我們找出滿足某些約束條件的最優(yōu)解，這時(shí)候我們就可以采用回溯法來解決這一類的問題。通過運(yùn)用回溯法，可以解決很多問題，譬如我們所熟知的“八皇后問題”，“0/1背包問題”，這只是在教學(xué)階段中的運(yùn)用

6、，在實(shí)際運(yùn)用中也產(chǎn)生很大的作用回溯法的優(yōu)點(diǎn)是容易理解，可行性比較強(qiáng)。[1]原福永算法設(shè)計(jì)與分析.機(jī)械工業(yè)出版社，1998；P213-21424算法創(chuàng)新與實(shí)踐論文第2章回溯法的背景回溯法是一種窮舉類型的算法，與其說它是一種算法，倒不如說它是一種試法。回溯法并沒有什么高深的算法思想，雖然名字起的很高規(guī)格，但其實(shí)它的算法性連二分查找都比不上。這里說的算法性其實(shí)就是指技巧性，對(duì)問題特性了解越深入，越能創(chuàng)造出很巧妙的算法，在時(shí)間復(fù)雜度的級(jí)別上提高算法效率。這體現(xiàn)了算法效率與適用性之間的矛盾，二分查找效率很高，但適用性比較低，類似的還有著名

7、的KMP算法。而窮舉法效率最低，但幾乎適用于所有問題。。回溯法是一種試探性算法，從這一點(diǎn)上看，它很像窮舉法。但它終究不是窮舉法，回溯法是有組織的進(jìn)行窮舉，在試探過程中不斷通過題設(shè)要求減少搜索空間，而這種減少不是一個(gè)一個(gè)解的減少，而是對(duì)搜索空間進(jìn)行大規(guī)模剪枝，從而使得實(shí)際搜索空間遠(yuǎn)遠(yuǎn)小于問題的解空間，所以回溯法的實(shí)際運(yùn)行效率還是比較高的?；厮莘ǖ膽?yīng)用背景說大很大，說小很小。算法大都在“不得不”的情況下才會(huì)使用，如果有別的算法，那它很有可能比回溯法高效，別忘了，回溯法是基于窮舉的。回溯法適用于解排列組合類問題，也就是說目標(biāo)解是從一個(gè)

8、候選空間中選擇出來的。從數(shù)量級(jí)上考慮，設(shè)候選空間的大小為n，如果選擇是可重復(fù)的，那生成的搜索樹為完全n叉樹，搜索空間為n^n（如0-1背包問題，生成的解空間為高度為n完全二叉樹，其中n為物體個(gè)數(shù)）。如果選擇不能重復(fù)，那生成的解空間為n!(如TSP問題生成的解空間