算法第5章 回溯法

1、第5章 回溯法 學(xué)習(xí)要點(diǎn)學(xué)習(xí)要點(diǎn) 理解回溯法的深度優(yōu)先搜索策略 掌握用回溯法解題的算法框架 （1）遞歸回溯最優(yōu)子結(jié)構(gòu)性質(zhì) （2）迭代回溯貪心選擇性質(zhì) （3）子集樹算法框架 （4）排列樹算法框架通過應(yīng)用范例學(xué)習(xí)回溯法的設(shè)計(jì)策略。（1）裝載問題；（2）批處理作業(yè)調(diào)度；（3）符號三角形問題（4）n后問題；（5）0-1背包問題； （6）最大團(tuán)問題；（7）圖的m著色問題（8）旅行售貨員問題（9）圓排列問題（10）電路板排列問題（11）連續(xù)郵資問題用計(jì)算機(jī)求解問題用計(jì)算機(jī)求解問題問題空間問題空間現(xiàn)實(shí)求解過程現(xiàn)實(shí)求解過程實(shí)際解實(shí)際解狀態(tài)空間狀態(tài)空間對象的定義對象的定義機(jī)器求解過程算法與程序的設(shè)計(jì)算法與程序的

2、設(shè)計(jì)機(jī)內(nèi)解機(jī)內(nèi)解計(jì)算機(jī)求解的過程計(jì)算機(jī)求解的過程 在狀態(tài)空間尋找機(jī)內(nèi)解在狀態(tài)空間尋找機(jī)內(nèi)解, , 可以看成是從初始狀態(tài)出發(fā)可以看成是從初始狀態(tài)出發(fā), ,搜索目標(biāo)狀態(tài)搜索目標(biāo)狀態(tài)( (解所在的狀態(tài)解所在的狀態(tài)) )的過程的過程。狀態(tài)空間狀態(tài)空間初始狀態(tài)初始狀態(tài)目標(biāo)狀態(tài)目標(biāo)狀態(tài)搜索搜索n搜索的過程可描述為：搜索的過程可描述為：S0S1Sn，其中，其中S0為初態(tài)，為初態(tài)，Sn為終態(tài)。或者說為終態(tài)?；蛘哒f(S0)且且(Sn)，這，這里里稱為初始條件，稱為初始條件，稱為終止條件。稱為終止條件。6求解是狀態(tài)空間的搜索求解是狀態(tài)空間的搜索 求解的過程可以描述為對狀態(tài)空間的搜索求解的過程可以描述為對狀態(tài)空間的

3、搜索S0S11S12S1k Sn1SniSnm其中其中S0為初始狀為初始狀態(tài)，不妨設(shè)態(tài)，不妨設(shè)Sni為為終止?fàn)顟B(tài)終止?fàn)顟B(tài)S0Snin問題求解就是通過搜索，尋找出一條從初始狀問題求解就是通過搜索，尋找出一條從初始狀態(tài)態(tài)S0到終止?fàn)顟B(tài)到終止?fàn)顟B(tài)Sni的路徑。的路徑。7幾種搜索方法幾種搜索方法狀態(tài)空間的搜索實(shí)際上是一種樹狀態(tài)空間的搜索實(shí)際上是一種樹/DAG（Directed Acyclic Graph ）的搜索，常用的方法有：）的搜索，常用的方法有：n廣度優(yōu)先搜索廣度優(yōu)先搜索n深度優(yōu)先搜索深度優(yōu)先搜索n啟發(fā)式搜索啟發(fā)式搜索從初始狀態(tài)開始，逐層地進(jìn)行搜索。從初始狀態(tài)開始，逐層地進(jìn)行搜索。從初始狀態(tài)開始

