第5章-回溯及分支限界

1、1第第5章章 回溯與分支限界回溯與分支限界5.1 回溯算法的基本思想和適用條件回溯算法的基本思想和適用條件5.2 回溯算法的設(shè)計步驟回溯算法的設(shè)計步驟5.3 回溯算法的效率估計和改進途徑回溯算法的效率估計和改進途徑5.4 分支限界分支限界 5.4.1 背包問題背包問題 5.4.2 最大團問題最大團問題 5.4.3 貨郎問題貨郎問題 5.4.4 圓排列問題圓排列問題 5.4.5 連續(xù)郵資問題連續(xù)郵資問題25.1回溯算法的基本思想和適用條件回溯算法的基本思想和適用條件5.1.1 幾個典型例子幾個典型例子 四后問題四后問題0-1背包問題背包問題貨郎問題（貨郎問題（TSP）5.1.2 回溯算法的適用條

2、件回溯算法的適用條件35.1.1幾個典型例子幾個典型例子例例5.1 n后問題后問題 4后問題：解是一個后問題：解是一個4維向量，維向量，（放置列號）（放置列號） 搜索空間：搜索空間：4叉樹叉樹 8后問題：解是一個后問題：解是一個8維向量，維向量，搜索空間：搜索空間：8叉樹，叉樹， 一個解：一個解： 4 實例：實例：V=12,11,9,8, W=8,6,4,3, B=13 結(jié)點：向量結(jié)點：向量（子集的部分特征向量）（子集的部分特征向量） 搜索空間：搜索空間：子集樹子集樹，2n片樹葉片樹葉 可行解：可行解： x1=0, x2=1, x3=1, x4=1. 價值價值:28，重量，重量:13 可行解：

3、可行解： x1=1, x2=0, x3=1, x4=0. 價值價值:21，重量，重量:12例例5.2 0-1背包問題背包問題5 對應(yīng)于巡回路線：對應(yīng)于巡回路線：12 4 3 1長度：長度：5+2+7+9=23 例例5.3 貨郎問題貨郎問題12345249713為巡回路線為巡回路線搜索空間：排列樹搜索空間：排列樹, (n-1)!片樹葉片樹葉實例：實例：6回溯算法的基本思想回溯算法的基本思想(1) 適用問題：求解搜索問題和優(yōu)化問題適用問題：求解搜索問題和優(yōu)化問題(2) 搜索空間：樹，結(jié)點對應(yīng)部分解向量，樹葉對應(yīng)可行解搜索空間：樹，結(jié)點對應(yīng)部分解向量，樹葉對應(yīng)可行解(3) 搜索過程：采用系統(tǒng)的方法隱

4、含遍歷搜索樹搜索過程：采用系統(tǒng)的方法隱含遍歷搜索樹(4) 搜索策略：深度優(yōu)先，寬度優(yōu)先，函數(shù)優(yōu)先，寬深結(jié)合等搜索策略：深度優(yōu)先，寬度優(yōu)先，函數(shù)優(yōu)先，寬深結(jié)合等(5) 結(jié)點分支判定條件：結(jié)點分支判定條件：滿足約束條件滿足約束條件-分支擴張解向量分支擴張解向量不滿足約束條件，回溯到該結(jié)點的父結(jié)點不滿足約束條件，回溯到該結(jié)點的父結(jié)點(6) 結(jié)點狀態(tài)：動態(tài)生成結(jié)點狀態(tài)：動態(tài)生成白結(jié)點白結(jié)點(尚未訪問尚未訪問)；灰結(jié)點灰結(jié)點(正在訪問該結(jié)點為根的子樹正在訪問該結(jié)點為根的子樹); 黑結(jié)點黑結(jié)點(該結(jié)點為根的子樹遍歷完成該結(jié)點為根的子樹遍歷完成)(7) 存儲：當(dāng)前路徑存儲：當(dāng)前路徑7設(shè)設(shè) P(x1, x2,

5、 , xi) 為真表示向量為真表示向量 滿足某個性滿足某個性質(zhì)質(zhì) (n后問題中后問題中i 個皇后放置在彼此不能攻擊的位置）個皇后放置在彼此不能攻擊的位置）多米諾性質(zhì)：多米諾性質(zhì)：例例5.4 求不等式的整數(shù)解求不等式的整數(shù)解 5x1+4x2 x3 10, 1 xi 3, i=1,2,3 P(x1, , xk) : 意味將意味將x1, x2, , xk代入原不等式的相應(yīng)部分代入原不等式的相應(yīng)部分使得左邊小于等于使得左邊小于等于10不滿足多米諾性質(zhì)不滿足多米諾性質(zhì)變換：變換： 令令 x3=3 x3, 5x1+4x2+x3 13 ，1 x1, x2 3, 0 x3 2 nkxxxPxxxPkk 0),

