第6章_分支限界法

1、第第6章章 分支限界法分支限界法2022-5-21算法設(shè)計與分析2第第6章章 分支限界法分支限界法學(xué)習要點學(xué)習要點 理解分支限界法的理解分支限界法的剪枝搜索剪枝搜索策略策略 掌握分支限界法的算法框架掌握分支限界法的算法框架 隊列式（隊列式（FIFO）分支限界法）分支限界法 優(yōu)先隊列式分支限界法優(yōu)先隊列式分支限界法 通過應(yīng)用范例學(xué)習分支限界法的設(shè)計策略通過應(yīng)用范例學(xué)習分支限界法的設(shè)計策略 0-1背包問題背包問題2022-5-21算法設(shè)計與分析36.1 分支限界法的基本思想分支限界法的基本思想 分支限界法與回溯法的不同分支限界法與回溯法的不同求解目標求解目標： 回溯法回溯法的求解目標：的求解目標：

2、找出找出T（解空間狀態(tài)樹）（解空間狀態(tài)樹）中滿足約束條件的所有解；中滿足約束條件的所有解； 分支限界法分支限界法的求解目標：的求解目標：找出滿足約束條件找出滿足約束條件的一個解，或是在滿足約束條件的解中找出的一個解，或是在滿足約束條件的解中找出使用某一目標函數(shù)值達到極大或極小的解，使用某一目標函數(shù)值達到極大或極小的解，即在某種意義下的即在某種意義下的最優(yōu)解最優(yōu)解。 2022-5-21算法設(shè)計與分析4分支限界法與回溯法的不同搜索方式分支限界法與回溯法的不同搜索方式 回溯法以回溯法以深度優(yōu)先深度優(yōu)先的方式搜索解空間樹的方式搜索解空間樹T，而分支限界法，而分支限界法則以則以廣度優(yōu)先廣度優(yōu)先或以或以最

3、小耗費優(yōu)先最小耗費優(yōu)先的方式搜索解空間樹的方式搜索解空間樹T。 分支限界法的搜索策略：在擴展結(jié)點處，先生成其所有的分支限界法的搜索策略：在擴展結(jié)點處，先生成其所有的兒子結(jié)點（分支），然后再從當前的兒子結(jié)點（分支），然后再從當前的活結(jié)點表活結(jié)點表中選擇下一中選擇下一個擴展對點。為了有效地選擇下一擴展結(jié)點，以加速搜索個擴展對點。為了有效地選擇下一擴展結(jié)點，以加速搜索的進程，在每一活結(jié)點處，計算一個的進程，在每一活結(jié)點處，計算一個函數(shù)值（限界）函數(shù)值（限界），并，并根據(jù)這些已計算出的函數(shù)值，從當前活結(jié)點表中選擇一個根據(jù)這些已計算出的函數(shù)值，從當前活結(jié)點表中選擇一個最有利的最有利的結(jié)點作為擴展結(jié)點，使

4、搜索朝著解空間樹上有最結(jié)點作為擴展結(jié)點，使搜索朝著解空間樹上有最優(yōu)解的分支推進，以便盡快地找出一個優(yōu)解的分支推進，以便盡快地找出一個最優(yōu)解最優(yōu)解。2022-5-21算法設(shè)計與分析5分支限界法的基本思想分支限界法的基本思想 分支限界法通常以分支限界法通常以廣度優(yōu)先廣度優(yōu)先或以或以最小耗費（最最小耗費（最大效益）優(yōu)先大效益）優(yōu)先的方式搜索問題的解空間樹。的方式搜索問題的解空間樹。 問題的解空間樹是表示問題解空間的一棵有序問題的解空間樹是表示問題解空間的一棵有序樹，常見的有樹，常見的有子集樹子集樹和和排列樹排列樹。2022-5-21算法設(shè)計與分析6回顧回顧：兩種典型的解空間樹兩種典型的解空間樹 子集