4、，逐個分枝地進(jìn)行搜索。從初始狀態(tài)開始，逐個分枝地進(jìn)行搜索。從初始狀態(tài)開始，每次選擇最有可能達(dá)到終從初始狀態(tài)開始，每次選擇最有可能達(dá)到終止?fàn)顟B(tài)的結(jié)點(diǎn)進(jìn)行搜索。止?fàn)顟B(tài)的結(jié)點(diǎn)進(jìn)行搜索。8三種搜索的優(yōu)劣之處三種搜索的優(yōu)劣之處 一般來說，三種搜索方法各有優(yōu)劣之處：一般來說，三種搜索方法各有優(yōu)劣之處： 廣度優(yōu)先搜索和深度優(yōu)先搜索廣度優(yōu)先搜索和深度優(yōu)先搜索優(yōu)點(diǎn)優(yōu)點(diǎn)：一定能一定能找到解找到解；缺點(diǎn)：缺點(diǎn)：時間復(fù)雜性大時間復(fù)雜性大。 啟發(fā)式搜索啟發(fā)式搜索優(yōu)點(diǎn)優(yōu)點(diǎn)：一般來說能較快地找到解，一般來說能較快地找到解，即其時間復(fù)雜性小即其時間復(fù)雜性??；缺點(diǎn)：缺點(diǎn)：需要設(shè)計(jì)一個評需要設(shè)計(jì)一個評價函數(shù)，并且評價函數(shù)的優(yōu)劣決

5、定了啟發(fā)式價函數(shù)，并且評價函數(shù)的優(yōu)劣決定了啟發(fā)式搜索的優(yōu)劣搜索的優(yōu)劣。 當(dāng)需要找出問題的解集，或者要求回答什么解是滿足某些約束條件的最佳解時，往往要使用回溯法。 回溯法的基本做法是搜索，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數(shù)相當(dāng)大的問題。 在問題的解空間樹中，回溯法按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。 算法搜索至解空間樹的任意一點(diǎn)時，先判斷該結(jié)點(diǎn)是算法搜索至解空間樹的任意一點(diǎn)時，先判斷該結(jié)點(diǎn)是否包含問題的解否包含問題的解。 如果肯定不包含，則跳過對該結(jié)點(diǎn)為根的子樹的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。回溯法5

6、.1 回溯法的算法框架5.1.1 問題的解空間 應(yīng)用回溯法解問題時，首先應(yīng)明確定義問題的解空間。問題的解空間應(yīng)至少包含問題的一個(最優(yōu))解。通常將解空間組織成樹或圖的形式。 問題的解向量：回溯法希望一個問題的解，能夠表示成一個n元式(x1,x2,xn)的形式。 顯約束：對分量xi的取值限定 隱約束：為滿足問題的解，而對不同分量之間施加的約束。 解空間：對于問題的一個實(shí)例，解向量滿足顯式約束條件的所有多元組，構(gòu)成了該實(shí)例的一個解空間。 例如，對于有n種可選物品的0-1背包問題，其解空間由長度為n的0-1向量組成。n=3時的0-1背包問題用完全二叉樹表示的解空間5.1.2 回溯法的基本思想 擴(kuò)展結(jié)

7、點(diǎn):一個正在產(chǎn)生兒子的結(jié)點(diǎn) 活結(jié)點(diǎn):一個自身已生成但其兒子還沒有全部生成的節(jié)點(diǎn) 死結(jié)點(diǎn):一個所有兒子已經(jīng)產(chǎn)生的結(jié)點(diǎn) 深度優(yōu)先的問題狀態(tài)生成法：如果對一個擴(kuò)展結(jié)點(diǎn)R，一旦產(chǎn)生了它的一個兒子C，就把C當(dāng)做新的擴(kuò)展結(jié)點(diǎn)。在完成對子樹C（以C為根的子樹）的窮盡搜索之后，將R重新變成擴(kuò)展結(jié)點(diǎn)，繼續(xù)生成R的下一個兒子（如果存在） 寬度優(yōu)先的問題狀態(tài)生成法：在一個擴(kuò)展結(jié)點(diǎn)變成死結(jié)點(diǎn)在一個擴(kuò)展結(jié)點(diǎn)變成死結(jié)點(diǎn)之前，它一直是擴(kuò)展結(jié)點(diǎn)之前，它一直是擴(kuò)展結(jié)點(diǎn)。 回溯法：為了避免生成那些不可能產(chǎn)生最佳解的問題狀態(tài)，要不斷地利用限界函數(shù)(bounding function)來處死那些實(shí)際上不可能產(chǎn)生所需解的活結(jié)點(diǎn)，以減少