6、.,(),.,(211215.1.2 回溯算法的適用條件回溯算法的適用條件85.2 回溯算法的設(shè)計步驟回溯算法的設(shè)計步驟(1) 定義搜索問題的解向量和每個分量的取值范圍定義搜索問題的解向量和每個分量的取值范圍解向量為解向量為 確定確定 xi 的可能取值的集合為的可能取值的集合為 Xi , i = 1, 2, , n. (2) 當(dāng)當(dāng) x1, x2, , xk-1 確定以后計算確定以后計算 xk 取值集合取值集合Sk, Sk Xk (3) 確定結(jié)點兒子的排列規(guī)則確定結(jié)點兒子的排列規(guī)則(4) 判斷是否滿足多米諾性質(zhì)判斷是否滿足多米諾性質(zhì)(5) 搜索策略搜索策略-深度優(yōu)先、寬度優(yōu)先等深度優(yōu)先、寬度優(yōu)先

7、等(6) 確定每個結(jié)點分支約束條件確定每個結(jié)點分支約束條件(7) 確定存儲搜索路徑的數(shù)據(jù)結(jié)構(gòu)確定存儲搜索路徑的數(shù)據(jù)結(jié)構(gòu)9算法算法5.1 ReBack(k) 1. if kn then 是解是解 2. else while Sk do 3. xkSk中最小值中最小值 4. SkSkxk 5. 計算計算Sk+1 6. ReBack(k+1) 算法算法5.2 ReBacktrack(n)輸入：輸入：n輸出：所有的解輸出：所有的解 1. for k1 to n 計算計算 Xk 2. ReBack(1) 回溯算法的遞歸實現(xiàn)回溯算法的遞歸實現(xiàn)10算法算法5.3 Backtrack(n) 輸入：輸入：n 輸

8、出：所有的解輸出：所有的解 1. 對于對于i =1, 2, , n 確定確定Xi 2. k1 3. 計算計算Sk 4. while Sk do 5. xkSk中最小值中最小值; SkSkxk 6. if kn then 7. kk+1; 計算計算Sk 8. else 是解是解 9. if k1 then kk-1； goto 4 回溯算法的迭代實現(xiàn)回溯算法的迭代實現(xiàn)11回溯算法解決問題的步驟回溯算法解決問題的步驟回溯算法也叫試探法，它是一種系統(tǒng)地搜索問題的回溯算法也叫試探法，它是一種系統(tǒng)地搜索問題的解的方法。解的方法。用回溯算法解決問題的一般步驟用回溯算法解決問題的一般步驟：1 針對所給問題，

9、定義問題的解空間，它至少包含針對所給問題，定義問題的解空間，它至少包含問題的一個（最優(yōu)）解。問題的一個（最優(yōu)）解。2 確定易于搜索的解空間結(jié)構(gòu)確定易于搜索的解空間結(jié)構(gòu),使得能用回溯法方便使得能用回溯法方便地搜索整個解空間地搜索整個解空間 。3 以深度優(yōu)先的方式搜索解空間，并且在搜索過程以深度優(yōu)先的方式搜索解空間，并且在搜索過程中用中用剪枝函數(shù)剪枝函數(shù)避免無效搜索。避免無效搜索。 回溯法回溯法的搜索過程涉及的結(jié)點（稱為的搜索過程涉及的結(jié)點（稱為搜索空間搜索空間）只是整個解空間樹的一部分，在搜索過程中，通常只是整個解空間樹的一部分，在搜索過程中，通常采用兩種策略避免無效搜索：采用兩種策略避免無效搜

10、索：（1）用）用約束條件約束條件剪去得不到剪去得不到可行解可行解的子樹；的子樹；（2）用）用目標(biāo)函數(shù)目標(biāo)函數(shù)剪去得不到剪去得不到最優(yōu)解最優(yōu)解的子樹。的子樹。這兩類函數(shù)統(tǒng)稱為這兩類函數(shù)統(tǒng)稱為剪枝函數(shù)剪枝函數(shù)（Pruning Function）。）。v 需要注意的是，問題的解空間樹是虛擬的，并不需要注意的是，問題的解空間樹是虛擬的，并不需要在算法運行時構(gòu)造一棵真正的樹結(jié)構(gòu)，只需要需要在算法運行時構(gòu)造一棵真正的樹結(jié)構(gòu)，只需要存儲從根結(jié)點到當(dāng)前結(jié)點的路徑。存儲從根結(jié)點到當(dāng)前結(jié)點的路徑?；厮莘ǖ那蠼膺^程回溯法的求解過程 由于問題的解向量由于問題的解向量X=(x1, x2, , xn)中的每個分量中的每個

11、分量xi(1in)都屬于一個有限集合都屬于一個有限集合Si=ai1, ai2, , airi，因此，因此，回溯法可以按某種順序（例如字典序）依次考察笛卡兒回溯法可以按某種順序（例如字典序）依次考察笛卡兒積積S1S2Sn中的元素。中的元素。 初始時，令解向量初始時，令解向量X為空，然后，從根結(jié)點出發(fā)，選為空，然后，從根結(jié)點出發(fā)，選擇擇S1的第一個元素作為解向量的第一個元素作為解向量X的第一個分量，即的第一個分量，即x1= a11，如果如果X=(x1)是問題的部分解，則繼續(xù)擴展解向量是問題的部分解，則繼續(xù)擴展解向量X，選擇，選擇S2的第一個元素作為解向量的第一個元素作為解向量X的第的第2個分量，否

12、則，選擇個分量，否則，選擇S1的下一個元素作為解向量的下一個元素作為解向量X的第一個分量，即的第一個分量，即x1= a12。依此類推，一般情況下，如果依此類推，一般情況下，如果X=(x1, x2, , xi)是問題的部是問題的部分解，則選擇分解，則選擇Si+1的第一個元素作為解向量的第一個元素作為解向量X的第的第i+1個分個分量時，有下面三種情況：量時，有下面三種情況：（1）如果）如果X=(x1, x2, , xi1)是問題的是問題的最終解最終解，則輸出這個解。，則輸出這個解。如果問題只希望得到一個解，則結(jié)束搜索，否則繼續(xù)搜索其如果問題只希望得到一個解，則結(jié)束搜索，否則繼續(xù)搜索其他解；他解；（

13、2）如果）如果X=(x1, x2, , xi1)是問題的是問題的部分解部分解，則繼續(xù)構(gòu)造解，則繼續(xù)構(gòu)造解向量的下一個分量；向量的下一個分量；（3）如果）如果X=(x1, x2, , xi1)既既不是問題的部分解也不是問題不是問題的部分解也不是問題的最終解的最終解，則存在下面兩種情況：，則存在下面兩種情況： 如果如果xi+1= ai1k不是集合不是集合Si1的最后一個元素，則令的最后一個元素，則令xi+1= ai1k1，即選擇，即選擇Si+1的下一個元素作為解向量的下一個元素作為解向量X的第的第i+1個分量；個分量； 如果如果xi+1= ai1k是集合是集合Si1的最后一個元素，就回溯到的最后一

14、個元素，就回溯到X=(x1, x2, , xi)，選擇，選擇Si的下一個元素作為解向量的下一個元素作為解向量X的第的第i個分量，假個分量，假設(shè)設(shè)xi= aik，如果，如果aik不是集合不是集合Si的最后一個元素，則令的最后一個元素，則令xi= aik1；否則，就繼續(xù)回溯到否則，就繼續(xù)回溯到X=(x1, x2, , xi1)；例例5 裝載問題裝載問題例例5.5 n個集裝箱裝上個集裝箱裝上2艘載重分別為艘載重分別為c1和和c2的輪船，的輪船，wi為集裝為集裝箱箱i的重量，且的重量，且問是否存在一種合理的裝載方案將問是否存在一種合理的裝載方案將n個集裝箱裝上輪船？如個集裝箱裝上輪船？如果有，給出一種

15、方案果有，給出一種方案. 求解思路：令第一船裝載量為求解思路：令第一船裝載量為W1，用回溯算法求使，用回溯算法求使W1-c1達達到最小的裝載方案到最小的裝載方案， 如果如果 回答回答Yes, 否則回答否則回答No. 問題滿足多米諾性質(zhì)，搜索策略：深度優(yōu)先問題滿足多米諾性質(zhì)，搜索策略：深度優(yōu)先 niiccw121211cWwnii 算法算法算法算法5.4 Loading (W,c1), 輸入：集裝箱重量輸入：集裝箱重量W=, c1是第一條船的載重是第一條船的載重輸出：使第一條船裝載最大的方案輸出：使第一條船裝載最大的方案，其中，其中xi=0,11. Sort(W); /對對w1,w2,wn按照從

16、大到小排序按照從大到小排序2. B ; best ; i 1; 3. while i n do 4. if 裝入裝入 i 后重量不超過后重量不超過c15. then B B wi; xi 1; i i+1; else xi0; i i+1; ifB1 and xi=0 do2. i i 1; if xi=1 then xi0; BB+wi; ii+1; 實例實例 W=, c1=152, c2=130復(fù)雜性：復(fù)雜性：W(n)=O(2n)00101290002040308000例例6 圖的著色問題圖的著色問題例例5.6 著色問題：給定無向連通圖著色問題：給定無向連通圖G和和m種顏色，用這些顏色種顏

17、色，用這些顏色給圖的頂點著色，每個頂點一種顏色給圖的頂點著色，每個頂點一種顏色. 要求是：要求是：G 的每條邊的的每條邊的兩個頂點著不同顏色兩個頂點著不同顏色. 給出所有可能的著色方案；如果不存在給出所有可能的著色方案；如果不存在著這樣的方案，則回答著這樣的方案，則回答“No”. 則搜索空間為深度則搜索空間為深度n 的的m叉完全樹叉完全樹. 將顏色編號為將顏色編號為1,2,m， 結(jié)點結(jié)點：x1, x2, , xk 1, 2, ., m, 1 k n，表示頂表示頂點點1著顏色著顏色 x1，頂點，頂點2著顏色著顏色 x2，頂點，頂點 k 著顏色著顏色 xk. 約束條件：該頂點鄰接表中的頂點與該頂點

18、沒有同色；約束條件：該頂點鄰接表中的頂點與該頂點沒有同色；搜索策略：深度優(yōu)先搜索策略：深度優(yōu)先時間：時間：O(nmn)19實例實例12332131231213220提高效率的途徑提高效率的途徑根據(jù)對稱性，只需搜索根據(jù)對稱性，只需搜索1/3的解空間即可的解空間即可. 當(dāng)當(dāng)1和和2確定確定,即即以后，只有以后，只有1個解，因此在個解，因此在為根的子樹中也只有為根的子樹中也只有1個解個解.由于由于3個子樹的對稱性，總共有個子樹的對稱性，總共有6個解個解.進一步分析，在取定進一步分析，在取定以后，不可以擴張成以后，不可以擴張成, 因為因為可以檢查是否有和可以檢查是否有和1,2,3都相鄰的頂點都相鄰的頂

19、點.如果存在如果存在,例如例如7, 則沒則沒有解有解. 所以可以從打叉的結(jié)點回溯，而不必搜索它的子樹所以可以從打叉的結(jié)點回溯，而不必搜索它的子樹.21 5.3 回溯算法的效率估計回溯算法的效率估計 與改進途徑與改進途徑Monte Carlo(蒙特卡羅蒙特卡羅)方法估計搜索樹中的結(jié)點，方法估計搜索樹中的結(jié)點，背景：蒙特卡羅方法于背景：蒙特卡羅方法于20世紀(jì)世紀(jì)40年代美國在年代美國在第二次世界大第二次世界大戰(zhàn)中研制原子彈戰(zhàn)中研制原子彈的的“曼哈頓計劃曼哈頓計劃”計劃的成員烏拉姆和計劃的成員烏拉姆和馮馮諾伊曼首先提出。數(shù)學(xué)家馮諾伊曼首先提出。數(shù)學(xué)家馮諾伊曼用馳名世界的賭諾伊曼用馳名世界的賭城城摩納

20、哥的摩納哥的Monte Carlo 1從根開始，隨機選擇一條路經(jīng)，直到不能分支為止從根開始，隨機選擇一條路經(jīng)，直到不能分支為止, 即從即從x1,x2, 依次對依次對xi 賦值，每個賦值，每個xi 的值是從當(dāng)時的的值是從當(dāng)時的 Si中隨機選取，直到向量不能擴張為止中隨機選取，直到向量不能擴張為止. 2假定搜索樹的其他假定搜索樹的其他 | Si | 1 個分支與以上隨機選出的個分支與以上隨機選出的 路徑一樣，計數(shù)搜索樹的點數(shù)路徑一樣，計數(shù)搜索樹的點數(shù). 3重復(fù)步驟重復(fù)步驟 1 和和 2，將結(jié)點數(shù)進行概率平均，將結(jié)點數(shù)進行概率平均.22算法算法5.6 Monte Carlo 輸入：輸入：n,t 為正

21、整數(shù)，為正整數(shù)，n為皇后數(shù)，為皇后數(shù)，t為抽樣次數(shù)為抽樣次數(shù)輸出：輸出：sum, 即即t 次抽樣路徑長度的平均值次抽樣路徑長度的平均值 1sum 0 /sum為為 t 次結(jié)點平均數(shù)次結(jié)點平均數(shù) 2for i 1 to t do /取樣次數(shù)取樣次數(shù) t 3. m Estimate(n) /m為本次結(jié)點總數(shù)為本次結(jié)點總數(shù) 4. sum sum + m 5. sum sum / t 算法實現(xiàn)算法實現(xiàn)23m為輸出為輸出本次取樣結(jié)點總數(shù)，本次取樣結(jié)點總數(shù)，k 為層數(shù)，為層數(shù)，r1為本層為本層分支數(shù)分支數(shù), r2為上層分支數(shù)，為上層分支數(shù)，n為樹的層數(shù)為樹的層數(shù)算法算法5.7 Estimate(n) 1.

22、 m1; r21; k1 /m為結(jié)點總數(shù)為結(jié)點總數(shù) 2. While k n do 3. if Sk= then return m 4. r1 |Sk|*r2 /r1為擴張后結(jié)點總數(shù)為擴張后結(jié)點總數(shù) 5. m m + r1 / r2為擴張前結(jié)點總數(shù)為擴張前結(jié)點總數(shù) 6. xk 隨機選擇隨機選擇 Sk 的元素的元素 7. r2 r1 8. k k+1 子過程子過程24估計四后搜索樹的結(jié)點數(shù)估計四后搜索樹的結(jié)點數(shù)case1：1+4+4 2+4 2=21case2: 4 4+1=17case3：1+4 1+4 2=13 實例實例Case3: Case1: Case2: 25估計結(jié)果估計結(jié)果假設(shè)假設(shè)

23、4 次抽樣測試：次抽樣測試： case1:1次，次，case2:1次，次，case3:2次，次， 平均結(jié)點數(shù)平均結(jié)點數(shù)(211+171+132)/4=16 搜索空間訪問的結(jié)點數(shù)為搜索空間訪問的結(jié)點數(shù)為17搜索空間搜索空間26影響算法效率的因素影響算法效率的因素最壞情況下的時間最壞情況下的時間W(n)=(p(n)f(n) 其中其中 p(n) 為每個結(jié)點時間，為每個結(jié)點時間，f(n)為結(jié)點個數(shù)為結(jié)點個數(shù) 影響回朔算法效率的因素影響回朔算法效率的因素 （1）搜索樹的結(jié)構(gòu)）搜索樹的結(jié)構(gòu) 分支情況：分支均勻否、分支情況：分支均勻否、 樹的深度：樹的深度： 對稱程度：對稱適合裁減對稱程度：對稱適合裁減 （

24、2）解的分布）解的分布 在不同子樹中分布多少是否均勻在不同子樹中分布多少是否均勻 分布深度分布深度 （3）約束條件的判斷：計算簡單）約束條件的判斷：計算簡單27（1）根據(jù)樹分支設(shè)計優(yōu)先策略：）根據(jù)樹分支設(shè)計優(yōu)先策略： 結(jié)點少的分支優(yōu)先，解多的分支優(yōu)先結(jié)點少的分支優(yōu)先，解多的分支優(yōu)先（2）利用搜索樹的對稱性剪裁子樹）利用搜索樹的對稱性剪裁子樹（3）分解為子問題）分解為子問題: 求解時間求解時間 f(n)=c2n，組合時間，組合時間T=O(f(n) 如果分解為如果分解為 k 個子問題，每個子問題大小為個子問題，每個子問題大小為 n/k 求解時間為求解時間為 Tkckn 2改進途徑改進途徑分支限界法

25、（分支分支限界法（分支+限界）限界）常以廣度優(yōu)先或以最小耗費（最常以廣度優(yōu)先或以最小耗費（最大效益）優(yōu)先的方式搜索問題的解空間樹。大效益）優(yōu)先的方式搜索問題的解空間樹。分支：分支：按廣度優(yōu)先的策略進行搜索按廣度優(yōu)先的策略進行搜索限界：限界：為加快搜索速度而采用啟發(fā)式信息剪枝的策略為加快搜索速度而采用啟發(fā)式信息剪枝的策略組合優(yōu)化問題的相關(guān)概念組合優(yōu)化問題的相關(guān)概念目標(biāo)函數(shù)目標(biāo)函數(shù)（極大化或極小化）（極大化或極小化）約束條件約束條件搜索空間中滿足約束條件的解稱為搜索空間中滿足約束條件的解稱為可行解可行解使得目標(biāo)函數(shù)達到極大使得目標(biāo)函數(shù)達到極大(或極小或極小)的解稱為的解稱為最優(yōu)解最優(yōu)解285.4

26、分支限界分支限界29分支限界技術(shù)（極大化）分支限界技術(shù)（極大化）設(shè)立設(shè)立代價函數(shù)代價函數(shù)函數(shù)值以該結(jié)點為根的搜索樹中的所有可行解的目標(biāo)函函數(shù)值以該結(jié)點為根的搜索樹中的所有可行解的目標(biāo)函數(shù)值的上界數(shù)值的上界父結(jié)點的代價不小于子結(jié)點的代價父結(jié)點的代價不小于子結(jié)點的代價設(shè)立設(shè)立界界代表當(dāng)時已經(jīng)得到的可行解的目標(biāo)函數(shù)的最大值代表當(dāng)時已經(jīng)得到的可行解的目標(biāo)函數(shù)的最大值界的設(shè)定初值可以設(shè)為界的設(shè)定初值可以設(shè)為0可行解的目標(biāo)函數(shù)值大于當(dāng)時的界，進行更新可行解的目標(biāo)函數(shù)值大于當(dāng)時的界，進行更新搜索中停止分支的依據(jù)搜索中停止分支的依據(jù)不滿足約束條件或者其代價函數(shù)小于當(dāng)時的界不滿足約束條件或者其代價函數(shù)小于當(dāng)時的

27、界 30實例：布線問題實例：布線問題NoImage印刷電路板將布線區(qū)域劃分成印刷電路板將布線區(qū)域劃分成n X m個方格如圖所個方格如圖所示。精確的電路布線問題要求確定連接方格示。精確的電路布線問題要求確定連接方格a的中的中點到方格點到方格b的中點的最短布線方案。在布線時，電的中點的最短布線方案。在布線時，電路只能沿直線或直角布線。為了避免線路相交，已路只能沿直線或直角布線。為了避免線路相交，已布了線的方格做了封鎖標(biāo)記，其它線路不允穿過被布了線的方格做了封鎖標(biāo)記，其它線路不允穿過被封鎖的方格。封鎖的方格。31背包問題的實例：背包問題的實例： 11 iiiiwvwv對變元重新排序使得對變元重新排序

28、使得4 , 3 , 2 , 1, N102347359max43214321 ixxxxxxxxxi否否則則有有若若對對某某個個 kiiijkiiikikkiikiiixvwxwbkjwvxwbxv111111)(實例：背包問題實例：背包問題排序后實例排序后實例 32結(jié)點結(jié)點 的代價函數(shù)的代價函數(shù) 4 , 3 , 2 , 1, N, 102347359max43214321 ixxxxxxxxxi 分支策略分支策略-深度優(yōu)先深度優(yōu)先 代價函數(shù)與分支策略確定代價函數(shù)與分支策略確定Biiik1 jjjjkll dL33UrUrji1 k1 i1 iiij2 / )rr r r c 2 ( lb行最

29、小的兩個元素素行不在路徑上的最小元x2=283/3210 0wv73/ 339 07/910 x1=174 / 539 x2=215 111x2=316213072 / 139 11012x1=004/510 143/ 365 003/ 310 實實例例345.4.2 最大團問題最大團問題例例5.9 最大團問題：給定無向圖最大團問題：給定無向圖G=, 求求G中的最大團中的最大團. 相關(guān)知識：相關(guān)知識： 無向無向圖圖G = , G的的子圖子圖：G= , 其中其中V V, E E, G的的補圖補圖： =, E是是E關(guān)于完全圖邊集的補集關(guān)于完全圖邊集的補集 G中的中的團團：G 的完全子圖的完全子圖

30、G 的的點獨立集點獨立集：G 的頂點子集的頂點子集A，且，且 u,v A, u,v E. 最大團最大團：頂點數(shù)最多的團：頂點數(shù)最多的團 最大點獨立集最大點獨立集：頂點數(shù)最多的點獨立集：頂點數(shù)最多的點獨立集命題：命題：U是是G 的最大團當(dāng)且僅當(dāng)?shù)淖畲髨F當(dāng)且僅當(dāng)U是是 的最大點獨立集的最大點獨立集 35結(jié)點結(jié)點的含義：的含義： 已檢索已檢索 k 個頂點，其中個頂點，其中 xi=1 對應(yīng)的頂點在當(dāng)前的團內(nèi)對應(yīng)的頂點在當(dāng)前的團內(nèi)搜索樹為子集樹搜索樹為子集樹約束條件：該頂點與當(dāng)前團內(nèi)每個頂點都有邊相連約束條件：該頂點與當(dāng)前團內(nèi)每個頂點都有邊相連界：當(dāng)前圖中已檢索到的極大團的頂點數(shù)界：當(dāng)前圖中已檢索到的極

31、大團的頂點數(shù)代價函數(shù)：目前的團擴張為極大團的頂點數(shù)上界代價函數(shù)：目前的團擴張為極大團的頂點數(shù)上界 F = Cn+n k 其中其中 Cn 為目前團的頂點數(shù)（初始為為目前團的頂點數(shù)（初始為0），）， k 為結(jié)點層數(shù)為結(jié)點層數(shù)時間：時間：O(n2n)算法設(shè)計算法設(shè)計3623514頂點編號順序為頂點編號順序為 1, 2, 3, 4, 5,對應(yīng)對應(yīng) x1, x2, x3, x4, x5, xi=1 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) i 在團內(nèi)在團內(nèi) 分支規(guī)定左子樹為分支規(guī)定左子樹為1，右子樹為，右子樹為0. B 為界，為界，F(xiàn) 為代價函數(shù)值為代價函數(shù)值.最大團的實例最大團的實例37a：得第一個極大團：得第一個極大團 1

32、, 2, 4 , 頂點數(shù)為頂點數(shù)為3, 界為界為3；b：代價函數(shù)值：代價函數(shù)值 F = 3, 回溯；回溯；c：得第二個極大團：得第二個極大團1, 3, 4, 5, 頂點數(shù)為頂點數(shù)為4, 修改界為修改界為4；d：不必搜索其它分支：不必搜索其它分支, 因為因為F = 4, 不超過界；不超過界；e：F = 4, 不必搜索不必搜索.最大團為最大團為 1, 3, 4, 5, 頂點數(shù)為頂點數(shù)為 4. 23514實例求解實例求解a,B=3 b,F=3c,B=4d,F=4e,F=4TSP問題問題 TSPTSP問題是指旅行家要旅行問題是指旅行家要旅行n n個城市，要求各個城個城市，要求各個城市經(jīng)歷且僅經(jīng)歷一次然

33、后回到出發(fā)城市，并要求所走市經(jīng)歷且僅經(jīng)歷一次然后回到出發(fā)城市，并要求所走的路程最短。的路程最短。271563134253984C= 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 (a) 一個無向圖一個無向圖 (b) 無向圖的代價矩陣無向圖的代價矩陣圖圖9.4 無向圖及其代價矩陣無向圖及其代價矩陣 采用貪心法求得近似解為采用貪心法求得近似解為135421，其路徑，其路徑長度為長度為1+2+3+7+3=16，這可以作為，這可以作為TSP問題的上界。問題的上界。 把矩陣中每一行最小的元素相加，可以得到一個簡單的把矩陣中每一行最小的元素相加，可以得到一個簡單的下界，其

34、路徑長度為下界，其路徑長度為1+3+1+3+2=10，但是還有一個信息量，但是還有一個信息量更大的下界：考慮一個更大的下界：考慮一個TSP問題的完整解，在每條路徑上，問題的完整解，在每條路徑上，每個城市都有兩條鄰接邊，一條是進入這個城市的，另一每個城市都有兩條鄰接邊，一條是進入這個城市的，另一條是離開這個城市的，那么，如果把矩陣中每一行最小的條是離開這個城市的，那么，如果把矩陣中每一行最小的兩個元素相加再除以兩個元素相加再除以2，如果圖中所有的代價都是整數(shù)，再，如果圖中所有的代價都是整數(shù)，再對這個結(jié)果向上取整，就得到了一個合理的下界。對這個結(jié)果向上取整，就得到了一個合理的下界。 lb=(1+3

35、)+(3+6)+(1+2)+(3+4)+(2+3)/2=14 于是，得到了目標(biāo)函數(shù)的界于是，得到了目標(biāo)函數(shù)的界14, 16。需要強調(diào)的是，這個解并不是一個合法的選擇（可能沒有需要強調(diào)的是，這個解并不是一個合法的選擇（可能沒有構(gòu)成哈密頓回路），它僅僅給出了一個參考下界。構(gòu)成哈密頓回路），它僅僅給出了一個參考下界。 部分解的目標(biāo)函數(shù)值的計算方法部分解的目標(biāo)函數(shù)值的計算方法 例如圖例如圖9.4所示無向圖，如果部分解包含邊所示無向圖，如果部分解包含邊(1, 4)，則該部分，則該部分解的下界是解的下界是lb=(1+5)+(3+6)+(1+2)+(3+5)+(2+3)/2=16。 112111212.22

36、.rrrrrrrrxrrdddxLnnnkkkkknnkkkk 271563134253984C= 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 (a) 一個無向圖一個無向圖 (b) 無向圖的代價矩陣無向圖的代價矩陣圖圖9.4 無向圖及其代價矩陣無向圖及其代價矩陣412lb=142356781startlb=1413lb=1414lb=1615lb=1923lb=1624lb=1625lb=1932lb=1634lb=1535lb=149101152lb=1954lb=14141542lb=161742lb=1845lb=15121352lb=2016分支限界

37、法求解分支限界法求解TSP問題示例問題示例425.4.3 貨郎問題貨郎問題例例5.10 貨郎問題：給定貨郎問題：給定n個城市集合個城市集合C=c1,c2,cn, 從一個城從一個城市到另一個城市的距離市到另一個城市的距離 dij 為正整數(shù)，求一條最短且每個城為正整數(shù)，求一條最短且每個城市恰好經(jīng)過一次的巡回路線市恰好經(jīng)過一次的巡回路線. 貨郎問題的類型：有向圖、無向圖貨郎問題的類型：有向圖、無向圖. 設(shè)巡回路線從設(shè)巡回路線從1開始，開始，解向量為解向量為, 其中其中 i1, i2, , in-1為為 2, 3, , n 的排列的排列. 搜索空間為排列樹，結(jié)點搜索空間為排列樹，結(jié)點 表示得到表示得到

38、 k 步路線步路線1234524971343為部分巡回路線擴張成全程巡回路線的長度下界為部分巡回路線擴張成全程巡回路線的長度下界時間時間 O(n!)：計算：計算O(n 1)!)次，代價函數(shù)計算次，代價函數(shù)計算O(n)約束條件約束條件：令：令B = i0=1, i1, i2, , ik , 則則 ik+1 2, , n B界界：當(dāng)前得到的最短巡回路線長度：當(dāng)前得到的最短巡回路線長度代價函數(shù)代價函數(shù)L：設(shè)頂點：設(shè)頂點 ci 出發(fā)的最短邊長度為出發(fā)的最短邊長度為 li，dj 為選為選定巡回路線中第定巡回路線中第 j 段的長度，則段的長度，則算法設(shè)計算法設(shè)計445.4.4 圓排列問題圓排列問題例例5.

