1、1,有許多問題，當(dāng)需要找出它的解集或者要求回答什么解是滿足某些約束條件的最佳解時，往往要使用回溯法。 回溯法的基本做法是搜索，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數(shù)相當(dāng)大的問題。 回溯法在問題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點時，先判斷該結(jié)點是否包含問題的解。如果肯定不包含，則跳過對該結(jié)點為根的子樹的搜索，逐層向其祖先結(jié)點回溯；否則，進入該子樹，繼續(xù)按深度優(yōu)先策略搜索。,回溯法,2,5.1回溯法的算法框架,一、問題的解空間 問題的解向量：回溯法希望一個問題的解能夠表示成一個n元式(x1,x2,xn)

2、的形式。 顯約束：對分量xi的取值限定。 隱約束：為滿足問題的解而對不同分量之間施加的約束。 解空間：對于問題的一個實例，解向量滿足顯式約束條件的所有多元組，構(gòu)成了該實例的一個解空間。,3,n=3時的0-1背包問題,用完全二叉樹表示的解空間,4,旅行售貨員問題的解空間,5,5.1 回溯法的算法框架,二、回溯法的基本思想,確定了解空間的組織結(jié)構(gòu)后，回溯法就從開始結(jié)點(根節(jié)點)出發(fā)，以深度優(yōu)先的方式搜索整個解空間。這個開始結(jié)點就成為一個活結(jié)點，同時成為當(dāng)前的擴展結(jié)點。在當(dāng)前的擴展結(jié)點處，搜索向縱深方向移至一個新結(jié)點。這個結(jié)點就成為一個新的活結(jié)點，并成為當(dāng)前擴展結(jié)點。如果在當(dāng)前的擴展結(jié)點處不能再向縱

3、深方向移動，則當(dāng)前的擴展結(jié)點就成為死結(jié)點。此時應(yīng)往回移動(回溯)至最近的一個活結(jié)點處，并使這個活結(jié)點成為當(dāng)前的擴展結(jié)點?；厮莘匆赃@種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已無活結(jié)點時為止。,擴展結(jié)點:一個正在產(chǎn)生兒子的結(jié)點稱為擴展結(jié)點 活結(jié)點:一個自身已生成但其兒子還沒有全部生成的節(jié)點稱做活結(jié)點 死結(jié)點:一個所有兒子已經(jīng)產(chǎn)生的結(jié)點稱做死結(jié)點,6,回溯法的基本思想,(1)針對所給問題，定義問題的解空間； (2)確定易于搜索的解空間結(jié)構(gòu)； (3)以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。,常用剪枝函數(shù)： 用約束函數(shù)在擴展結(jié)點處剪去不滿足約束的子樹； 用限