8、問題的計(jì)算量。具有限界函數(shù)的深度優(yōu)先生成法稱為回溯法。 基本思想： 確定了解空間的組織結(jié)構(gòu)后，回溯法就從開始結(jié)點(diǎn)（根結(jié)點(diǎn)）出發(fā)，以深度優(yōu)先的方式搜索整個解空間。 開始結(jié)點(diǎn)就成為一個活結(jié)點(diǎn)，同時也成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。 在當(dāng)前擴(kuò)展結(jié)點(diǎn)，搜索向縱深方向移至一個新結(jié)點(diǎn)。這個新結(jié)點(diǎn)就成為一個新的活結(jié)點(diǎn)，并成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。 如果在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處不能再向縱深方向移動，則當(dāng)前擴(kuò)展結(jié)點(diǎn)就成為死結(jié)點(diǎn)。 此時，應(yīng)往回移動（回溯）至最近的一個活結(jié)點(diǎn)處，并使這個活結(jié)點(diǎn)成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。 回溯法即以這種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結(jié)點(diǎn)時為止。 示例1 0-1背包問題 n=3,

9、C=30, w=16, 15, 15, v=45, 25, 25開始時，Cr=C=30，V=0，A為唯一活結(jié)點(diǎn)，也是當(dāng)前擴(kuò)展結(jié)點(diǎn)擴(kuò)展A，先到達(dá)B結(jié)點(diǎn)Cr=Cr-w1=14，V=V+v1=45此時A、B為活結(jié)點(diǎn)，B成為當(dāng)前擴(kuò)展結(jié)點(diǎn)擴(kuò)展B，先到達(dá)DCrw2，D導(dǎo)致一個不可行解，回溯到B再擴(kuò)展B到達(dá)EE可行，此時A、B、E是活結(jié)點(diǎn)，E成為新的擴(kuò)展結(jié)點(diǎn)擴(kuò)展E，先到達(dá)JCr45，皆得到一個可行解x=(0,1,1)，V=50L不可擴(kuò)展，成為死結(jié)點(diǎn)，返回到F再擴(kuò)展F到達(dá)MM是葉結(jié)點(diǎn)，且2550，不是最優(yōu)解M不可擴(kuò)展，成為死結(jié)點(diǎn)，返回到FF沒有可擴(kuò)展結(jié)點(diǎn)，成為死結(jié)點(diǎn)，返回到C再擴(kuò)展C到達(dá)GCr=30，V=0，

10、活結(jié)點(diǎn)為A、C、G，G為當(dāng)前擴(kuò)展結(jié)點(diǎn)擴(kuò)展G，先到達(dá)N，N是葉結(jié)點(diǎn)，且2550，不是最優(yōu)解，又N不可擴(kuò)展，返回到G再擴(kuò)展G到達(dá)O，O是葉結(jié)點(diǎn)，且050，不是最優(yōu)解，又O不可擴(kuò)展，返回到GG沒有可擴(kuò)展結(jié)點(diǎn)，成為死結(jié)點(diǎn)，返回到CC沒有可擴(kuò)展結(jié)點(diǎn)，成為死結(jié)點(diǎn)，返回到AA沒有可擴(kuò)展結(jié)點(diǎn)，成為死結(jié)點(diǎn)，算法結(jié)束，最優(yōu)解X=(0,1,1)，最優(yōu)值V=50ACr=C=30，V=0Bw1=16，v1=45Cr=14，V=45C Cr=30，V=0DCrw2不可行解JCr45x=(0,1,1)Fw2=15，v2=25Cr=15，V=25M25n) output(x);/ tn時已搜索到一個葉結(jié)點(diǎn), output(x

11、)對得到 的可行解x進(jìn)行記錄或輸出處理. else for (int i=f(n,t);i0) if (f(n,t)=g(n,t) for (int i=f(n,t);in) output(x); else for (int i=0;in) output(x); else for (int i=t;i n) / 到達(dá)葉結(jié)點(diǎn) 更新最優(yōu)解bestx, bestw; return;/bestw記錄當(dāng)前已找到的最大裝載量 r -= wi; if (cw + wi bestw) xi = 0; / 搜索右子樹 backtrack(i + 1); r += wi; 5.3 批處理作業(yè)調(diào)度n給定n個作業(yè)集合

12、J1,J2,Jn。每個作業(yè)先由機(jī)器1處理，再由機(jī)器2處理。Ji需機(jī)器j的處理時間為tji。n對于一個確定的作業(yè)調(diào)度，設(shè)Fji是作業(yè)i在機(jī)器j上完成處理的時間(時間點(diǎn))。所有作業(yè)在機(jī)器2上完成處理的時間和f=F21+F22+F2n稱為該作業(yè)調(diào)度的完成時間和。n問題：對于給定的n個作業(yè)，制定最佳作業(yè)調(diào)度方案，使其完成時間和達(dá)到最小。tji機(jī)器1機(jī)器2作業(yè)121作業(yè)231作業(yè)323這3個作業(yè)的6種可能的調(diào)度方案是1,2,3；1,3,2；2,1,3；2, 3, 1；3, 1, 2；3, 2, 1；它們所相應(yīng)的完成時間和分別是19(=3+6 +10)，18，20，21，19，19。易見，最佳調(diào)度方案是1

13、, 3, 2，其完成時間和為18。對于批處理作業(yè)調(diào)度問題,可以證明, 存在一個最佳作業(yè)調(diào)度使得在機(jī)器1和2上以相同次序完成。解空間：排列樹設(shè)x=1,2, n為所給n個作業(yè),則相應(yīng)的排列樹由x1:n的所有排列構(gòu)成.void Flowshop:Backtrack(int i) /Backtrack是類是類Flowshop的私有成員函數(shù)的私有成員函數(shù) if (i n) for (int j = 1; j = n; j+) bestxj = xj; bestf = f; else for (int j = i; j f1)?f2i-1:f1)+Mxj2; f+=f2i; if (f half)|(t*

14、(t-1)/2-counthalf) return; if (tn) sum+;/ 搜索至葉結(jié)點(diǎn),得到+-號相同的符號三角形, 三角形數(shù)增1. else for (int i=0;i2;i+) p1t=i; count+=i; for (int j=2;j=t;j+) pjt-j+1=pj-1t-j+1pj-1t-j+2; count+=pjt-j+1; Backtrack(t+1); for (int j=2;j=t;j+) count-=pjt-j+1; count-=i; + + - + - + + - - - - +- + + + - - + + - - + - - - +復(fù)雜度分析復(fù)

