算法設(shè)計與分析王紅梅第二版第8章_回溯法

1、 在現(xiàn)實世界中，很多問題沒有（至少目前沒有）有效的算法，在現(xiàn)實世界中，很多問題沒有（至少目前沒有）有效的算法，這些問題的解只能通過窮舉搜索來得到。只有滿足約這些問題的解只能通過窮舉搜索來得到。只有滿足約束條件的解才是可行解，只有滿足目標(biāo)函數(shù)的解才是束條件的解才是可行解，只有滿足目標(biāo)函數(shù)的解才是最優(yōu)解，這就有可能避免無效的搜索，提高搜索效率。最優(yōu)解，這就有可能避免無效的搜索，提高搜索效率?；厮莘ê头种藿绶ň鶎儆谟薪M織的系統(tǒng)化搜索技術(shù)，可看作回溯法和分支限界法均屬于有組織的系統(tǒng)化搜索技術(shù)，可看作是窮舉搜索的改進(jìn)。是窮舉搜索的改進(jìn)。蠻力法：生成問題的所有可能解，再去評估是否滿足約束條件；蠻力法：生

2、成問題的所有可能解，再去評估是否滿足約束條件；回溯法：每次只構(gòu)造可能解的一部分，然后評估這個部分解，回溯法：每次只構(gòu)造可能解的一部分，然后評估這個部分解，如果有可能導(dǎo)致一個完整解，則對其進(jìn)一步構(gòu)造，否如果有可能導(dǎo)致一個完整解，則對其進(jìn)一步構(gòu)造，否則不必繼續(xù)構(gòu)造這個部分解。這樣可以避免搜索所有則不必繼續(xù)構(gòu)造這個部分解。這樣可以避免搜索所有的可能解，適用于求解組合數(shù)量較大的問題。的可能解，適用于求解組合數(shù)量較大的問題?；谒阉鞯乃惴ㄔO(shè)計技術(shù)基于搜索的算法設(shè)計技術(shù)教學(xué)重點教學(xué)重點回溯法的設(shè)計思想，各種經(jīng)典問題的回溯思想回溯法的設(shè)計思想，各種經(jīng)典問題的回溯思想教學(xué)難點教學(xué)難點批處理作業(yè)調(diào)度問題的回溯算

3、法批處理作業(yè)調(diào)度問題的回溯算法教學(xué)內(nèi)容及目教學(xué)內(nèi)容及目標(biāo)標(biāo)知識點知識點教學(xué)要求教學(xué)要求了解了解理解理解掌握掌握熟練掌握熟練掌握問題的解空間樹問題的解空間樹回溯法的設(shè)計思想回溯法的設(shè)計思想回溯法的時間性能回溯法的時間性能圖著色問題圖著色問題哈密爾頓回路問題哈密爾頓回路問題八皇后問題八皇后問題批處理作業(yè)調(diào)度問題批處理作業(yè)調(diào)度問題學(xué)習(xí)目標(biāo)本章要點本章要點8.1 概概 述述 8.2 圖問題中的回溯法圖問題中的回溯法8.3 組合問題中的回溯法組合問題中的回溯法8.1 概概 述述 8.1.1 問題的解空間問題的解空間8.1.2 回溯法的設(shè)計思想回溯法的設(shè)計思想8.1.3 回溯法的時間性能回溯法的時間性能概

4、述概述 -問題的解空間問題的解空間 概述概述 -問題的解空間問題的解空間 (a) 二維搜索空間無解 (b) 三維搜索空間的解 圖8.1 錯誤的解空間將不能搜索到正確答案概述概述 -問題的解空間問題的解空間 概述概述 -問題的解空間問題的解空間 n回溯法回溯法“可能解可能解”及及“解空間解空間”的表達(dá)的表達(dá)n 可能解的表示可能解的表示：用：用等長向量等長向量 X=(x1, x2, , xn)，其中分量，其中分量 xi (1in) 的的取值范圍取值范圍是某個有限集合是某個有限集合 Si=ai1, ai2, , airi，所，所有可能的解向量構(gòu)成了問題的有可能的解向量構(gòu)成了問題的解空間解空間。 概述