5、樹（子集樹（Subset Trees）：）：當所給問題是從當所給問題是從n個元素的集合個元素的集合中找出滿足某種性質(zhì)的子集時，相應(yīng)的解空間樹稱為子集中找出滿足某種性質(zhì)的子集時，相應(yīng)的解空間樹稱為子集樹。在子集樹中，樹。在子集樹中，|S0|=|S1|=|Sn-1|=c，即每個結(jié)點有相同，即每個結(jié)點有相同數(shù)目的子樹，通常情況下數(shù)目的子樹，通常情況下c=2，所以，子集樹中共有，所以，子集樹中共有2n個葉個葉子結(jié)點，因此，遍歷子集樹需要子結(jié)點，因此，遍歷子集樹需要O(2n)時間。時間。 排列樹（排列樹（Permutation Trees）：）：當所給問題是確定當所給問題是確定n個元個元素滿足某種性質(zhì)的

6、排列時，相應(yīng)的解空間樹稱為排列樹。素滿足某種性質(zhì)的排列時，相應(yīng)的解空間樹稱為排列樹。在排列樹中，通常情況下，在排列樹中，通常情況下，|S0|=n，|S1|=n-1，|Sn-1|=1，所以，排列樹中共有所以，排列樹中共有n!個葉子結(jié)點，因此，遍歷排列樹需個葉子結(jié)點，因此，遍歷排列樹需要要O(n!)時間。時間。2022-5-21算法設(shè)計與分析7分支限界法的基本思想分支限界法的基本思想 每一個活結(jié)點每一個活結(jié)點只有一次機會只有一次機會成為擴展結(jié)點成為擴展結(jié)點 活結(jié)點一旦成為擴展結(jié)點，就一次性產(chǎn)生其所有兒子活結(jié)點一旦成為擴展結(jié)點，就一次性產(chǎn)生其所有兒子結(jié)點。在這些兒子結(jié)點中，那些導(dǎo)致不可行解或?qū)е陆Y(jié)點

7、。在這些兒子結(jié)點中，那些導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點被非最優(yōu)解的兒子結(jié)點被舍棄舍棄，其余兒子結(jié)點被，其余兒子結(jié)點被加入加入活活結(jié)點表結(jié)點表中中 從活結(jié)點表中取下一結(jié)點成為當前擴展結(jié)點，并重復(fù)從活結(jié)點表中取下一結(jié)點成為當前擴展結(jié)點，并重復(fù)上述結(jié)點擴展過程上述結(jié)點擴展過程 這個過程一直持續(xù)到這個過程一直持續(xù)到找到所求的解或活結(jié)點表為空找到所求的解或活結(jié)點表為空時時為止。為止?；罱Y(jié)點表：具有先進先出的性質(zhì)，是隊列?；罱Y(jié)點表：具有先進先出的性質(zhì)，是隊列。2022-5-21算法設(shè)計與分析8分支限界法的適用范圍分支限界法的適用范圍 分支限界法類似于回溯法，有一些問題其實無論用回溯分支限界法類似于回

8、溯法，有一些問題其實無論用回溯法還是分支限界法都可以得到很好的解決，但是另外一法還是分支限界法都可以得到很好的解決，但是另外一些則不然。些則不然。 下表列出了回溯法和分支限界法的一些區(qū)別：下表列出了回溯法和分支限界法的一些區(qū)別：方法方法對解空間樹的搜對解空間樹的搜索方式索方式存儲結(jié)點的常存儲結(jié)點的常用數(shù)據(jù)結(jié)構(gòu)用數(shù)據(jù)結(jié)構(gòu)結(jié)點存儲特性結(jié)點存儲特性常用應(yīng)用常用應(yīng)用回溯法回溯法深度優(yōu)先搜索深度優(yōu)先搜索棧棧活結(jié)點的所有活結(jié)點的所有可行子結(jié)點被可行子結(jié)點被遍歷后才被從遍歷后才被從棧中彈出棧中彈出找出滿足約束找出滿足約束條件的所有解條件的所有解分支限界分支限界法法廣度優(yōu)先或最小廣度優(yōu)先或最小消耗優(yōu)先搜索消耗

9、優(yōu)先搜索隊列、優(yōu)先隊隊列、優(yōu)先隊列列每個結(jié)點只有每個結(jié)點只有一一次成為擴展次成為擴展結(jié)點結(jié)點的機會的機會找出滿足約束找出滿足約束條件的一個解條件的一個解或特定意義下或特定意義下的最優(yōu)解的最優(yōu)解2022-5-21算法設(shè)計與分析9A、適合采用回溯法解決的問題、適合采用回溯法解決的問題 n后問題后問題 問題定義：問題定義：在在nn的國際象棋棋盤上擺下的國際象棋棋盤上擺下n個皇后，使所個皇后，使所有的皇后都不能攻擊到對方，找出所有符合要求的情況。有的皇后都不能攻擊到對方，找出所有符合要求的情況。 分析：分析： n后問題的解空間樹是一棵后問題的解空間樹是一棵排列樹排列樹，解與解之間不存在，解與解之間不存