15、雜度分析計(jì)算可行性約束需要O(n)時間，在最壞情況下有 O(2n)個結(jié)點(diǎn)需要計(jì)算可行性約束，故解符號三角形問題的回溯算法所需的計(jì)算時間為 O(n2n)。5.5 n后問題p在nn格的棋盤上放置彼此不受攻擊的n個皇后。按照國際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。pn后問題等價于在nn格的棋盤上放置n個皇后，任何2個皇后不放在同一行或同一列或同一斜線上。1 2 3 4 5 6 7 812345678QQQQQQQQ解向量：(x1, x2, , xn), xi表示皇后i放在棋盤的第i行的第xi列上. 解空間: 排列樹顯約束：xi=1,2, ,n (列的取值范圍)隱約束：

16、1)不同列：xi xj 2)不處于同一正、反對角線上：|i-j| |xi-xj| 事實(shí)上,如果用(i, j)表示棋盤上第i行與第j列交叉的位置, 則在同一條平行于主對角線的對角線上的兩點(diǎn)(i, j)和(k, l)滿足關(guān)系式i-j=k-l;而處于同一條平行于副對角線的對角線上的兩點(diǎn)(i, j)和(k, l), 則滿足關(guān)系式i+j=k+l. 將這兩個關(guān)系式略作變形即得兩種情況的統(tǒng)一表示： | i-k | = | j-l | (*)反之,如果棋盤上的兩點(diǎn)(i, j)和(k, l)滿足關(guān)系式(*), 則它們一定位于同一條對角線上. 設(shè)計(jì)函數(shù)Place來測試: 若將皇后k放在xk列, 是否與前面已放置的