5、概述 -問題的解空間問題的解空間 n 解空間表達(dá)解空間表達(dá)：用：用解空間樹解空間樹（Solution Space Trees）/也稱也稱狀態(tài)空間樹狀態(tài)空間樹的方式組織：的方式組織：n第第1層層（根結(jié)點）：表示搜索的（根結(jié)點）：表示搜索的初始狀態(tài)初始狀態(tài)n第第2層結(jié)點層結(jié)點：表示對解向量的第一個分量做出選擇后：表示對解向量的第一個分量做出選擇后到達(dá)的狀態(tài)到達(dá)的狀態(tài)n第第1層到第層到第2層間層間邊上標(biāo)出對第一個分量選擇的結(jié)果邊上標(biāo)出對第一個分量選擇的結(jié)果n依此類推依此類推，從根結(jié)點，從根結(jié)點葉結(jié)點的路徑葉結(jié)點的路徑構(gòu)成了解空間的一個可能解構(gòu)成了解空間的一個可能解。n可行解：可行解：滿足約束條件的解

6、，滿足約束條件的解，解空間中的一個子集解空間中的一個子集n最優(yōu)解：最優(yōu)解：使目標(biāo)函數(shù)取極值使目標(biāo)函數(shù)取極值(極大或極小極大或極小)的可行解，一個或少數(shù)幾個的可行解，一個或少數(shù)幾個例：例：貨郎擔(dān)問題，有貨郎擔(dān)問題，有nn種可能解。種可能解。n!種可行解，只有一個或種可行解，只有一個或幾個是最優(yōu)解幾個是最優(yōu)解。例：例：背包問題，有背包問題，有2n種可能解，有些是可行解，只有一個或種可能解，有些是可行解，只有一個或幾個是最優(yōu)解幾個是最優(yōu)解n有些問題，只要可行解，不需要最優(yōu)解有些問題，只要可行解，不需要最優(yōu)解：例：八皇后問題例：八皇后問題和和圖的著色圖的著色問題問題概述概述 -問題的解空間問題的解空間

7、 例：對于例：對于n=3 的的0/1 背包問題，其解空間樹如圖背包問題，其解空間樹如圖8.2 所示，樹中所示，樹中的的8個葉子結(jié)點分別代表該個葉子結(jié)點分別代表該問題的問題的 8 個可能解個可能解。 對物品對物品1的選擇的選擇對物品對物品3的選擇的選擇對物品對物品2的選擇的選擇1111110000000112345781112141531069概述概述 -問題的解空間問題的解空間 例：對于例：對于n=4 的的TSP 問題，圖問題，圖8.3是是經(jīng)壓縮后的解空間樹經(jīng)壓縮后的解空間樹，樹中的，樹中的24 個葉子結(jié)個葉子結(jié)點分別代表該問題的點分別代表該問題的24 個可能解，例如個可能解，例如結(jié)點結(jié)點5

8、代表一個可能解，路徑為代表一個可能解，路徑為 12341，長度為各邊代價之和，長度為各邊代價之和。 圖圖8.3 n=4 的的 TSP 問題問題經(jīng)壓縮后經(jīng)壓縮后解空間樹解空間樹2434223434131424121233121341313123212142414343224341231241345710121517212326283133 37 3942444749525457596264469111416202225273032 363841434648515356586163381319242935404550556021834241123434概述概述 -問題的解空間問題的解空間 8.1

9、概概 述述 8.1.1 問題的解空間問題的解空間8.1.2 回溯法的設(shè)計思想回溯法的設(shè)計思想8.1.3 回溯法的時間性能回溯法的時間性能回溯法的設(shè)計思想回溯法的設(shè)計思想 回溯法從根結(jié)點出發(fā)，按照回溯法從根結(jié)點出發(fā)，按照深度優(yōu)先策略遍歷深度優(yōu)先策略遍歷解空間樹，搜索滿足約束條件的解。在搜索至樹中解空間樹，搜索滿足約束條件的解。在搜索至樹中任一結(jié)點時，先任一結(jié)點時，先判斷判斷該結(jié)點對應(yīng)的部分解是否滿足該結(jié)點對應(yīng)的部分解是否滿足約束條件約束條件/是否超出是否超出目標(biāo)函數(shù)目標(biāo)函數(shù)的界，也就是判斷該結(jié)的界，也就是判斷該結(jié)點是否點是否包含包含問題的（最優(yōu)）解，問題的（最優(yōu)）解，如果肯定不包含，如果肯定不包