39、11 圓排列問題：給定圓排列問題：給定n個圓的半徑序列個圓的半徑序列, 將各圓與將各圓與矩形底邊相切排列矩形底邊相切排列, 求具有最小長度求具有最小長度 ln 的圓的排列順序的圓的排列順序.解為解為為為1, 2, , n的的排列，解空間為排列樹排列，解空間為排列樹. 部分解向量部分解向量 ：表示：表示前前 k 個圓已排好個圓已排好. 令令B= i1, i2, , ik ,下一個圓選擇下一個圓選擇ik+1. 約束條件：約束條件：ik+1 1, 2, , n B界：當(dāng)前得到的最小園排列長度界：當(dāng)前得到的最小園排列長度45 k：算法完成第：算法完成第 k 步，已經(jīng)選擇了第步，已經(jīng)選擇了第1 k 個圓個圓 rk：第：第 k 個圓的半徑個圓的半徑 dk：第：第 k 1 個圓到第個圓到第 k 個圓的圓心水平距離，個圓的圓心水平距離，k1 xk：第：第 k 個圓的圓心坐標(biāo)，規(guī)定個圓的圓心坐標(biāo)，規(guī)定 x1=0, lk： 第第 1 k 個圓的排列長度個圓的排列長度 Lk：放好：放好 1k 個圓以后，對應(yīng)結(jié)點的代價函數(shù)值個圓以后，對應(yīng)結(jié)點的代價函數(shù)值 Lk ln代價函數(shù)符號說明代價函數(shù)符號說明461112121,2)()(rrxldxxrrrrrrd