17、k-1個皇后都不在同一列, 且不在同一斜線上. 回溯法解n后問題, 用一棵完全n叉樹來表示其解空間. 用可行性約束函數(shù)place可剪去不滿足行、列和斜線約束的子樹.bool Queen:Place(int k) for (int j=1;jn) sum+;/sum為已找到的可行方案數(shù)為已找到的可行方案數(shù) else for (int i=1;i=n;i+) xt=i; if (Place(t) Backtrack(t+1); 5.6 0-1背包問題解空間：子集樹 (與裝載問題的回溯法相似)可行性約束函數(shù)：見教材p138-14111cxwniiitemplateTypep Knap:Bound(i

18、nt i)/ 計(jì)算上界 Typew cleft = c - cw; / 剩余容量 Typep b = cp; / 以物品單位重量價值遞減序裝入物品 while (i = n & wi = cleft) cleft -= wi; b += pi; i+; / 裝滿背包 if (i n) / 到達(dá)葉結(jié)點(diǎn) for (int j = 1; j = n; j+) bestxj = xj; bestn = cn; return; / 檢查頂點(diǎn) i 與當(dāng)前團(tuán)的連接 int OK = 1; for (int j = 1; j bestn) / 進(jìn)入右子樹,確定還有足夠多的頂點(diǎn)使得可能找到更大的團(tuán)。 x

19、i = 0; Backtrack(i+1);復(fù)雜度分析復(fù)雜度分析最大團(tuán)問題的回溯算法backtrack所需的計(jì)算時間顯然為O(n2n)。12453325.8 圖的m著色問題1.問題描述 u給定無向連通圖G和m種不同的顏色。用這些顏色為圖G的各頂點(diǎn)著色，每個頂點(diǎn)著一種顏色。是否有一種著色法使G中每條邊的2個頂點(diǎn)著不同顏色。這個問題是圖的m可著色判定問題。u若一個圖最少需要m種顏色才能使圖中每條邊連接的2個頂點(diǎn)著不同顏色，則稱這個數(shù)m為該圖的色數(shù)。求一個圖的色數(shù)m的問題稱為圖的m可著色優(yōu)化問題。33 對于圖著色的研究是從m可著色性問題的著名特例 四色問題開始的。 四色猜想是英國學(xué)者于1852年提出

20、的，這個問題要求證明平面或球面上的任何地圖的所有區(qū)域都可以至多用四種顏色來著色，使任何兩個有一段公共邊界的相鄰區(qū)域沒有相同的顏色。 這個問題可轉(zhuǎn)換成對一平面圖的4著色判定問題.34 多年來，已證明用5種顏色足以對任何一幅地圖著色. 但是, 一直找不到一定要求多于4種顏色的地圖。 直到1976年 ，這個問題才由三位美國學(xué)者在計(jì)算機(jī)上花費(fèi)了1200個小時才給出證明：任何平面圖是可以4著色的。 四色猜想從此變成了四色定理。35可平面圖可平面圖：若一個圖的所有頂點(diǎn)和邊：若一個圖的所有頂點(diǎn)和邊, 都能用某都能用某種方式畫在平面上種方式畫在平面上, 且沒有任何兩邊相交且沒有任何兩邊相交.假設(shè)每個國家單連通

21、，假設(shè)每個國家單連通，國家國家相鄰相鄰指這兩個國家有一指這兩個國家有一段長度不為段長度不為0的公共邊界，而不僅有一個公共點(diǎn)的公共邊界，而不僅有一個公共點(diǎn)。36實(shí)例：如下圖實(shí)例：如下圖n=7, m=3n=7, m=3372. 2. 算法設(shè)計(jì)算法設(shè)計(jì)一般連通圖的可著色問題，不僅限于可平面圖。一般連通圖的可著色問題，不僅限于可平面圖。給定圖給定圖G=（V，E）和）和m種顏色，如果該圖不是種顏色，如果該圖不是m可可著色，給出否定回答；若著色，給出否定回答；若m可著色，找出所有不同著可著色，找出所有不同著色方法。色方法。算法算法：回溯法：回溯法解空間解空間: 完全完全m叉樹叉樹38 n3，m3的狀態(tài)空間

22、樹39解向量：(x1, x2, , xn)頂點(diǎn)i所著顏色xi .可行性約束函數(shù)：頂點(diǎn)i與已著色的相鄰頂點(diǎn)顏色不重復(fù)。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=1)/結(jié)點(diǎn)相連&(xj=xk)/結(jié)點(diǎn)同色 return false;