10、含，則跳過對以該結(jié)點為根的子樹的搜索，即所謂則跳過對以該結(jié)點為根的子樹的搜索，即所謂剪枝剪枝（Pruning）；）；否則否則，進(jìn)入以該結(jié)點為根的子樹，繼，進(jìn)入以該結(jié)點為根的子樹，繼續(xù)按照深度優(yōu)先策略搜索。續(xù)按照深度優(yōu)先策略搜索。例：對于例：對于n=3 的的0/1 背包問題，其參數(shù)如下：背包問題，其參數(shù)如下： 重量重量W=20, 15,10，價值價值V=20, 30, 25，背包容量背包容量C=C=25下圖是解空間樹結(jié)構(gòu)結(jié)果，從根結(jié)點出發(fā)，其搜索過程如下：下圖是解空間樹結(jié)構(gòu)結(jié)果，從根結(jié)點出發(fā)，其搜索過程如下： 1不可行解不可行解價值價值=20價值價值=55 價值價值=30 價值價值=25價值價值

11、=0111100000011238111214151310697不可行解不可行解回溯法的設(shè)計思想回溯法的設(shè)計思想X1=1, V1=20C=25-20=5X2=1, W2=15V2=30,C=5X2=0,V=20C=5X3=0,V=20C=5可行解可行解1X1=0, V=0C=25X2=1, V=30C=10可行解可行解2 可行解可行解3可行解可行解4可行解可行解5在在2叉完全樹叉完全樹中，結(jié)點總數(shù)有：中，結(jié)點總數(shù)有：1+21+22+222=151不可行解不可行解價值價值=20價值價值=55 價值價值=30 價值價值=25價值價值=0111100000011238111214151310697不

12、可行解不可行解回溯法的設(shè)計思想回溯法的設(shè)計思想 1045不可行解不可行解回溯法的設(shè)計思想回溯法的設(shè)計思想n需要注意的是：需要注意的是： 問題的解空間樹是虛擬的問題的解空間樹是虛擬的，并不需要在算法運行時構(gòu)造一，并不需要在算法運行時構(gòu)造一棵真正的樹結(jié)構(gòu)，棵真正的樹結(jié)構(gòu)，只需要存儲從根結(jié)點到當(dāng)前結(jié)點的路徑只需要存儲從根結(jié)點到當(dāng)前結(jié)點的路徑。8.1 概概 述述 8.1.1 問題的解空間問題的解空間8.1.2 回溯法的設(shè)計思想回溯法的設(shè)計思想8.1.3 回溯法的時間性能回溯法的時間性能回溯法的時間性能回溯法的時間性能 一般情況下，在問題的解向量一般情況下，在問題的解向量 X=( x1, x2, , x

13、n )中，分量中，分量 xi (1in) 的取值范圍為某個有限集合的取值范圍為某個有限集合Si=ai1, ai2, , airi，因此，問題的，因此，問題的解空間由笛卡兒積解空間由笛卡兒積 A=S1S2Sn 構(gòu)成，并且第構(gòu)成，并且第 1 層的根結(jié)點有層的根結(jié)點有|S1| 棵子樹，則第棵子樹，則第2層共有層共有 |S1| 個結(jié)點，第個結(jié)點，第 2 層的每個結(jié)層的每個結(jié)點有點有 |S2| 棵子樹，則第棵子樹，則第3層共有層共有 |S1|S2| 個結(jié)點；個結(jié)點； 依此類推依此類推，第，第n+1層共有層共有|S1|S2|Sn| 個結(jié)個結(jié)點，他們都是點，他們都是葉子結(jié)點葉子結(jié)點，代表問題的，代表問題的所

