【正文】 計算機算法設(shè)計與分析 Design and Analysis of Computer Algorithms 第六章 分支限界法 BranchandBound Algorithm 2021年 11月 12日 2 ?理解分支限界法的剪枝搜索策略。 ?掌握分支限界法的算法框架 1. 隊列式 (FIFO)分支限界法 2. 優(yōu)先隊列式分支限界法 ?通過應(yīng)用范例學(xué)習(xí)分支限界法的設(shè)計策略。 1. 單源最短路徑問題 2. 裝載問題； 3. 布線問題 4. 01背包問題； 5. 最大團問題； 6. 旅行售貨員問題 7. 電路板排列問題 8. 批處理作業(yè)調(diào)度問題 學(xué)習(xí)要點 2021年 11月 12日 3 提綱 一、分支限界法的基本思想 二、單源最短路徑問題 三、裝載問題 四、 01背包問題 五、最大團問題 六、旅行售貨員問題 2021年 11月 12日 4 提綱 一、分支限界法的基本思想 二、單源最短路徑問題 三、裝載問題 四、 01背包問題 五、最大團問題 六、旅行售貨員問題 2021年 11月 12日 5 分支限界法同回溯法類似，它也是在解空間中搜索問題的可行解或最優(yōu)解，但搜索的方式不同?；厮莘ú捎蒙疃葍?yōu)先的方式，朝縱深方向搜索，直至達到問題的一個可行解，或經(jīng)判斷沿此路徑不會達到問題的可行解或最優(yōu)解時，停止向前搜索，并沿原路返回到該路徑上最后一個還可擴展的結(jié)點。從該結(jié)點出發(fā)朝新的方向縱深搜索。分支定界法則采用寬度優(yōu)先的方式搜索解空間樹，它將活結(jié)點存放在一個特殊的表中。其策略是：在擴展結(jié)點處，先生成其所有的兒子結(jié)點 ,將那些導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子舍棄，其余兒子加入活結(jié)點表中。此后，從活結(jié)點表中取出一個結(jié)點作為當(dāng)前擴展結(jié)點。并重復(fù)上述結(jié)點擴展過程。所以，分支限界法與回溯法的本質(zhì)區(qū)別在于搜索方式的不同?；厮莘ǜm于處理那些求所有可行解的問題，而分支限界法更適于處理那些只確定一個可行解，特別是最優(yōu)化問題。 2021年 11月 12日 6 分支限界法與回溯法的比較 ?分支限界法類似于回溯法，也是一種在問題的解空間樹 T中搜索問題解的算法。 ?分支限界法與回溯法的求解目標(biāo)（適用范圍）不同： ?回溯法適用于找出滿足約束條件的所有解的情況； ?分支限界法發(fā)誓找出滿足條件的一個解，或某種意義下的最優(yōu)解。 ?搜索方式不同 ?回溯法：深度優(yōu)先 ?分支限界法：廣度優(yōu)先 2021年 11月 12日 7 分支限界法的基本思想 ?分支限界法常以廣度優(yōu)先或以最小耗費（最大效益）優(yōu)先的方式搜索問題的解空間樹。 ?在分支限界法中，每一個活結(jié)點只有一次機會成為擴展結(jié)點?；罱Y(jié)點一旦成為擴展結(jié)點，就一次性產(chǎn)生其所有兒子結(jié)點。在這些兒子結(jié)點中， 導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點被舍棄 ，其余兒子結(jié)點被加入活結(jié)點表中。 ?此后，從活結(jié)點表中取下一結(jié)點成為當(dāng)前擴展結(jié)點，并重復(fù)上述結(jié)點擴展過程。這個過程一直持續(xù)到找到所需的解或活結(jié)點表為空時為止 。 2021年 11月 12日 8 常見的兩種分支限界法 ?從活結(jié)點表中選擇下一擴展結(jié)點的不同方式導(dǎo)致不同的分支限界法： ?隊列式 (FIFO)分支限界法：將活結(jié)點表組織成一個隊列，按照隊列先進先出（ FIFO） 原則選取下一個節(jié)點為擴展節(jié)點。 ?優(yōu)先隊列式分支限界法：將活結(jié)點表組織成一個優(yōu)先隊列，按照優(yōu)先隊列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的節(jié)點成為當(dāng)前擴展節(jié)點。 ?最大優(yōu)先隊列：使用最大堆，體現(xiàn)最大效益優(yōu)先 ?最小優(yōu)先隊列：使用最小堆，體現(xiàn)最小費用優(yōu)先 2021年 11月 12日 9 隊列式分支限界法的搜索解空間樹的方式類似于解空間樹的寬度優(yōu)先搜索，不同的是隊列式分支限界法不搜索以不可行結(jié)點（已經(jīng)被判定不能導(dǎo)致可行解或不能導(dǎo)致最優(yōu)解的結(jié)點）為根的子樹。這是因為，按照規(guī)則，這樣的結(jié)點未被列入活結(jié)點表。 2021年 11月 12日 10 優(yōu)先隊列式分支限界法的搜索方式是根據(jù)活結(jié)點的優(yōu)先級確定下一個擴展結(jié)點。結(jié)點的優(yōu)先級常用一個與該結(jié)點有關(guān)的數(shù)值 p 來表示。 最大優(yōu)先隊列規(guī)定 p 值較大的結(jié)點點的優(yōu)先級較高。在算法實現(xiàn)時通常用一個最大堆來實現(xiàn)最大優(yōu)先隊列，用最大堆的 Deletemax 運算抽取堆中的下一個結(jié)點作為當(dāng)前擴展結(jié)點，體現(xiàn)最大效益優(yōu)先的原則。 類似地，最小優(yōu)先隊列規(guī)定 p 值較小的結(jié)點的優(yōu)先級較高。在算法實現(xiàn)時，常用一個最小堆來實現(xiàn)，用最小堆的Deletemin 運算抽取堆中下一個結(jié)點作為當(dāng)前擴展結(jié)點，體現(xiàn)最小優(yōu)先的原則。 2021年 11月 12日 11 采用優(yōu)先隊列式分支定界算法解決具體問題時，應(yīng)根據(jù)問題的特點選用最大優(yōu)先或最小優(yōu)先隊列，確定各個結(jié)點的 p 值。 2021年 11月 12日 12 實例 01背包問題 n=3, c=30, w=[16,15,15], p=[45,25,25] 2021年 11月 12日 13 實例分析－ 01背包問題 n=3, c=30, w=[16,15,15], p=[45,25,25] ? 隊列式分支限界法： [A] B, C = B, C [B, C] D, E = E [C, E] F, G = F, G [E, F, G] J, K = K(45) [1,0,0] [F, G] L, M =L(50) [0, 1, 1] M(25) [G] N, 0 =N(25), O(0) 不搜索以不可行結(jié)點為根的子樹 ? 優(yōu)先隊列式分支限界法： [A] B, C = B(45), C(0) [B, C] D, E = E(45) [E, C] J, K = K(45) [1, 0, 0] [C] F, G = F(25), G(0) [F, G] L, M = L(50), [0, 1, 1] M(25) [G] N, O = N(25), O(0) ? 可用剪枝函數(shù)加速搜索 2021年 11月 12日 14 實例－ TSP問題 1 2 3 4 20 6 30 5 4 10 A B C D E F G H I J K L M N O P Q 1 2 3 4 3 4 4 3 4 2 3 2 2 4 2 3 問題描述：某售貨員要到若干城市去推銷商品，一直各城市之間的路程，他要選定一條從駐地出發(fā)，經(jīng)過每個城市一遍，最后回到住地的路線，使總的路程最短。 2021年 11月 12日 15 實例分析－ TSP問題 ? 隊列式分支限界法： [B] C, D, E [C, D, E] F, G [D, E, F, G] H, I [E, F, G, H, I] J, K [F, G, H, I, J, K] L(59) [1,2,3,4,1] [G, H, I, J, K] M(66) [H, I, J, K] N(25) [1, 3, 2, 4,1] [I, J, K] 134(26) [J, K] P(25) [K] Q(59) ? 優(yōu)先隊列式分支限界法： [B] C, D, E = C(30), D(6), E(4) [E, D, C] J, K = J(14), K(24) [D, J, K, C] H, I = H(11), I(26) [H, J, K, I, C] N = N(25) [1, 3, 2, 4,1] [J, K, I, C] P = P(25) [K, I, C] Q = Q(59) [I, C] I, C 被限界掉 1 2 3 4 20 6 30 5 4 10 A B C D E F G H I J K L M N O P Q 1 2 3 4 3 4 4 3 4 2 3 2 2 4 2 3 2021年 11月 12日 16 應(yīng)用分支限界法的關(guān)鍵 ? 如何確定合適的 限界函數(shù)？ ? 如何組織 活結(jié)點表？ ? 如何確定最優(yōu)解中的 各個分量？ 好的限界函數(shù)不僅計算簡單，還要保證最優(yōu)解在搜索空間中，更重要的是能在搜索的早期對超出目標(biāo)函數(shù)界的結(jié)點進行丟棄，減少搜索空間，從而盡快找到問題的最優(yōu)解。 通常采用最大堆或最小堆來實現(xiàn)優(yōu)先隊列式分支限界法求解問題。 可以用如下方法求