10、在優(yōu)劣的分別。直到搜索到葉結(jié)點時才能確定出一組解。優(yōu)劣的分別。直到搜索到葉結(jié)點時才能確定出一組解。 采用回溯法可以系統(tǒng)地搜索問題的全部解。采用回溯法可以系統(tǒng)地搜索問題的全部解。 考慮使用分支限界法？考慮使用分支限界法？2022-5-21算法設(shè)計與分析10B、既可以采用回溯法也可以采用分支限、既可以采用回溯法也可以采用分支限界法解決的問題界法解決的問題 0-1背包問題背包問題 問題定義：問題定義：給定若干物品的重量和價值，以及給定若干物品的重量和價值，以及一個背包的容量上限。求出一種方案使得背包一個背包的容量上限。求出一種方案使得背包中存放物品的價值最高。中存放物品的價值最高。 分析：分析：0-

11、1背包問題的解空間樹是一棵子集樹，背包問題的解空間樹是一棵子集樹，所要求的解具有所要求的解具有最優(yōu)性質(zhì)最優(yōu)性質(zhì)。2022-5-21算法設(shè)計與分析11采用采用回溯法回溯法解決解決0-1背包問題的搜索策略背包問題的搜索策略 只要一個結(jié)點的左孩子結(jié)點是一個可行結(jié)點就搜索其只要一個結(jié)點的左孩子結(jié)點是一個可行結(jié)點就搜索其左子左子樹樹； 而對于而對于右子樹右子樹，需要用，需要用貪心算法貪心算法構(gòu)造一個構(gòu)造一個上界函數(shù)上界函數(shù)，只在，只在這個上界函數(shù)的值超過當前最優(yōu)解時才進入搜索。這個上界函數(shù)的值超過當前最優(yōu)解時才進入搜索。 隨著搜索進程的推進，最優(yōu)解不斷得到加強，對搜索的限隨著搜索進程的推進，最優(yōu)解不斷得

12、到加強，對搜索的限制就越來越嚴格。制就越來越嚴格。ABCDEFGHIJKLMNO111001001100102022-5-21算法設(shè)計與分析12分支限界法兩種方式分支限界法兩種方式 從活結(jié)點表中選擇下一擴展結(jié)點的不同方式導(dǎo)致不同的從活結(jié)點表中選擇下一擴展結(jié)點的不同方式導(dǎo)致不同的分支限界法。分支限界法。 最常見的有以下兩種方式：最常見的有以下兩種方式： 隊列式（隊列式（FIFO）分支限界法：）分支限界法：隊列式分支限界法將隊列式分支限界法將活結(jié)點表組織成一個隊列，并按隊列的活結(jié)點表組織成一個隊列，并按隊列的先進先出原先進先出原則則選取下一個結(jié)點為當前擴展結(jié)點。選取下一個結(jié)點為當前擴展結(jié)點。 優(yōu)先

13、隊列式分支限界法：優(yōu)先隊列式分支限界法：優(yōu)先隊列式分支限界法將優(yōu)先隊列式分支限界法將活結(jié)點表組織成一個活結(jié)點表組織成一個優(yōu)先隊列優(yōu)先隊列，按優(yōu)先隊列中規(guī)定，按優(yōu)先隊列中規(guī)定的結(jié)點優(yōu)先級選取優(yōu)先級最高的下一個結(jié)點成為當?shù)慕Y(jié)點優(yōu)先級選取優(yōu)先級最高的下一個結(jié)點成為當前擴展結(jié)點。前擴展結(jié)點。2022-5-21算法設(shè)計與分析13舉例舉例：0-1背包問題背包問題 n=3時時0-1背包問題的一個實例：背包問題的一個實例：w=16, 15, 15，p=45, 25, 25，c=30，其解空間是子集樹。，其解空間是子集樹。ABCDEFGHIJKLMNO111001001100102022-5-21算法設(shè)計與分析