14、有可能解所有可能解。在用回溯法求解問題時，常用到在用回溯法求解問題時，常用到兩種典型的解空間樹兩種典型的解空間樹： （1）子集樹子集樹：當(dāng)問題是從：當(dāng)問題是從n 個元素的個元素的集合集合中找出中找出滿足某種性質(zhì)滿足某種性質(zhì)的的子集子集時，相應(yīng)的時，相應(yīng)的解空間樹稱為子集樹解空間樹稱為子集樹。在子集樹中，。在子集樹中，|S1|=|S2|=|Sn|=c，即，即每個結(jié)點有相同數(shù)目的子樹每個結(jié)點有相同數(shù)目的子樹，當(dāng)，當(dāng)c=2，則子集樹中共有則子集樹中共有 2n 個葉子結(jié)點，因此，遍歷子集樹需要個葉子結(jié)點，因此，遍歷子集樹需要(2n)時間。如：時間。如：0/1背包背包（2）排列樹排列樹：當(dāng)問題是確定：當(dāng)

15、問題是確定 n 個元素個元素滿足某種性質(zhì)滿足某種性質(zhì)的的排列排列時，時，相應(yīng)的相應(yīng)的解空間樹稱為排列樹解空間樹稱為排列樹。在排列樹中，通常情況下，。在排列樹中，通常情況下，|S1|=n，|S2|=n-1，|Sn|=1，所以，排列樹中共有，所以，排列樹中共有n! 個葉子結(jié)點，因個葉子結(jié)點，因此，遍歷排列樹需要此，遍歷排列樹需要(n!)時間。時間。如：如：TSP問題問題回溯法的時間性能回溯法的時間性能 回溯法實際上屬于蠻力窮舉法，當(dāng)然不能指回溯法實際上屬于蠻力窮舉法，當(dāng)然不能指望它有很好的最壞時間復(fù)雜性（指數(shù)階）。其有望它有很好的最壞時間復(fù)雜性（指數(shù)階）。其有效性往往體現(xiàn)在當(dāng)問題規(guī)模效性往往體現(xiàn)在

16、當(dāng)問題規(guī)模n很大時，在搜索過很大時，在搜索過程中對問題的解空間樹大量剪枝。程中對問題的解空間樹大量剪枝。但是但是很難估計出在搜索過程中所產(chǎn)生的結(jié)點很難估計出在搜索過程中所產(chǎn)生的結(jié)點數(shù)數(shù)，這也是分析回溯法的時間性能的主要困難。，這也是分析回溯法的時間性能的主要困難?；厮莘ǖ臅r間性能回溯法的時間性能 本章要點本章要點8.1 概概 述述 8.2 圖問題中的回溯法圖問題中的回溯法8.3 組合問題中的回溯法組合問題中的回溯法8.2 圖問題中的回溯法圖問題中的回溯法 8.2.1 圖著色問題圖著色問題 8.2.2 哈密頓回路問題哈密頓回路問題圖著色問題圖著色問題 圖著色問題描述為圖著色問題描述為：給定無向連

17、通圖：給定無向連通圖G=(V, E)和和正整數(shù)正整數(shù)m，求最小的整數(shù)，求最小的整數(shù)m，當(dāng)用，當(dāng)用m種顏色對種顏色對G中的中的頂點著色，使得頂點著色，使得任意兩個相鄰頂點著色不同任意兩個相鄰頂點著色不同。 由于用由于用m 種顏色為無向圖種顏色為無向圖 G=(V, E) 著色，其中，著色，其中，V 的頂?shù)捻旤c個數(shù)為點個數(shù)為n，可以用一個，可以用一個 n 元組元組 C=(c1, c2, , cn) 來描述圖的一來描述圖的一種可能著色，其中，種可能著色，其中，ci1, 2, , m(1in) 表示賦予頂點表示賦予頂點i 的的顏色。顏色。 例如：例如：5 元組元組 (1, 2, 2, 3, 1) 表示對

