回溯法論文-回溯法的分析與應(yīng)用

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

算法創(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è)矩形框中，且要求各圓與矩形框的底邊相切。圓排列問題要求從n個(gè)圓的所有排列中找出有最小長度的圓排列。圖著色問題用數(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)三角形問題圖排列問題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)解。最基本的方法是通過枚舉法搜索問題的解空間。但許多問題解空間的大小隨問題規(guī)模n的增長呈指數(shù)規(guī)律增長，這就使問題理論上可解而實(shí)際不可行。為了使搜索空間減少到盡可能小，就需要采用良好的搜索技術(shù)?；厮莘ň褪且环N較好的搜索技術(shù)。回溯法又稱為試探法，它是一種有效的試探回溯搜索技術(shù)。即運(yùn)用回溯法求解問題不是基于某種確定的法則，而是通過大量反復(fù)的試探和回溯。它的基本做法是搜索，能避免不必要搜素的窮舉式搜索?；厮莘ㄔ趩栴}的解空間樹中按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹，算法搜索至解空間樹的任意一點(diǎn)時(shí)，先判斷該節(jié)點(diǎn)是否包含問題的解，如果肯定不包含，則跳過對(duì)該結(jié)點(diǎn)為根的子樹的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。簡單地說，采用回溯法求解問題的整個(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)用，在實(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)了算法效率與適用性之間的矛盾，二分查找效率很高，但適用性比較低，類似的還有著名的KMP算法。而窮舉法效率最低，但幾乎適用于所有問題。?；厮莘ㄊ且环N試探性算法，從這一點(diǎn)上看，它很像窮舉法。但它終究不是窮舉法，回溯法是有組織的進(jìn)行窮舉，在試探過程中不斷通過題設(shè)要求減少搜索空間，而這種減少不是一個(gè)一個(gè)解的減少，而是對(duì)搜索空間進(jìn)行大規(guī)模剪枝，從而使得實(shí)際搜索空間遠(yuǎn)遠(yuǎn)小于問題的解空間，所以回溯法的實(shí)際運(yùn)行效率還是比較高的。回溯法的應(yīng)用背景說大很大，說小很小。算法大都在“不得不”的情況下才會(huì)使用，如果有別的算法，那它很有可能比回溯法高效，別忘了，回溯法是基于窮舉的?；厮莘ㄟm用于解排列組合類問題，也就是說目標(biāo)解是從一個(gè)候選空間中選擇出來的。從數(shù)量級(jí)上考慮，設(shè)候選空間的大小為n，如果選擇是可重復(fù)的，那生成的搜索樹為完全n叉樹，搜索空間為n^n（如0-1背包問題，生成的解空間為高度為n完全二叉樹，其中n為物體個(gè)數(shù)）。如果選擇不能重復(fù)，那生成的解空間為n!(如TSP問題生成的解空間為n!,其中n為城市個(gè)數(shù))。也就是說，當(dāng)我們通過分析發(fā)現(xiàn)問題的解空間為n^n或者n!時(shí)，那很可能要用到我們的回溯法了。要用回溯法解決問題，那首先要確定問題的狀態(tài)空間樹。這個(gè)并不是很難，就看每一步選擇有多少個(gè)可選值就可以了，第一步有8個(gè)可選值，那樹第一層就有8個(gè)節(jié)點(diǎn)，第二步有5個(gè)可選值，那第一層每個(gè)節(jié)點(diǎn)都有5個(gè)分支，則第二層有8×5=40個(gè)節(jié)點(diǎn)，以此類推……到第n層一共有m1×m2×……×mn個(gè)節(jié)點(diǎn)，其中mi為第i步的可選值的個(gè)數(shù)。[2]王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析.電子工業(yè)出版社，2012；P53-54確定了狀態(tài)空間樹，那下一步就是搜索了。這時(shí)候就體現(xiàn)出回溯法的優(yōu)勢(shì)了，前面不是說了嘛，回溯法的特點(diǎn)就是有規(guī)律、有組織的進(jìn)行搜索，那下面就來看一下回溯法是如何進(jìn)行搜索的：在開始搜索之前，我們先來說一下我們要做的事情，我們要得到一個(gè)解向量solution，每個(gè)分量對(duì)應(yīng)每一步選擇的結(jié)果，顯然這個(gè)解向量的長度應(yīng)該為n（我們采用c語言的標(biāo)準(zhǔn)，下標(biāo)范圍為0到n-1）。好了，現(xiàn)在我們有了一個(gè)狀態(tài)空間樹（邏輯上的，并不用實(shí)現(xiàn)）和一個(gè)解向量（物理上的，要用來裝數(shù)據(jù)24 算法創(chuàng)新與實(shí)踐論文的）?，F(xiàn)在可以開始搜索了，先設(shè)定一個(gè)下標(biāo)r，這個(gè)r就是解向量的下標(biāo)，也用于標(biāo)識(shí)狀態(tài)樹的第r行。先做第一步，令r=0，選solution[0]，也就是從樹的第0行選擇一個(gè)值放入solution[0]，顯然剛開始我們應(yīng)該選擇第一個(gè)，即前面提到的8個(gè)里面的第一個(gè)。然后看這個(gè)半成品解向量是否是可行的，也就是說看看剛才選擇的那個(gè)值是否滿足要求，加入那個(gè)值不滿足要求，那應(yīng)該選擇第二個(gè)，以此類推直到選擇一個(gè)可行的值，放入solution[0]。然后r++進(jìn)行第二步，選擇solution[1]，同樣的，我們應(yīng)該從樹的第二行中選擇第一個(gè)看構(gòu)成的解是否可行（此時(shí)解向量中包含兩個(gè)元素），這樣的步驟一直進(jìn)行下去，直到出現(xiàn)這樣的情況[3]毛靜華，劉麗紅.基于回溯法的案例推理方法研究.《情報(bào)雜志》,2015；P40-41（1）r=n-1了，也就是說我們得到了問題的一個(gè)可行解，這時(shí)候就要看題設(shè)要求了，如果只要求找到一個(gè)可行解，那此時(shí)算法就可以停止了。（2）某一層的候選值選完了，我們知道，沒一層的候選值都有一定個(gè)數(shù)，如上面提到的例子中第二層只有5個(gè)候選值，如果這五個(gè)候選值都試探完了還是沒有可行解那該怎么辦呢？這里體現(xiàn)的思想就是我們回溯法名字的由來，回溯。也就是令r--退回去，從新選擇上面的解。比如上面的例子先選擇8個(gè)中的第一個(gè)作為解的一部分，然后發(fā)現(xiàn)后面的5個(gè)和前面這個(gè)都不能組成可行解，那這就說明前面那個(gè)選擇是不可行的，和后面是不搭配的。所以應(yīng)該返回去選擇8個(gè)中的第二個(gè)，然后再對(duì)5個(gè)進(jìn)行選擇，看哪個(gè)與這個(gè)第二個(gè)想匹配。（3）最后一種情況，因?yàn)槲覀冞@個(gè)過程中有回溯過程，即r--的過程，那可能最后r小于0了，這說明整個(gè)樹都搜索完了，也就是問題沒有可行解。回溯法一般有兩種代碼實(shí)現(xiàn)方案，遞歸方法和非遞歸方法。相比之下，遞歸設(shè)計(jì)方法比較簡單，用前面提到的r作為遞歸變量即可，如果滿足搜索條件，則遞歸調(diào)用r+1對(duì)應(yīng)函數(shù)，如果不滿足，則遞歸調(diào)用r-1對(duì)應(yīng)的函數(shù)。基礎(chǔ)步為當(dāng)r＜0或r=n-1分別對(duì)應(yīng)無解和得到可行解，這個(gè)就不多說了。非遞歸方法，也就是循環(huán)方法設(shè)計(jì)細(xì)節(jié)比較多，但只要掌握了其特點(diǎn)，對(duì)不同問題的適用性很強(qiáng)（即代碼只通過很少的修改就可以應(yīng)用到不同問題），加之其效率高于遞歸算法（循環(huán)的優(yōu)勢(shì)），所以這里我們著重講一下回溯的非遞歸代碼實(shí)現(xiàn)。24 算法創(chuàng)新與實(shí)踐論文第3章圖的著色問題3.1問題描述給定一個(gè)無向連通圖G和m>0種顏色，在只準(zhǔn)使用者m中顏色對(duì)G的結(jié)點(diǎn)重色的情況下，是否能使途中任何相鄰的兩個(gè)結(jié)點(diǎn)都具有不同的顏色嗎?3.2四色猜想四色問題是m圖著色問題的一個(gè)特例，根據(jù)四色原理，證明平面或球面上的任何地圖的所有區(qū)域都至多可用四種、顏色來著色，并使任何兩個(gè)有一段公共邊界的相鄰區(qū)域沒有相同的顏色。這個(gè)問題可轉(zhuǎn)換成對(duì)一平面圖的４－著色判定問題(平面圖是一個(gè)能畫于平面上而邊無任何交叉的圖)。將地圖的每個(gè)區(qū)域變成一個(gè)結(jié)點(diǎn)，若兩個(gè)區(qū)域相鄰，則相應(yīng)的結(jié)點(diǎn)用一條邊連接起來。4352112345多年來，雖然已證明用5種顏色足以對(duì)任一幅地圖著色，但是一直找不到一定要求多于4種顏色的地圖。直到1976年這個(gè)問題才由愛普爾，黑肯和考西利用電子計(jì)算機(jī)的幫助得以解決。他們證明了4種顏色足以對(duì)任何地圖著色。[4]馮俊.算法與程序設(shè)計(jì)基礎(chǔ)教程.清華大學(xué)出版社，2010；P252-256圖圖3-124 算法創(chuàng)新與實(shí)踐論文3.3算法設(shè)計(jì)考慮所有的圖，討論在至多使用m種顏色的情況下，可對(duì)一給定的圖著色的所有不同方法。通過回溯的方法，不斷的為每一個(gè)節(jié)點(diǎn)著色，在前面n-1個(gè)節(jié)點(diǎn)都合法的著色之后，開始對(duì)第n個(gè)節(jié)點(diǎn)進(jìn)行著色，這時(shí)候枚舉可用的m個(gè)顏色，通過和第n個(gè)節(jié)點(diǎn)相鄰的節(jié)點(diǎn)的顏色，來判斷這個(gè)顏色是否合法，如果找到那么一種顏色使得第n個(gè)節(jié)點(diǎn)能夠著色，那么說明m種顏色的方案是可行的。用m種顏色為無向圖G=(V,E)著色，其中，V的頂點(diǎn)個(gè)數(shù)為n，可以用一個(gè)n元組x=(x1,x2,…,xn)來描述圖的一種可能著色，其中，xi∈{1,2,…,m}，(1≤i≤n)表示賦予頂點(diǎn)i的顏色。例如，5元組(1,2,2,3,1)表示對(duì)具有5個(gè)頂點(diǎn)的無向圖（a）的一種著色，頂點(diǎn)A著顏色1，頂點(diǎn)B著顏色2，頂點(diǎn)C著顏色2，如此等等。如果在n元組X中，所有相鄰頂點(diǎn)都不會(huì)著相同顏色，就稱此n元組為可行解，否則為無效解。容易看出，每個(gè)頂點(diǎn)可著顏色有m種選擇，n個(gè)頂點(diǎn)就有mn種不同的著色方案，問題的解空間是一棵高度為n的完全m叉樹，這里樹高度的定義為從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑的長度。每個(gè)分支結(jié)點(diǎn)，都有m個(gè)兒子結(jié)點(diǎn)。最底層有mn個(gè)葉子結(jié)點(diǎn)。圖3-224 算法創(chuàng)新與實(shí)踐論文3.4源代碼#include#includeusingnamespacestd;constintN=5;constintM=3;ifstreamfin("5d8.txt");classColor{friendintmColoring(int,int,int**);private:boolOk(intk);voidBacktrack(intt);intn,m,**a,*x;longsum;};intmColoring(intn,intm,int**a);intmain(){int**a=newint*[N+1];for(inti=1;i<=N;i++){24 算法創(chuàng)新與實(shí)踐論文a[i]=newint[N+1];}cout<<"圖G的鄰接矩陣為:"<>a[i][j];cout<n){sum++;for(inti=1;i<=n;i++)cout<n時(shí)，算法搜索至葉節(jié)點(diǎn)，得到一個(gè)新的“+”個(gè)數(shù)與“-”個(gè)數(shù)相同的符號(hào)三角形，當(dāng)前已找到的符號(hào)三角形數(shù)sum增1。當(dāng)I<=n時(shí)，當(dāng)前擴(kuò)展節(jié)點(diǎn)Z是解空間中的內(nèi)部結(jié)點(diǎn)。該結(jié)點(diǎn)有X[i]=1和X[i]=0兩個(gè)兒子結(jié)點(diǎn)。對(duì)當(dāng)前擴(kuò)展結(jié)點(diǎn)Z的每一個(gè)兒子結(jié)點(diǎn)，計(jì)算其相應(yīng)的符號(hào)三角形中的“+”個(gè)數(shù)count與“-”個(gè)數(shù)，并以深度優(yōu)先的方式遞歸的對(duì)可行子樹搜索，或減去不可行子樹。[6]未知.計(jì)算機(jī)算法設(shè)計(jì)與分析.百度文庫，2011；無解的判斷，n*(n+1)/2為奇數(shù)。4.3源代碼#includeusingnamespacestd;classTriangle{friendintCompute(int);private:voidBacktrack(inti);intn,half,count,**p;longsum;};intCompute(intn);24 算法創(chuàng)新與實(shí)踐論文intmain(){for(intn=1;n<=10;n++){cout<<"n="<half)||(t*(t-1)/2-count>half)){return;}if(t>n){sum++;}else{for(inti=0;i<2;i++){p[1][t]=i;count+=i;for(intj=2;j<=t;j++){24 算法創(chuàng)新與實(shí)踐論文p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2];count+=p[j][t-j+1];}Backtrack(t+1);for(intj=2;j<=t;j++){count-=p[j][t-j+1];}count-=i;}}}intCompute(intn){TriangleX;X.n=n;X.count=0;X.sum=0;X.half=n*(n+1)/2;if(X.half%2==1)return0;X.half=X.half/2;int**p=newint*[n+1];for(inti=0;i<=n;i++){p[i]=newint[n+1];}24 算法創(chuàng)新與實(shí)踐論文for(inti=0;i<=n;i++){for(intj=0;j<=n;j++){p[i][j]=0;}}X.p=p;X.Backtrack(1);for(inti=0;i<=n;i++){delete[]p[i];}delete[]p;p=0;returnX.sum;}計(jì)算可行性約束需要O(n)時(shí)間，在最壞情況下有O(2^n)個(gè)結(jié)點(diǎn)需要計(jì)算可行性約束，故解符號(hào)三角形問題的回溯算法所需的計(jì)算時(shí)間為O(n2^n)。24 算法創(chuàng)新與實(shí)踐論文4.4運(yùn)行結(jié)果圖圖4-224 算法創(chuàng)新與實(shí)踐論文第5章圓的排列問題5.1問題描述給定n個(gè)大小不等的圓c1,c2,…,cn，現(xiàn)要將這n個(gè)圓排進(jìn)一個(gè)矩形框中，且要求各圓與矩形框的底邊相切。圓排列問題要求從n個(gè)圓的所有排列中找出有最小長度的圓排列。例如，當(dāng)n=3，且所給的3個(gè)圓的半徑分別為1，1，2時(shí)，這3個(gè)圓的最小長度的圓排列如圖所示。其最小長度為2+4。[7]楊金勇等.圓排列包裝問題最優(yōu)解解析.華僑大學(xué)學(xué)報(bào)，2013年2期；P58-62圖4-12+√45.2問題分析圓排列問題的解空間是一棵排列樹。按照回溯法搜索排列樹的算法框架，設(shè)開始時(shí)a=[r1,r2,……rn]是所給的n個(gè)元的半徑，則相應(yīng)的排列樹由a[1:n]的所有排列構(gòu)成。解圓排列問題的回溯算法中，CirclePerm(n,a)返回找到的最小的圓排列長度。初始時(shí)，數(shù)組a是輸入的n個(gè)圓的半徑，計(jì)算結(jié)束后返回相應(yīng)于最優(yōu)解的圓排列。center計(jì)算圓在當(dāng)前圓排列中的橫坐標(biāo)，由x^2=sqrt((r1+r2)^2-(r1-r2)^2)推導(dǎo)出x=2*sqrt(r1*r2)。24 算法創(chuàng)新與實(shí)踐論文Compoute計(jì)算當(dāng)前圓排列的長度。變量min記錄當(dāng)前最小圓排列長度。數(shù)組r表示當(dāng)前圓排列。數(shù)組x則記錄當(dāng)前圓排列中各圓的圓心橫坐標(biāo)。在遞歸算法Backtrack中，當(dāng)i>n時(shí)，算法搜索至葉節(jié)點(diǎn)，得到新的圓排列方案。此時(shí)算法調(diào)用Compute計(jì)算當(dāng)前圓排列的長度，適時(shí)更新當(dāng)前最優(yōu)值。當(dāng)i#includeusingnamespacestd;floatCirclePerm(intn,float*a);templateinlinevoidSwap(Type&a,Type&b);intmain(){float*a=newfloat[4];a[1]=1,a[2]=1,a[3]=2;cout<<"圓排列中各圓的半徑分別為："<temp){24 算法創(chuàng)新與實(shí)踐論文temp=valuex;}}returntemp;}voidCircle::Compute(void){floatlow=0,high=0;for(inti=1;i<=n;i++){if(x[i]-r[i]high){high=x[i]+r[i];}}if(high-lown)24 算法創(chuàng)新與實(shí)踐論文{Compute();}else{for(intj=t;j<=n;j++){Swap(r[t],r[j]);floatcenterx=Center(t);if(centerx+r[t]+r[1]inlinevoidSwap(Type&a,Type&b){Typetemp=a;a=b;b=temp;}5.4運(yùn)行結(jié)果圖圖5-124 算法創(chuàng)新與實(shí)踐論文結(jié)論在三個(gè)實(shí)例編程中，總的算法思想都是利用回溯法求解問題。第一個(gè)我們選的圖的著色問題，這是一個(gè)NP問題。涉及到圖的鄰接頂點(diǎn)的訪問和圖的便利。圖的儲(chǔ)存結(jié)構(gòu)選擇的是鄰接矩陣的形式，在遍歷圖式時(shí)是從第一個(gè)頂點(diǎn)開始，一次在頂點(diǎn)數(shù)組中完成所有頂點(diǎn)的遍歷，保證了全部的頂點(diǎn)都是可以訪問到的，因?yàn)橐灾且粋€(gè)動(dòng)態(tài)的過程，可以在遍歷的過程中完成著色，每次訪問一個(gè)結(jié)點(diǎn)，先賦值第一種顏色，如果和它的臨接點(diǎn)的顏色不重復(fù)，則對(duì)下個(gè)頂點(diǎn)著色，否則本頂點(diǎn)的顏色轉(zhuǎn)化到下一種，直到能夠完成賦值。程序編寫本身不難，思路很清晰，就是賦值和比較之間的來回循環(huán)比較困難。在通過三個(gè)實(shí)例的練習(xí)中，我們對(duì)回溯算法有了更進(jìn)一步的理解，對(duì)回溯法的解框架更清楚了。但在另一方面，也認(rèn)識(shí)到了自己的不足，因此，通過這三個(gè)編程，又使自己收獲了很多，還需要更加深入的學(xué)習(xí)算法。這說明回溯法是一種通用性很高的算法模型，這是因?yàn)槲覀兓厮莘嫦虻氖且豢每臻g搜索樹，這課樹已經(jīng)完成了從實(shí)際問題到數(shù)學(xué)表達(dá)的建模。而每棵樹的特性都是相當(dāng)一致的，所以我們的算法也具有高度的一致性。從這個(gè)角度看，一旦掌握了回溯法，那以后用起來是比較簡單的，所以回溯法是一個(gè)很值得學(xué)習(xí)的算法。問題的解空間通常是在搜索問題的解得過程中動(dòng)態(tài)產(chǎn)生的，這是回溯的一個(gè)重要特性。其實(shí)回溯法的根本思想就是從一條路往前走，能進(jìn)則進(jìn)，不能進(jìn)則退回來，換一條路再試。當(dāng)我們遇到某一類問題時(shí)，它的問題可以分解，但是又不能得出明確的動(dòng)態(tài)規(guī)劃或是遞歸解法，此時(shí)可以考慮用回溯法解決此類問題?；厮莘ǖ膬?yōu)點(diǎn)在于其程序結(jié)構(gòu)明確，可讀性強(qiáng)，易于理解，而且通過對(duì)問題的分析可以大大提高運(yùn)行效率。但是，對(duì)于可以得出明顯的遞推公式迭代求解的問題，還是不要用回溯法，因?yàn)樗ㄙM(fèi)的時(shí)間比較長。對(duì)于用回溯法求解的問題，首先要將問題進(jìn)行適當(dāng)?shù)霓D(zhuǎn)化，得出狀態(tài)空間樹。這棵樹的每條完整路徑都代表了一種解的可能。通過深度優(yōu)先搜索這棵樹，枚舉每種可能的解的情況；從而得出結(jié)果。但是，回溯法中通過構(gòu)造約束函數(shù)，可以大大提升程序效率，因?yàn)樵谏疃葍?yōu)先搜索的過程中，不斷的將每個(gè)解（并不一定是完整的，事實(shí)上這也就是構(gòu)造約束函數(shù)的意義所在）與約束函數(shù)進(jìn)行對(duì)照從而刪除一些不可能的解，這樣就不必繼續(xù)把解的剩余部分列出從而節(jié)省部分時(shí)間。24 算法創(chuàng)新與實(shí)踐論文參考文獻(xiàn)24