23、return true;403 復(fù)雜度分析復(fù)雜度分析n圖m可著色問題的解空間樹中，內(nèi)結(jié)點(diǎn)個數(shù)是： n對于每一個內(nèi)結(jié)點(diǎn)，在最壞情況下，用ok檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)每一個兒子的顏色可用性需耗時O(mn)。n因此，回溯法總的時間耗費(fèi)是10niim)() 1/() 1()(10nnniinmOmmnmmnm41 問題描述問題描述： 某售貨員到若干城市去推銷商品，已知各某售貨員到若干城市去推銷商品，已知各城市之間的路程城市之間的路程(或旅費(fèi)或旅費(fèi))。他要選定一條。他要選定一條路線，經(jīng)過每個城市路線，經(jīng)過每個城市一遍一遍最后回到駐地的最后回到駐地的路線，路線，使得總的路程使得總的路程(或總旅費(fèi)或總旅費(fèi))最小最小

24、。5.9 旅行售貨員問題42 哈密頓回路問題哈密頓回路問題設(shè)G =（V，E）是一個有n個結(jié)點(diǎn)的連通圖。一個哈密頓回路是一條沿著圖G中的n條邊經(jīng)過每個結(jié)點(diǎn)一次, 最后回到起始點(diǎn)的一條周游回路。一個哈密頓回路是從G中的某個結(jié)點(diǎn)v1開始，依次經(jīng)過G的結(jié)點(diǎn)v2，v3，vn+1，且邊（vi，vi+1），i=1,n，均在G中，除了vn+1與v1是同一個結(jié)點(diǎn)之外，其余結(jié)點(diǎn)均不相同。43pG1的哈密頓回路存在，為128765431，而G2不存在任何哈密頓回路。p目前還沒有什么比較容易的方法,來確定一個已知圖是否含有哈密頓回路。p方法：回溯算法 G1：有哈密頓回路 G2：沒有哈密頓回路44解空間：排列樹temp

25、latevoid Traveling:Backtrack(int i) if (i = n) if (axn-1xn != NoEdge & axn1 != NoEdge &/ NoEdge是無邊標(biāo)記 (cc + axn-1xn + axn1 bestc | bestc = NoEdge) for (int j = 1; j = n; j+) bestxj = xj; bestc = cc + axn-1xn + axn1; else for (int j = i; j = n; j+) / 是否可進(jìn)入xj子樹? if (axi-1xj != NoEdge & (cc

26、+ axi-1xi n) Compute(); /完成所有圓，計(jì)算排列長度 else for (int j = t; j = n; j+) /考慮各種排列 Swap(rt, rj); float centerx=Center(t);/求得第t個圓的圓心相對第1個圓的圓心的橫坐標(biāo) if (centerx+rt+r1min) /判斷此時排列長度是否已超過當(dāng)前解，未超過繼續(xù)遞歸 xt=centerx;/修改圓t的圓心坐標(biāo) Backtrack(t+1); Swap(rt, rj);/還原排列 51 void Circle:Compute(void)/ 計(jì)算當(dāng)前圓排列的長度 float low=0, /

27、low表示圓排列的最左端坐標(biāo) high=0; /high表示圓排列的最右端坐標(biāo) /此時的坐標(biāo)是相對第一個圓的圓心建立的 for (int i=1;i=n;i+) if (xi-rihigh) high=xi+ri;/計(jì)算最右端 if (high-lowmin) min=high-low;float Circle:Center(int t)/ 計(jì)算當(dāng)前所選擇圓的圓心橫坐標(biāo) float temp=0; for (int j=1;jtemp) temp=valuex;/取較大值 return temp; /返回圓t的圓心橫坐標(biāo)52 3復(fù)雜度分析復(fù)雜度分析 在最壞情況下, 算法backtrack可能需

28、要計(jì)算O(n!)次當(dāng)前圓排列長度; 每次計(jì)算需O(n)計(jì)算時間，整個算法的計(jì)算時間復(fù)雜性為O(n+1)!) 53 上述算法尚有許多改進(jìn)的余地。例如:u象1,2,n-1,n和n,n-1, ,2,1這種互為鏡像的排列具有相同的圓排列長度，只計(jì)算一個就夠了，可減少約一半的計(jì)算量。u如果所給的n個圓中有k個圓有相同的半徑，則這k個圓產(chǎn)生的k!個完全相同的圓排列，只計(jì)算一個就夠了。算法的改進(jìn)算法的改進(jìn)：對稱性應(yīng)用對稱性應(yīng)用54是大規(guī)模電子系統(tǒng)設(shè)計(jì)中提出的一個實(shí)際問題是大規(guī)模電子系統(tǒng)設(shè)計(jì)中提出的一個實(shí)際問題. 問題描述問題描述:將將n n塊電路板以最佳排列方案塊電路板以最佳排列方案, , 插入帶有插入帶有

29、n n個插槽的機(jī)箱中個插槽的機(jī)箱中. n塊電路板的不同的排列方式塊電路板的不同的排列方式, 對應(yīng)于不同的電路對應(yīng)于不同的電路板插入方案板插入方案.電路板集合電路板集合: B=1, 2, , n 連接塊集合連接塊集合: L=N1, N2, , Nm 其中其中: Nj B，NNj j中所有電路板用一根導(dǎo)線連接中所有電路板用一根導(dǎo)線連接5.11 電路板排列問題電路板排列問題55 排列排列: X=, 即在機(jī)箱的第即在機(jī)箱的第i個插個插槽中插入電路板槽中插入電路板xi. 排列密度排列密度density(X)： 跨越相鄰電路板插槽的最大連線數(shù)跨越相鄰電路板插槽的最大連線數(shù) 求解求解: 具有最小排列密度具有

30、最小排列密度density(X)的排列的排列56實(shí)例實(shí)例：B=1,2,B=1,2,8, L=N,8, L=N1 1,N,N2 2, ,N,N5 5,N N1 1=4,5,6,N=4,5,6,N2 2=2,3,N=2,3,N3 3=1,3,N=1,3,N4 4=3,6,N=3,6,N5 5=7,8 =7,8 排列排列 X X1 1= 排列密度排列密度=?=?density(Xdensity(X1 1) = 2) = 2 電路板插槽電路板插槽編號編號57N N1 1=4,5,6,N=4,5,6,N2 2=2,3,N=2,3,N3 3=1,3,N=1,3,N4 4=3,6,=3,6,N N5 5=7

31、,8=7,8排列排列 X X2 2= density(Xdensity(X2 2)=)= 4 4 插槽2和3之間的連線數(shù)為4 58p算法算法設(shè)計(jì)設(shè)計(jì):電路板排列問題是一個電路板排列問題是一個NP難問題難問題.p解空間解空間: 排列樹排列樹p算法算法: 通過系統(tǒng)搜索問題解空間的排列樹通過系統(tǒng)搜索問題解空間的排列樹,找出電找出電路板最佳排列路板最佳排列.p 符號說明符號說明: totalj：連接塊連接塊Nj的電路板數(shù)的電路板數(shù) nowj：x1, x2, , xi中包含的中包含的Nj中的電路板數(shù)中的電路板數(shù) cd：從電路板從電路板1到到i的最大排列密度的最大排列密度p橫跨電路板橫跨電路板i到到i+1

32、的連接塊集合的連接塊集合，其條件如下：，其條件如下： 塊塊Nj的連線跨越的連線跨越i和和i+1 nowj0且且nowjtotalj 59計(jì)算插槽計(jì)算插槽i i和和i i1 1的連線密度的連線密度例如例如i=2, i=2, 此刻此刻 now1=now2=now3=now4=1, now1=now2=now3=now4=1, total1=3, total1=3, total2=total3=total4=2, total2=total3=total4=2,N N1 1,N,N2 2,N,N3 3,N,N4 4的連線都跨越電路板的連線都跨越電路板2 2和和3 360 算法效率 在每個結(jié)點(diǎn)處, 函數(shù)

33、Backtrack花費(fèi)O(m)時間計(jì)算每個兒子結(jié)點(diǎn)的密度. 排列樹的搜索時間為O(n!). 算法耗費(fèi)為O(mn!).615.12 連續(xù)郵資問題p假設(shè)國家發(fā)行了n種不同面值的郵票種不同面值的郵票，并且規(guī)定每張信封上最多只允許貼貼mm張郵票張郵票。p連續(xù)郵資問題要求連續(xù)郵資問題要求:對于給定的n和m的值，給出郵票面值的最佳設(shè)計(jì)，使得在1張信封上可貼出從郵資從郵資1開始開始，增量為增量為1的最大連續(xù)郵資區(qū)間。62 p例如: 當(dāng)n=5和m=4時， 設(shè)解為X=,其中x1=1,并且滿足： x1x2x5p面值為X=(1, 3, 11, 15, 32)的5種郵票, 可以貼出郵資的最大連續(xù)郵資區(qū)間是1到70。p

34、若若X=, 則郵資連續(xù)區(qū)間為則郵資連續(xù)區(qū)間為1-4.63算法設(shè)計(jì)：解向量：用n元組x1: n表示n種不同的郵票面值，并約定它們從小到大排列。x1=1是唯一的選擇。此時最大連續(xù)郵資區(qū)間是1: m. x2的取值范圍是2: m+1可行性約束函數(shù)：已選定x1: i-1，其最大連續(xù)郵資區(qū)間是1: r，接下來xi的取值范圍是xi-1+1: r+1。方法：回溯法，用一棵樹來表示解空間。 樹結(jié)點(diǎn)的度隨x的值變化l代碼程序見p171-17364 5.13 回溯法效率分析通過前面具體實(shí)例的討論容易看出，回溯算法的效率在很大程度上依賴于以下因素：產(chǎn)生xk的時間；滿足顯約束的xk值的個數(shù)；計(jì)算約束函數(shù)constrai

35、nt的時間；計(jì)算上界函數(shù)bound的時間；滿足約束函數(shù)和上界函數(shù)約束的所有xk的個數(shù)。p好的約束函數(shù)能顯著地減少所生成的結(jié)點(diǎn)數(shù)。但這樣的約束函數(shù)往往計(jì)算量較大。p選擇約束函數(shù)時, 通常存在生成結(jié)點(diǎn)數(shù)與約束函數(shù)計(jì)算量之間的折衷。65重排原理p在搜索試探時，選取xi的值順序是任意的。在其它條件相當(dāng)在其它條件相當(dāng)?shù)那疤嵯?，讓可取值最少的的前提下，讓可取值最少的xi優(yōu)先優(yōu)先。p下圖中關(guān)于同一問題的2棵不同解空間樹，可以體會到這種策略的潛力。圖(a)中，從第1層剪去1棵子樹，則從所有應(yīng)當(dāng)考慮的3元組中一次消去12個3元組(葉結(jié)點(diǎn))。對于圖(b)，雖然同樣從第1層剪去1棵子樹，卻只從應(yīng)當(dāng)考慮的3元組中消去

36、8個3元組。前者的效果明顯比后者好。(a)(b)66估計(jì)回溯算法的結(jié)點(diǎn)數(shù)目和平均效率估計(jì)回溯算法的結(jié)點(diǎn)數(shù)目和平均效率 蒙特卡羅方法蒙特卡羅方法主要思想主要思想: :在解空間樹上產(chǎn)生一條隨機(jī)的路徑在解空間樹上產(chǎn)生一條隨機(jī)的路徑, ,并沿此路徑估算并沿此路徑估算解空間樹中滿足約束條件的結(jié)點(diǎn)總數(shù)解空間樹中滿足約束條件的結(jié)點(diǎn)總數(shù). . Monte Carlo方法的算法步驟方法的算法步驟: 1從根開始，隨機(jī)選擇一條路經(jīng)，直到不能分支為止從根開始，隨機(jī)選擇一條路經(jīng)，直到不能分支為止, 從從x1, x2, , 依次對依次對xi賦值，每個賦值，每個xi的值是從當(dāng)時的路徑中隨機(jī)選取，的值是從當(dāng)時的路徑中隨機(jī)選取

37、，直到向量不能擴(kuò)張為止直到向量不能擴(kuò)張為止. 2假定搜索樹的其他分支與以上隨機(jī)選出的路徑一樣，計(jì)算假定搜索樹的其他分支與以上隨機(jī)選出的路徑一樣，計(jì)算搜索樹的結(jié)點(diǎn)數(shù)。搜索樹的結(jié)點(diǎn)數(shù)。 3重復(fù)步驟重復(fù)步驟1和和2，將結(jié)點(diǎn)數(shù)進(jìn)行概率平均。，將結(jié)點(diǎn)數(shù)進(jìn)行概率平均。67算法算法Monte Carlo 1sum0; /sum為為t次結(jié)點(diǎn)平均數(shù)次結(jié)點(diǎn)平均數(shù)2for i1 to t do /取樣次數(shù)取樣次數(shù)t3. mEstimate(n); /m為本次結(jié)點(diǎn)總數(shù)為本次結(jié)點(diǎn)總數(shù)4. sumsum+m; 5. sumsum/t;68 m為本次取樣結(jié)點(diǎn)總數(shù)，為本次取樣結(jié)點(diǎn)總數(shù)，k為層數(shù)，為層數(shù)，r為本層分支數(shù)為本層分支數(shù), n為樹的為樹的層數(shù)層數(shù), mi為第為第i層滿足約束條件的結(jié)點(diǎn)數(shù)層滿足約束條件的結(jié)點(diǎn)數(shù). 算法算法Estimate(n) /估算回溯法生成的結(jié)點(diǎn)數(shù)估算回溯法生成的結(jié)點(diǎn)數(shù) 1. m1; r1; k1; 2. While k n do 3. SetType T = x