18、表示對5 個頂點無向圖的著色方案之個頂點無向圖的著色方案之一，其中：一，其中： 頂點頂點 1: 著顏色著顏色1；頂點頂點 2 : 著顏色著顏色2；頂點頂點 3 : 著顏色著顏色 2 5 元組元組 (1, 3, 2, 3, 1)表示另一種著色方案表示另一種著色方案 如用如用m種顏色給種顏色給n個頂點的圖著色，有個頂點的圖著色，有mn種可能的著色組合種可能的著色組合圖著色問題圖著色問題 圖著色問題圖著色問題 三著色具有三個頂點的圖的狀態(tài)空間樹頂點頂點1的的m種著色種著色圖著色問題圖著色問題 D=1ACBDE1234567891011121314A=1B=2C=3D=3E=1(a) 一個無向圖一個無

19、向圖 (b) 回溯法搜索空間回溯法搜索空間圖圖8.8 回溯法求解圖著色問題示例回溯法求解圖著色問題示例圖著色問題圖著色問題 頂點頂點設(shè)數(shù)組colorn表示頂點的著色情況，回溯法求解m著色問題的算法如下： 算法算法8.1圖著色問題圖著色問題 1將數(shù)組colorn初始化為0； 2k=1; 3while (k=1) 3.1 依次考察每一種顏色，若頂點k的著色與其他頂點的著色不發(fā)生沖突，則轉(zhuǎn)步驟3.2；否則，搜索下一個顏色； 3.2 若頂點已全部著色，則輸出數(shù)組colorn，返回； 3.3 否則， 3.3.1 若頂點k是一個合法著色，則k=k+1，轉(zhuǎn)步驟3處理下一個頂點； 3.3.2 否則，重置頂點k

20、的著色情況，k=k-1，轉(zhuǎn)步驟3回溯；圖著色問題圖著色問題 算法算法8.2 圖著色問題圖著色問題 void GraphColor (int n, int c , int m) /所有數(shù)組下標(biāo)從所有數(shù)組下標(biāo)從1開始開始 for (i=1; i=1) colork=colork+1; while (colork=m) if Ok(k) break; else colork=colork+1; /搜索下一個顏色搜索下一個顏色 if (colork=m & k= =n) /求解完畢，輸出解求解完畢，輸出解 for (i=1; i=n; i+) cout=1) 3.1 xk=xk+1，搜索下一個

21、頂點，搜索下一個頂點; 3.2 若若(n個頂點沒有被窮舉完個頂點沒有被窮舉完) 執(zhí)行下列操作執(zhí)行下列操作 3.2.1 若若(頂點頂點xk不在哈密頓回路上不在哈密頓回路上&(xk-1,xk)E)， 轉(zhuǎn)步驟轉(zhuǎn)步驟3.3; 3.2.2 否則，否則，xk=xk+1，搜索下一個頂點；，搜索下一個頂點； 3.3 若數(shù)組若數(shù)組 xn已形成哈密頓路徑，則輸出數(shù)組已形成哈密頓路徑，則輸出數(shù)組xn，算法結(jié)束；，算法結(jié)束； 3.4 否則，否則， 3.4.1 若數(shù)組若數(shù)組 xn 構(gòu)成哈密頓路徑的部分解，構(gòu)成哈密頓路徑的部分解， 則則 k=k+1，轉(zhuǎn)步驟，轉(zhuǎn)步驟3； 3.4.2 否則，重置否則，重置 xk，k=

22、k-1，取消頂點，取消頂點 xk 的訪問標(biāo)志，的訪問標(biāo)志， 轉(zhuǎn)步驟轉(zhuǎn)步驟3；哈密頓回路問題哈密頓回路問題 算法算法8.4哈密頓回路問題哈密頓回路問題 void Hamiton(int n, int x , int c ) /所有數(shù)組下標(biāo)從所有數(shù)組下標(biāo)從1開始開始 for (i=1; i=1) xk=xk+1; /搜索下一頂點搜索下一頂點 while (xk=1) 3.1 把皇后把皇后k擺放在下一列的位置，即擺放在下一列的位置，即xk+; 3.2 從從xk開始依次考察每一列，如果皇后開始依次考察每一列，如果皇后k擺放在擺放在xk位置不發(fā)生沖位置不發(fā)生沖突，則轉(zhuǎn)步驟突，則轉(zhuǎn)步驟3.3;否則否則xk

