資源描述：
《本科畢業(yè)設(shè)計論文--回溯法回溯法的分析與應(yīng)用.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、算法創(chuàng)新與實踐論文沈陽理工大學(xué)算法實踐與創(chuàng)新論文題目回溯法的分析與應(yīng)用學(xué)生姓名：學(xué)號：學(xué)生姓名：學(xué)號：學(xué)生姓名：學(xué)號：24算法創(chuàng)新與實踐論文摘要對于計算機科學(xué)來說，算法的概念是至關(guān)重要的，算法是一系列解決問題的清晰指令，也就是說，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時間內(nèi)獲得所要求的輸出。為了更加的了解算法，本篇論文中，我們先研究一個算法---回溯法。回溯法是一種常用的重要的基本設(shè)計方法。它的基本做法是在可能的范圍之內(nèi)搜索，適于解一些組合數(shù)相當(dāng)大的問題。圓排列描述的是在給定n個大小不等的圓C1,C2,?,Cn
2、,現(xiàn)要將這n個圓排進一個矩形框中，且要求各圓與矩形框的底邊相切。圓排列問題要求從n個圓的所有排列中找出有最小長度的圓排列。圖著色問題用數(shù)學(xué)定義就是給定一個無向圖G=（V,E），其中V為頂點集合，E為邊集合，圖著色問題即為將V分為K個顏色組，每個組形成一個獨立集，即其中沒有相鄰的頂點。其優(yōu)化版本是希望獲得最小的K值。符號三角形問題要求對于給定的n，計算有多少個不同的符號三角形，使其所含的“+”和“-”的個數(shù)相同。在本篇論文中，我們將運用回溯法來解決著圖的著色問題，符號三角形問題，圖排列問題，將此三個問題
3、進行深入的探討。關(guān)鍵詞:回溯法圖的著色問題符號三角形問題圖排列問題I24算法創(chuàng)新與實踐論文目錄第1章引言1第2章回溯法的背景2第3章圖的著色問題43.1問題描述43.2四色猜想43.3算法設(shè)計53.4源代碼63.5運行結(jié)果圖10第4章符號三角形問題114.1問題描述114.2算法設(shè)計114.3源代碼124.4運行結(jié)果圖16第5章圓的排列問題175.1問題描述175.2問題分析175.3源代碼185.4運行結(jié)果圖22結(jié)論23參考文獻24II24算法創(chuàng)新與實踐論文第1章引言在現(xiàn)實世界中，有相當(dāng)一類問題試求
4、問題的全部解或求問題的最優(yōu)解。最基本的方法是通過枚舉法搜索問題的解空間。但許多問題解空間的大小隨問題規(guī)模n的增長呈指數(shù)規(guī)律增長，這就使問題理論上可解而實際不可行。為了使搜索空間減少到盡可能小，就需要采用良好的搜索技術(shù)。回溯法就是一種較好的搜索技術(shù)。回溯法又稱為試探法，它是一種有效的試探回溯搜索技術(shù)。即運用回溯法求解問題不是基于某種確定的法則，而是通過大量反復(fù)的試探和回溯。它的基本做法是搜索，能避免不必要搜素的窮舉式搜索?；厮莘ㄔ趩栴}的解空間樹中按深度優(yōu)先策略，從根結(jié)點出發(fā)搜索解空間樹，算法搜索至解空間
5、樹的任意一點時，先判斷該節(jié)點是否包含問題的解，如果肯定不包含，則跳過對該結(jié)點為根的子樹的搜索，逐層向其祖先結(jié)點回溯；否則，進入該子樹，繼續(xù)按深度優(yōu)先策略搜索。簡單地說，采用回溯法求解問題的整個過程貫穿了搜索---試探—決定回溯或前進這三種基本運算。通過運用回溯法，可以解決很多問題，譬如我們所熟知的“八皇后問題”，“0/1背包問題”，這只是在教學(xué)階段中的運用，在實際運用中也產(chǎn)生很大的作用在學(xué)習(xí)過程中，我們會遇到這樣的問題，讓我們?nèi)ふ医o定問題的解集或者讓我們找出滿足某些約束條件的最優(yōu)解，這時候我們就可以
6、采用回溯法來解決這一類的問題。通過運用回溯法，可以解決很多問題，譬如我們所熟知的“八皇后問題”，“0/1背包問題”，這只是在教學(xué)階段中的運用，在實際運用中也產(chǎn)生很大的作用回溯法的優(yōu)點是容易理解，可行性比較強。[1]原福永算法設(shè)計與分析.機械工業(yè)出版社，1998；P213-21424算法創(chuàng)新與實踐論文第2章回溯法的背景回溯法是一種窮舉類型的算法，與其說它是一種算法，倒不如說它是一種試法。回溯法并沒有什么高深的算法思想，雖然名字起的很高規(guī)格，但其實它的算法性連二分查找都比不上。這里說的算法性其實就是指技巧
7、性，對問題特性了解越深入，越能創(chuàng)造出很巧妙的算法，在時間復(fù)雜度的級別上提高算法效率。這體現(xiàn)了算法效率與適用性之間的矛盾，二分查找效率很高，但適用性比較低，類似的還有著名的KMP算法。而窮舉法效率最低，但幾乎適用于所有問題。?；厮莘ㄊ且环N試探性算法，從這一點上看，它很像窮舉法。但它終究不是窮舉法，回溯法是有組織的進行窮舉，在試探過程中不斷通過題設(shè)要求減少搜索空間，而這種減少不是一個一個解的減少，而是對搜索空間進行大規(guī)模剪枝，從而使得實際搜索空間遠(yuǎn)遠(yuǎn)小于問題的解空間，所以回溯法的實際運行效率還是比較高的。
8、回溯法的應(yīng)用背景說大很大，說小很小。算法大都在“不得不”的情況下才會使用，如果有別的算法，那它很有可能比回溯法高效，別忘了，回溯法是基于窮舉的。回溯法適用于解排列組合類問題，也就是說目標(biāo)解是從一個候選空間中選擇出來的。從數(shù)量級上考慮，設(shè)候選空間的大小為n，如果選擇是可重復(fù)的，那生成的搜索樹為完全n叉樹，搜索空間為n^n（如0-1背包問題，生成的解空間為高度為n完全二叉樹，其中n為物體個數(shù)）。如果選擇不能重復(fù)，那生成的解空間為n!(如TSP問題生成的解空間