14、14 用用隊列式分支限界法隊列式分支限界法解此問題時，用一個解此問題時，用一個隊列隊列來存儲活結(jié)點來存儲活結(jié)點表。表。 算法從根結(jié)點算法從根結(jié)點A開始。初始時活結(jié)點隊列為空，結(jié)點開始。初始時活結(jié)點隊列為空，結(jié)點A是當是當前擴展結(jié)點。結(jié)點前擴展結(jié)點。結(jié)點A的的2個兒子結(jié)點個兒子結(jié)點B和和C均為可行結(jié)點，所均為可行結(jié)點，所以將這以將這2個兒子結(jié)點按個兒子結(jié)點按從左到右從左到右的順序加入活結(jié)點隊列，并的順序加入活結(jié)點隊列，并且且舍棄舍棄當前擴展結(jié)點當前擴展結(jié)點A。ABCDEFGHIJKLMNO11100100110010活結(jié)點隊列：活結(jié)點隊列：ABC2022-5-21算法設(shè)計與分析15 依依先進先出

15、先進先出原則，下一個擴展結(jié)點是活結(jié)點隊列的隊首結(jié)點原則，下一個擴展結(jié)點是活結(jié)點隊列的隊首結(jié)點B。擴展結(jié)點。擴展結(jié)點B得到其兒子結(jié)點得到其兒子結(jié)點D和和E。 由于由于D是是不可行結(jié)點不可行結(jié)點，被舍去。，被舍去。 E是可行結(jié)點，被加入活結(jié)點隊列。是可行結(jié)點，被加入活結(jié)點隊列。ABCDEFGHIJKLMNO11100100110010w=16, 15, 15，p=45, 25, 25，c=30活結(jié)點隊列：活結(jié)點隊列：BCE2022-5-21算法設(shè)計與分析16 接下來，接下來，C成為當前擴展結(jié)點，它的成為當前擴展結(jié)點，它的2個兒子結(jié)點個兒子結(jié)點F和和G均為均為可行結(jié)點，因此被加入到活結(jié)點隊列中?？尚?/p>

16、結(jié)點，因此被加入到活結(jié)點隊列中。 擴展下一個結(jié)點擴展下一個結(jié)點E得到結(jié)點得到結(jié)點J和和K。J是不可行結(jié)點，被舍去。是不可行結(jié)點，被舍去。K是一個可行的葉結(jié)點，表示所求問題的一個是一個可行的葉結(jié)點，表示所求問題的一個可行解可行解，其價，其價值為值為45。ABCDEFGHIJKLMNO11100100110010w=16, 15, 15，p=45, 25, 25，c=30活結(jié)點隊列：活結(jié)點隊列：FEG活結(jié)點隊列：活結(jié)點隊列：FG2022-5-21算法設(shè)計與分析17當前活結(jié)點隊列的隊首結(jié)點當前活結(jié)點隊列的隊首結(jié)點F成為下一個擴展結(jié)點。它的成為下一個擴展結(jié)點。它的2個兒子結(jié)點個兒子結(jié)點L和和M均為葉結(jié)

17、點。均為葉結(jié)點。L表示獲得價值為表示獲得價值為50的可行解；的可行解；M表示獲得價值為表示獲得價值為25的可行解。的可行解。G是最后的一個擴展結(jié)點，其兒子結(jié)點是最后的一個擴展結(jié)點，其兒子結(jié)點N和和O均為可行葉結(jié)點。最后，均為可行葉結(jié)點。最后，活結(jié)點隊列已空，算法終止活結(jié)點隊列已空，算法終止。算法搜索得到最優(yōu)值為算法搜索得到最優(yōu)值為50。ABCDEFGHIJKLMNO11100100110010w=16, 15, 15，p=45, 25, 25，c=302022-5-21算法設(shè)計與分析18 優(yōu)先隊列式分支限界法優(yōu)先隊列式分支限界法也是從根結(jié)點也是從根結(jié)點A開始搜索解空間開始搜索解空間樹的。樹的。