23、+試探下一列試探下一列; 3.3 若若n個皇后已全部擺放，則輸出一個解，算法結(jié)束；個皇后已全部擺放，則輸出一個解，算法結(jié)束； 3.4 若尚有皇后沒擺放，則若尚有皇后沒擺放，則k+，轉(zhuǎn)步驟，轉(zhuǎn)步驟3擺放下一個皇后；擺放下一個皇后； 3.5 若若xk出界，則回溯，出界，則回溯，xk=-1,k-,轉(zhuǎn)步驟轉(zhuǎn)步驟3重新擺放皇后重新擺放皇后k;4. 退出循環(huán)，說明退出循環(huán)，說明n皇后問題無解；皇后問題無解；C+描述八皇后問題八皇后問題 八皇后問題八皇后問題)(n8.3 組合問題中的回溯法組合問題中的回溯法 8.3.1 八皇后問題八皇后問題 8.3.2 批處理作業(yè)調(diào)度問題批處理作業(yè)調(diào)度問題批處理作業(yè)調(diào)度問題

24、批處理作業(yè)調(diào)度問題 n 批處理作業(yè)調(diào)度問題批處理作業(yè)調(diào)度問題? ? 設(shè)有設(shè)有n 個作業(yè)個作業(yè) 1, 2, , n 要在兩臺機器上處理：要在兩臺機器上處理： 作業(yè)作業(yè)i 先先由機器由機器1處理處理( (所需時間為所需時間為ai ) ) 再由再由機器機器2 處理處理 (所需時間為所需時間為bi ) (1in） 批處理作業(yè)調(diào)度問題批處理作業(yè)調(diào)度問題： 要求確定這要求確定這n個作業(yè)的最優(yōu)處理順序，使得從第個作業(yè)的最優(yōu)處理順序，使得從第1個作業(yè)在機器個作業(yè)在機器1上處理開始，到最后一個作業(yè)在機器上處理開始，到最后一個作業(yè)在機器2上處理結(jié)束上處理結(jié)束所需時間最少所需時間最少。 批處理作業(yè)調(diào)度問題批處理作業(yè)

25、調(diào)度問題 作業(yè)作業(yè)1:2作業(yè)作業(yè)2:3作業(yè)作業(yè)3:2空閑空閑:2作業(yè)作業(yè)1:1機器機器1機器機器2作業(yè)作業(yè)2:1作業(yè)作業(yè)3:3(a) 調(diào)度方案調(diào)度方案(1, 2, 3)，最后，最后完成時間為完成時間為10作業(yè)作業(yè)1:2作業(yè)作業(yè)2:3作業(yè)作業(yè)3:2空閑空閑:2作業(yè)作業(yè)1:1機器機器1機器機器2作業(yè)作業(yè)2:1作業(yè)作業(yè)3:3(b) 調(diào)度方案調(diào)度方案(1, 3, 2)，最后，最后完成時間為完成時間為8批處理作業(yè)調(diào)度問題批處理作業(yè)調(diào)度問題 *作業(yè)作業(yè)2:3作業(yè)作業(yè)1:2作業(yè)作業(yè)3:2空閑空閑作業(yè)作業(yè)2:1機器機器1機器機器2作業(yè)作業(yè)1:1作業(yè)作業(yè)3:3(c) 調(diào)度方案調(diào)度方案(2, 1, 3)，最后，最后完成時間為完成時間為10作業(yè)作業(yè)2:3作業(yè)作業(yè)3:2作業(yè)作業(yè)1:2空閑空閑:3作業(yè)作業(yè)2:1機器機器1機器機器2作業(yè)作業(yè)1:1作業(yè)作業(yè)3:3(d) 調(diào)度方案調(diào)度方案(2