4、界函數(shù)剪去得不到最優(yōu)解的子樹。,用回溯法解題的一個顯著特征是在搜索過程中動態(tài)產(chǎn)生問題的解空間。在任何時刻，算法只保存從根結(jié)點到當(dāng)前擴展結(jié)點的路徑。如果解空間樹中從根結(jié)點到葉結(jié)點的最長路徑的長度為h(n)，則回溯法所需的計算空間通常為O(h(n)。而顯式地存儲整個解空間則需要O(2h(n)或O(h(n)!)內(nèi)存空間。,7,遞歸回溯,回溯法對解空間作深度優(yōu)先搜索，因此，在一般情況下用遞歸方法實現(xiàn)回溯法。,void backtrack (int t) if (tn) output(x); else for (int i=f(n,t);i=g(n,t);i+) xt=h(i); if (constra

5、int(t) ,8,迭代回溯,采用樹的非遞歸深度優(yōu)先遍歷算法，可將回溯法表示為一個非遞歸迭代過程。,void iterativeBacktrack () int t=1; while (t0) if (f(n,t)=g(n,t) for (int i=f(n,t);i=g(n,t);i+) xt=h(i); if (constraint(t) ,9,子集樹與排列樹,遍歷子集樹需O(2n)計算時間,遍歷排列樹需要O(n!)計算時間,void backtrack (int t) if (tn) output(x); else for (int i=0;i=1;i+) xt=i; if (legal

6、(t) backtrack(t+1); ,void backtrack (int t) if (tn) output(x); else for (int i=t;i=n;i+) swap(xt, xi); if (legal(t) backtrack(t+1); swap(xt, xi); ,10,三、子集樹的構(gòu)造,當(dāng)所給的問題是從n個元素的集合中找出滿足某種性質(zhì)的子集時，相應(yīng)的解空間樹稱為子集樹(subset tree)。 例如：對于n個元素的整數(shù)集1,2,n，n=1時，只有兩個子集，即為和1；n=2時，有4個子集；n=3時，有8個子集。每增加一個新元素，都使子集個數(shù)加倍，因此對于n個元素，

7、有2n個子集。,例如：0-1背包問題對應(yīng)的解空間就是一棵子集樹，樹中所有結(jié)點都可能成為問題的解。,11,四、排列樹的構(gòu)造,當(dāng)所給的問題是從n個元素的集合中找出滿足某種性質(zhì)的排列時，相應(yīng)的解空間樹稱為排列樹(permutation tree)。 例如：對于1,2,n的一個排列，其第一個元素可以有n種不同的選擇。一旦選定這個值x1，則第二個位置有n-1種選擇，重復(fù)這個過程，得到不同排列的總數(shù)為n!。排列樹中至多有n!個葉結(jié)點。因此對于n個元素，有n!個子集。,例如：n皇后問題對應(yīng)的解空間就是一棵排列樹。,12,五、搜索樹的構(gòu)造,13,n后問題,在nn格的棋盤上放置彼此不受攻擊的n個皇后。按照國際象

8、棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。n后問題等價于在nn格的棋盤上放置n個皇后，任何2個皇后不放在同一行或同一列或同一斜線上。,14,解向量：(x1, x2, , xn) 顯約束：xi=1,2, ,n 隱約束： 1)不同列：xixj 2)不處于同一正、反對角線：|i-j|xi-xj|,n后問題,15,bool Queen:Place(int k) for (int j=1;jn) sum+; else for (int i=1;i=n;i+) xt=i; if (Place(t) Backtrack(t+1); ,16,Queen:backtrack() X1=0;

9、 int k=1; While(k0) xk+=1; while(xk=n) ,Place(int k) for(int j=1;jk;j+) if(abs(k-j)=aba(xj-xk)|(xj=xk) return false; return true; ,17,0-1背包問題,解空間：子集樹 可行性約束函數(shù)： 上界函數(shù)：,迷宮問題,1、形式化描述問題： 迷宮用A 描述迷宮， 當(dāng)Ai,j=0 表示該房間為空，當(dāng)Ai,j=1 表示該房間封閉,2、解的形式： (x1, x2, , xn) n取值不確定 Xi=1, 2, 3, 4 -顯約束,3、隱約束條件 當(dāng)Ai,j=2 表示該房間已經(jīng)走過，不

10、能再走； Ai,j=1 表示該房間封閉，也不能走； 每步走的方向：上下左右,4、畫出解空間樹,Sum=1; ailjl=2; aizjz=3;/sum為所能走過的房間數(shù) for( i=1;im or jln) continue; if ( ailjl=0 ) else if(k4) else /回溯 ,if ( ailjl=0 ) i =il; j = jl; /記錄當(dāng)前位置 xs=k; /記錄決策 s=s+1; /下一步（縱深搜索） ailjl=2; /房間已經(jīng)走過 start=1; break; /又從1開始 else if (ailjl=3 or s=sum) xs=k; break;

11、,if(k4) /回溯 aij=0;s-; L=xs; i=i-vL; j=j-uL; start=L+1; else if(ssum) 輸出解,21,圖的m著色問題,給定無向連通圖G和m種不同的顏色。用這些顏色為圖G的各頂點著色，每個頂點著一種顏色。是否有一種著色法使G中每條邊的2個頂點著不同顏色。這個問題是圖的m可著色判定問題。若一個圖最少需要m種顏色才能使圖中每條邊連接的2個頂點著不同顏色，則稱這個數(shù)m為該圖的色數(shù)。求一個圖的色數(shù)m的問題稱為圖的m可著色優(yōu)化問題。,復(fù)雜度分析 圖m可著色問題的解空間樹中內(nèi)結(jié)點個數(shù)是 對于每一個內(nèi)結(jié)點，在最壞情況下，用ok檢查當(dāng)前擴展結(jié)點的每一個兒子所相應(yīng)

12、的顏色可用性需耗時O(mn)。因此，回溯法總的時間耗費是,22,解向量：(x1, x2, , xn)表示頂點i所著顏色xi 可行性約束函數(shù)：頂點i與已著色的相鄰頂點顏色不重復(fù)。,圖的m著色問題,void Color:Backtrack(int t) if (tn) sum+; for (int i=1; i=n; i+) cout xi ; cout endl; else for (int i=1;i=m;i+) xt=i; if (Ok(t) Backtrack(t+1); bool Color:Ok(int k) / 檢查顏色可用性 for (int j=1;j=n;j+) if (akj

13、=1) ,M_coloring(int n, int m, int g ) /非遞歸算法1 for(i=1;i=1) xk+; while(k=1) if(kn) 輸出解；if(k1) 無解；,M_coloring(int n, int m, int g ) /非遞歸算法2 for(i=1;i0) xk=xk+1; while(xk=m ,Bool Color(k) for(i=1;i=n;i+) f(gik=1 and xi=xk) return(false); return(true); ,25,旅行售貨員問題,解空間：排列樹,template void Traveling:Backtra

14、ck(int i) if (i = n) if (axn-1xn != NoEdge ,復(fù)雜度分析 算法backtrack在最壞情況下可能需要更新當(dāng)前最優(yōu)解O(n-1)!)次，每次更新bestx需計算時間O(n)，從而整個算法的計算時間復(fù)雜性為O(n!)。,子集和數(shù)的問題,假設(shè)有n個不同的正整數(shù)，找出這些數(shù)中所有使其和為正整數(shù)m的組合。,解空間： 1、解的形式： (x1,x2,xn) 2、顯約束條件：xi=0或1 3、隱約束條件: 子集和為m 4、解空間樹,Sumofsub() for(i=1;i1) k=k-1; xk-1=0; s=s-wk-1; xk=1; while(k0) if(k=

15、0) 無解； ,28,回溯法效率分析,通過前面具體實例的討論容易看出，回溯算法的效率在很大程度上依賴于以下因素： (1)產(chǎn)生xk的時間； (2)滿足顯約束的xk值的個數(shù)； (3)計算約束函數(shù)constraint的時間； (4)計算上界函數(shù)bound的時間； (5)滿足約束函數(shù)和上界函數(shù)約束的所有xk的個數(shù)。 好的約束函數(shù)能顯著地減少所生成的結(jié)點數(shù)。但這樣的約束函數(shù)往往計算量較大。因此，在選擇約束函數(shù)時通常存在生成結(jié)點數(shù)與約束函數(shù)計算量之間的折衷。,29,重排原理,對于許多問題而言，在搜索試探時選取xi的值順序是任意的。在其它條件相當(dāng)?shù)那疤嵯?，讓可取值最少的xi優(yōu)先。從圖中關(guān)于同一問題的2棵不同

16、解空間樹，可以體會到這種策略的潛力。,圖(a)中，從第1層剪去1棵子樹，則從所有應(yīng)當(dāng)考慮的3元組中一次消去12個3元組。對于圖(b)，雖然同樣從第1層剪去1棵子樹，卻只從應(yīng)當(dāng)考慮的3元組中消去8個3元組。前者的效果明顯比后者好。,(a),(b),30,練習(xí),例3：在任意給定的字符表(例如：1,2,3)上，生成一個由該字符組成、含n個字符的序列，但要求生成的序列中沒有兩個相鄰的子序列是相同的。,例如：對于n=5,序列“12321”是問題的一個解，而序列“12323”因有兩個相鄰的子序列都為“23”，所以該序列不是問題的解。,為找到一個滿足要求的長為n個字符的序列，從空序列開始，每次檢查當(dāng)前序列是

17、否含有兩個相鄰的子序列。在沒有兩個相鄰的子序列相同的情況下，在序列之后添加一個字符，讓序列延長。如果當(dāng)前序列有兩個相鄰的子序列一樣時，就改變序列。如此重復(fù)執(zhí)行延長、檢查或修改、檢查，直到找到一個滿足問題要求的解。,31,練習(xí),算法：,int n,m; int good; char sMAXLEN; 輸入欲求序列長度n; m=0; good=1; do if(good) 延長序列;m+; else 改變序列;若所有字符都嘗試過，則m- good=檢查當(dāng)前序列是否合理的結(jié)果; while(!good|m!=n) ,32,#include #define MAXLEN 100 main() int n,m; int