18、 用一個用一個極大堆極大堆來表示活結(jié)點表的優(yōu)先隊列，該優(yōu)先隊列來表示活結(jié)點表的優(yōu)先隊列，該優(yōu)先隊列的優(yōu)先級定義為的優(yōu)先級定義為活結(jié)點所擁有的活結(jié)點所擁有的價值價值。ABCDEFGHIJKLMNO11100100110010w=16, 15, 15，p=45, 25, 25，c=302022-5-21算法設(shè)計與分析19 初始時堆為空，擴展結(jié)點初始時堆為空，擴展結(jié)點A得到它的得到它的2個兒子結(jié)點個兒子結(jié)點B和和C。 這這2個結(jié)點均為個結(jié)點均為可行結(jié)點可行結(jié)點，因此被加入到堆中，結(jié)點，因此被加入到堆中，結(jié)點A被被舍棄。結(jié)點舍棄。結(jié)點B獲得的當前價值是獲得的當前價值是45，而結(jié)點，而結(jié)點C的當前價值的

19、當前價值為為0。ABCDEFGHIJKLMNO11100100110010w=16, 15, 15，p=45, 25, 25，c=302022-5-21算法設(shè)計與分析20 由于結(jié)點由于結(jié)點B的價值大于結(jié)點的價值大于結(jié)點C的價值，所以結(jié)點的價值，所以結(jié)點B是堆中最是堆中最大元素，從而成為下一個擴展結(jié)點。大元素，從而成為下一個擴展結(jié)點。 擴展結(jié)點擴展結(jié)點B得到結(jié)點得到結(jié)點D和和E。D不是可行結(jié)點，被舍去。不是可行結(jié)點，被舍去。E是是可行結(jié)點被加入到堆中。可行結(jié)點被加入到堆中。E的價值為的價值為45，成為當前堆中最大，成為當前堆中最大元素，從而成為下一個擴展結(jié)點。元素，從而成為下一個擴展結(jié)點。ABC

20、DEFGHIJKLMNO11100100110010w=16, 15, 15，p=45, 25, 25，c=302022-5-21算法設(shè)計與分析21 擴展結(jié)點擴展結(jié)點E得到得到2個葉結(jié)點個葉結(jié)點J和和K。J是不可行結(jié)點，被舍是不可行結(jié)點，被舍棄。棄。K是一個可行葉結(jié)點，表示所求問題的一個可行解，是一個可行葉結(jié)點，表示所求問題的一個可行解，其價值為其價值為45。 此時，堆中僅剩下一個活結(jié)點此時，堆中僅剩下一個活結(jié)點C。ABCDEFGHIJKLMNO11100100110010w=16, 15, 15，p=45, 25, 25，c=302022-5-21算法設(shè)計與分析22 此時，堆中僅剩下一個活結(jié)

21、點此時，堆中僅剩下一個活結(jié)點C，它成為當前擴展結(jié)點。，它成為當前擴展結(jié)點。它的它的2個兒子結(jié)點個兒子結(jié)點F和和G均為可行結(jié)點，因此被插入到當前均為可行結(jié)點，因此被插入到當前堆中。堆中。 結(jié)點結(jié)點F的價值為的價值為25，是堆中最大元素，成為下一個擴展結(jié)點。，是堆中最大元素，成為下一個擴展結(jié)點。ABCDEFGHIJKLMNO11100100110010w=16, 15, 15，p=45, 25, 25，c=302022-5-21算法設(shè)計與分析23 結(jié)點結(jié)點F的的2個兒子結(jié)點個兒子結(jié)點L和和M均為葉結(jié)點。葉結(jié)點均為葉結(jié)點。葉結(jié)點L相應(yīng)相應(yīng)于價值為于價值為50的可行解。的可行解。 葉結(jié)點葉結(jié)點M相應(yīng)于

22、價值為相應(yīng)于價值為25的可行解。葉結(jié)點的可行解。葉結(jié)點L所相應(yīng)的所相應(yīng)的解成為解成為當前最優(yōu)解當前最優(yōu)解。ABCDEFGHIJKLMNO11100100110010w=16, 15, 15，p=45, 25, 25，c=302022-5-21算法設(shè)計與分析24 最后，結(jié)點最后，結(jié)點G成為擴展結(jié)點，其兒子結(jié)點成為擴展結(jié)點，其兒子結(jié)點N和和O均為葉結(jié)均為葉結(jié)點，它們的價值分別為點，它們的價值分別為25和和0。 接下來，接下來，存儲活結(jié)點的堆已空，算法存儲活結(jié)點的堆已空，算法終止終止。算法搜索得到。算法搜索得到最優(yōu)值為最優(yōu)值為50。相應(yīng)的最優(yōu)解是從根結(jié)點。相應(yīng)的最優(yōu)解是從根結(jié)點A到結(jié)點到結(jié)點L的路徑

23、的路徑(0,1,1)。ABCDEFGHIJKLMNO11100100110010w=16, 15, 15，p=45, 25, 25，c=302022-5-21算法設(shè)計與分析25分析分析 當要尋求問題的一個最優(yōu)解時，與回溯法時類似地可以當要尋求問題的一個最優(yōu)解時，與回溯法時類似地可以用用剪枝函數(shù)剪枝函數(shù)來加速搜索。該函數(shù)給出每一個可行結(jié)點相來加速搜索。該函數(shù)給出每一個可行結(jié)點相應(yīng)的子樹可能獲得的應(yīng)的子樹可能獲得的最大價值的最大價值的上界上界。 如果這個上界不會比當前最優(yōu)值更大，則說明相應(yīng)的子如果這個上界不會比當前最優(yōu)值更大，則說明相應(yīng)的子樹中不含問題的最優(yōu)解，因而可以剪去。樹中不含問題的最優(yōu)解，

24、因而可以剪去。 另一方面，也可以將上界函數(shù)確定的每個結(jié)點的上界值另一方面，也可以將上界函數(shù)確定的每個結(jié)點的上界值作為優(yōu)先級，作為優(yōu)先級，以該優(yōu)先級的以該優(yōu)先級的非增序非增序抽取當前擴展結(jié)點抽取當前擴展結(jié)點。這種策略有時可以更迅速地找到最優(yōu)解。這種策略有時可以更迅速地找到最優(yōu)解。2022-5-21算法設(shè)計與分析26解空間樹的動態(tài)搜索過程解空間樹的動態(tài)搜索過程（最小消耗優(yōu)先）（最小消耗優(yōu)先） 分支限界法首先確定一個合理的分支限界法首先確定一個合理的限界函數(shù)限界函數(shù)，并根據(jù)限界函，并根據(jù)限界函數(shù)確定數(shù)確定目標函數(shù)的界目標函數(shù)的界down, up。 然后，按照廣度優(yōu)先策略遍歷問題的解空間樹，在分支結(jié)然

25、后，按照廣度優(yōu)先策略遍歷問題的解空間樹，在分支結(jié)點上，依次搜索該結(jié)點的所有孩子結(jié)點，分別估算這些孩點上，依次搜索該結(jié)點的所有孩子結(jié)點，分別估算這些孩子結(jié)點的目標函數(shù)的可能取值，如果子結(jié)點的目標函數(shù)的可能取值，如果某孩子結(jié)點的目標函某孩子結(jié)點的目標函數(shù)可能取得的值超出目標函數(shù)的界，則將其數(shù)可能取得的值超出目標函數(shù)的界，則將其丟棄丟棄，因為從，因為從這個結(jié)點生成的解不會比目前已經(jīng)得到的解更好；否則，這個結(jié)點生成的解不會比目前已經(jīng)得到的解更好；否則，將其加入將其加入待處理結(jié)點表待處理結(jié)點表（表表PT）中。）中。 依次從表依次從表PT中選取使目標函數(shù)的值取得中選取使目標函數(shù)的值取得極值極值的結(jié)點成為的

26、結(jié)點成為當前擴展結(jié)點，重復(fù)上述過程，直到找到最優(yōu)解。當前擴展結(jié)點，重復(fù)上述過程，直到找到最優(yōu)解。2022-5-21算法設(shè)計與分析27 隨著這個遍歷過程的不斷深入，表隨著這個遍歷過程的不斷深入，表PT中所估算的目標函中所估算的目標函數(shù)的界越來越接近問題的最優(yōu)解。數(shù)的界越來越接近問題的最優(yōu)解。 當搜索到一個當搜索到一個葉結(jié)點葉結(jié)點時：時： 如果該結(jié)點的目標函數(shù)值是表如果該結(jié)點的目標函數(shù)值是表PT中的中的極值極值，則該葉則該葉子結(jié)點對應(yīng)的解就是問題的最優(yōu)解。子結(jié)點對應(yīng)的解就是問題的最優(yōu)解。 否則，根據(jù)這個葉結(jié)點調(diào)整目標函數(shù)的界否則，根據(jù)這個葉結(jié)點調(diào)整目標函數(shù)的界，依次考察依次考察表表PT中的結(jié)點，將

27、超出目標函數(shù)界的結(jié)點丟棄，然中的結(jié)點，將超出目標函數(shù)界的結(jié)點丟棄，然后從表后從表PT中選取使目標函數(shù)取得極值的結(jié)點繼續(xù)進中選取使目標函數(shù)取得極值的結(jié)點繼續(xù)進行擴展。行擴展。2022-5-21算法設(shè)計與分析28 加入限界的優(yōu)先隊列式分支限界法加入限界的優(yōu)先隊列式分支限界法也是從根結(jié)點也是從根結(jié)點A開始開始搜索解空間樹的。搜索解空間樹的。 用一個用一個極大堆極大堆來表示活結(jié)點表的優(yōu)先隊列，該優(yōu)先隊列來表示活結(jié)點表的優(yōu)先隊列，該優(yōu)先隊列的優(yōu)先級定義為的優(yōu)先級定義為活結(jié)點所擁有的活結(jié)點所擁有的價值價值。用。用BOUND來計來計算其上界，將上界算其上界，將上界當前最優(yōu)解的結(jié)點剪枝。當前最優(yōu)解的結(jié)點剪枝。

28、ABCDEFGHIJKLMNO11100100110010w=16, 15, 15，p=45, 25, 25，c=302022-5-21算法設(shè)計與分析29 初始時堆為空，擴展結(jié)點初始時堆為空，擴展結(jié)點A得到它的得到它的2個兒子結(jié)點個兒子結(jié)點B和和C。 這這2個結(jié)點均為個結(jié)點均為可行結(jié)點可行結(jié)點，因此被加入到堆中，結(jié)點，因此被加入到堆中，結(jié)點A被被舍棄。結(jié)點舍棄。結(jié)點B獲得的當前價值是獲得的當前價值是45，而結(jié)點，而結(jié)點C的當前價值的當前價值為為0。Bestp = 0，C.up = 50。ABCDEFGHIJKLMNO11100100110010w=16, 15, 15，p=45, 25, 25

29、，c=302022-5-21算法設(shè)計與分析30 由于結(jié)點由于結(jié)點B的價值大于結(jié)點的價值大于結(jié)點C的價值，所以結(jié)點的價值，所以結(jié)點B是堆中最是堆中最大元素，從而成為下一個擴展結(jié)點。大元素，從而成為下一個擴展結(jié)點。 擴展結(jié)點擴展結(jié)點B得到結(jié)點得到結(jié)點D和和E。D不是可行結(jié)點，被舍去。不是可行結(jié)點，被舍去。E是是可行結(jié)點被加入到堆中?？尚薪Y(jié)點被加入到堆中。E的價值為的價值為45，成為當前堆中最大，成為當前堆中最大元素，從而成為下一個擴展結(jié)點。元素，從而成為下一個擴展結(jié)點。 Bestp = 0，E.up = 68。ABCDEFGHIJKLMNO11100100110010w=16, 15, 15，p=

30、45, 25, 25，c=302022-5-21算法設(shè)計與分析31 擴展結(jié)點擴展結(jié)點E得到得到2個葉結(jié)點個葉結(jié)點J和和K。J是不可行結(jié)點，被舍是不可行結(jié)點，被舍棄。棄。K是一個可行葉結(jié)點，表示所求問題的一個可行解，是一個可行葉結(jié)點，表示所求問題的一個可行解，其價值為其價值為45。 Bestp = 45。 此時，堆中僅剩下一個活結(jié)點此時，堆中僅剩下一個活結(jié)點C。ABCDEFGHIJKLMNO11100100110010w=16, 15, 15，p=45, 25, 25，c=302022-5-21算法設(shè)計與分析32 此時，堆中僅剩下一個活結(jié)點此時，堆中僅剩下一個活結(jié)點C，它成為當前擴展結(jié)點。，它成為當前擴展結(jié)點。它的它的2個兒子結(jié)點個兒子結(jié)點F和和G均為可行結(jié)點。均為可行結(jié)點。 Bestp = 45，G.up = 25 bestp，結(jié)點，結(jié)點G被剪枝。被剪枝。ABCDEFGHIJKLMNO11100100110010w=16, 15, 15，p=45, 25, 25，c=302022-5-21算法設(shè)計與分析33結(jié)點結(jié)點F的的2個兒子結(jié)點個兒子結(jié)點L和和M均為葉結(jié)點。均為葉結(jié)點。 Bestp = 45，M.up = 25 b