分支限界法 (1)

1、算法設計與分析算法設計與分析清華大學出版社清華大學出版社第第9章章 分支限界法分支限界法 9.1 概概 述述 9.2 圖問題中的分支限界法圖問題中的分支限界法9.3 組合問題中的分支限界法組合問題中的分支限界法9.4 實驗項目實驗項目電路布線問題電路布線問題來源：http:/ 概概 述述 9.1.1 解空間樹的動態(tài)搜索（解空間樹的動態(tài)搜索（2）9.1.2 分支限界法的設計思想分支限界法的設計思想9.1.3 分支限界法的時間性能分支限界法的時間性能來源：http:/ 分支限界法首先確定一個合理的限界函數(shù)，并根據(jù)限分支限界法首先確定一個合理的限界函數(shù)，并根據(jù)限界函數(shù)確定目標函數(shù)的界界函數(shù)確定目標函

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

3、。依次從表）中。依次從表PT中選取使目標函數(shù)的中選取使目標函數(shù)的值取得極值的結點成為當前擴展結點，重復上述過程，直值取得極值的結點成為當前擴展結點，重復上述過程，直到找到最優(yōu)解。到找到最優(yōu)解。9.1.1 解空間樹的動態(tài)搜索（解空間樹的動態(tài)搜索（2） 來源：http:/ 隨著這個遍歷過程的不斷深入，表隨著這個遍歷過程的不斷深入，表PT中所估算的目標函中所估算的目標函數(shù)的界越來越接近問題的最優(yōu)解。當搜索到一個葉子結點時數(shù)的界越來越接近問題的最優(yōu)解。當搜索到一個葉子結點時，如果該結點的目標函數(shù)值是表，如果該結點的目標函數(shù)值是表PT中的極值（對于最小化問中的極值（對于最小化問題，是極小值；對于最大化問

4、題，是極大值），則該葉子結題，是極小值；對于最大化問題，是極大值），則該葉子結點對應的解就是問題的最優(yōu)解；否則，根據(jù)這個葉子結點調(diào)點對應的解就是問題的最優(yōu)解；否則，根據(jù)這個葉子結點調(diào)整目標函數(shù)的界（對于最小化問題，調(diào)整上界；對于最大化整目標函數(shù)的界（對于最小化問題，調(diào)整上界；對于最大化問題，調(diào)整下界），依次考察表問題，調(diào)整下界），依次考察表PT中的結點，將超出目標函中的結點，將超出目標函數(shù)界的結點丟棄，然后從表數(shù)界的結點丟棄，然后從表PT中選取使目標函數(shù)取得極值的中選取使目標函數(shù)取得極值的結點繼續(xù)進行擴展。結點繼續(xù)進行擴展。來源：http:/ 例：例：0/1背包問題。假設有背包問題。假設有4個

5、物品，其重量分別為個物品，其重量分別為(4, 7, 5, 3)，價值分別為，價值分別為(40, 42, 25, 12)，背包容量，背包容量W=10。首先，將給。首先，將給定物品按單位重量價值從大到小排序，結果如下：定物品按單位重量價值從大到小排序，結果如下：物品物品重量重量(w)價值價值(v)價值價值/重量重量(v/w)144010274263525543124來源：http:/ 應用貪心法求得近似解為應用貪心法求得近似解為(1, 0, 0, 0)，獲得的價，獲得的價值為值為40，這可以作為，這可以作為0/1背包問題的下界。背包問題的下界。 如何求得如何求得0/1背包問題的一個合理的上界呢？考

6、背包問題的一個合理的上界呢？考慮最好情況，背包中裝入的全部是第慮最好情況，背包中裝入的全部是第1個物品且可以個物品且可以將背包裝滿，則可以得到一個非常簡單的上界的計將背包裝滿，則可以得到一個非常簡單的上界的計算方法：算方法：ub=W(v1/w1)=1010=100。于是，得到。于是，得到了目標函數(shù)的界了目標函數(shù)的界40, 100。 限界函數(shù)為：限界函數(shù)為： )()(11iiwvwWvub來源：http:/ v=0ub=100w=4, v=40ub=76w=0, v=0ub=60w=11無效解無效解w=4, v=40ub=70w=9, v=65ub=69w=4, v=40ub=64w=12無效解

7、無效解w=9, v=65ub=65234567891分支限界法求解分支限界法求解0/1背包問題背包問題來源：http:/ 分支限界法求解分支限界法求解0/1背包問題，其搜索空間如圖背包問題，其搜索空間如圖9.1所所示，具體的搜索過程如下：示，具體的搜索過程如下：（1）在根結點）在根結點1，沒有將任何物品裝入背包，因此，背包，沒有將任何物品裝入背包，因此，背包的重量和獲得的價值均為的重量和獲得的價值均為0，根據(jù)限界函數(shù)計算結點，根據(jù)限界函數(shù)計算結點1的目的目標函數(shù)值為標函數(shù)值為1010=100；（2）在結點）在結點2，將物品，將物品1裝入背包，因此，背包的重量為裝入背包，因此，背包的重量為4，獲

8、得的價值為獲得的價值為40，目標函數(shù)值為，目標函數(shù)值為40 + (10-4)6=76，將結，將結點點2加入待處理結點表加入待處理結點表PT中；在結點中；在結點3，沒有將物品，沒有將物品1裝入裝入背包，因此，背包的重量和獲得的價值仍為背包，因此，背包的重量和獲得的價值仍為0，目標函數(shù)，目標函數(shù)值為值為10660，將結點，將結點3加入表加入表PT中；中；（3）在表）在表PT中選取目標函數(shù)值取得極大的結點中選取目標函數(shù)值取得極大的結點2優(yōu)先進優(yōu)先進行搜索；行搜索； 來源：http:/ + (10-4)5=70，將結點，將結點5加入表加入表PT中；中；（5）在表）在表PT中選取目標函數(shù)值取得極大的結點

9、中選取目標函數(shù)值取得極大的結點5優(yōu)先進行優(yōu)先進行搜索；搜索；（6）在結點）在結點6，將物品，將物品3裝入背包，因此，背包的重量為裝入背包，因此，背包的重量為9，獲得的價值為獲得的價值為65，目標函數(shù)值為，目標函數(shù)值為65 + (10-9)4=69，將結，將結點點6加入表加入表PT中；在結點中；在結點7，沒有將物品，沒有將物品3裝入背包，因此，裝入背包，因此，背包的重量和獲得的價值與結點背包的重量和獲得的價值與結點5相同，目標函數(shù)值為相同，目標函數(shù)值為40 + (10-4)464，將結點，將結點6加入表加入表PT中；中；來源：http:/ 分支限界法的設計思想分支限界法的設計思想 假設求解最大化

10、問題，解向量為假設求解最大化問題，解向量為X=(x1, x2, , xn)，其，其中，中，xi的取值范圍為某個有窮集合的取值范圍為某個有窮集合Si，|Si|=ri（1in）。在）。在使用分支限界法搜索問題的解空間樹時，首先根據(jù)限界函使用分支限界法搜索問題的解空間樹時，首先根據(jù)限界函數(shù)估算目標函數(shù)的界數(shù)估算目標函數(shù)的界down, up，然后從根結點出發(fā)，擴展，然后從根結點出發(fā)，擴展根結點的根結點的r1個孩子結點，從而構成分量個孩子結點，從而構成分量x1的的r1種可能的取值種可能的取值方式。對這方式。對這r1個孩子結點分別估算可能取得的目標函數(shù)值個孩子結點分別估算可能取得的目標函數(shù)值bound(x

11、1)，其含義是以該孩子結點為根的子樹所可能取得，其含義是以該孩子結點為根的子樹所可能取得的目標函數(shù)值不大于的目標函數(shù)值不大于bound(x1)，也就是部分解應滿足：，也就是部分解應滿足： bound(x1)bound(x1, x2) bound(x1, x2, , xk) bound(x1, x2, , xn)來源：http:/ 若某孩子結點的目標函數(shù)值超出目標函數(shù)的界，則將該若某孩子結點的目標函數(shù)值超出目標函數(shù)的界，則將該孩子結點丟棄；否則，將該孩子結點保存在待處理結點表孩子結點丟棄；否則，將該孩子結點保存在待處理結點表PT中。從表中。從表PT中選取使目標函數(shù)取得極大值的結點作為下中選取使目

12、標函數(shù)取得極大值的結點作為下一次擴展的根結點，重復上述過程，當?shù)竭_一個葉子結點一次擴展的根結點，重復上述過程，當?shù)竭_一個葉子結點時，就得到了一個可行解時，就得到了一個可行解X=(x1, x2, , xn)及其目標函數(shù)值及其目標函數(shù)值bound(x1, x2, , xn)。 如果如果bound(x1, x2, , xn)是表是表PT中目標函數(shù)值最大的結點，中目標函數(shù)值最大的結點，則則bound(x1, x2, , xn)就是所求問題的最大值，就是所求問題的最大值，(x1, x2, , xn)就是問題的最優(yōu)解；就是問題的最優(yōu)解； 如果如果bound(x1, x2, , xn)不是表不是表PT中目標

13、函數(shù)值最大的結中目標函數(shù)值最大的結點，說明還存在某個部分解對應的結點，其上界大于點，說明還存在某個部分解對應的結點，其上界大于bound(x1, x2, , xn)。于是，用。于是，用bound(x1, x2, , xn)調(diào)整目標調(diào)整目標函數(shù)的下界，即令函數(shù)的下界，即令down=bound(x1, x2, , xn)，并將表，并將表PT中中超出目標函數(shù)下界超出目標函數(shù)下界down的結點刪除，然后選取目標函數(shù)值的結點刪除，然后選取目標函數(shù)值取得極大值的結點作為下一次擴展的根結點，繼續(xù)搜索，取得極大值的結點作為下一次擴展的根結點，繼續(xù)搜索，直到某個葉子結點的目標函數(shù)值在表直到某個葉子結點的目標函數(shù)

14、值在表PT中最大。中最大。 來源：http:/ up；2將待處理結點表將待處理結點表PT初始化為空；初始化為空；3對根結點的每個孩子結點對根結點的每個孩子結點x執(zhí)行下列操作執(zhí)行下列操作 3.1 估算結點估算結點x的目標函數(shù)值的目標函數(shù)值value; 3.2 若若(value=down)，則將結點，則將結點x加入表加入表PT中；中；4循環(huán)直到某個葉子結點的目標函數(shù)值在表循環(huán)直到某個葉子結點的目標函數(shù)值在表PT中最大中最大 4.1 i=表表PT中值最大的結點；中值最大的結點； 4.2 對結點對結點i的每個孩子結點的每個孩子結點x執(zhí)行下列操作執(zhí)行下列操作 4.2.1 估算結點估算結點x的目標函數(shù)值的

15、目標函數(shù)值value; 4.2.2 若若(value=down)，則將結點，則將結點x加入表加入表PT中；中； 4.2.3 若若(結點結點x是葉子結點且結點是葉子結點且結點x的的value值在表值在表PT中最大中最大)， 則將結點則將結點x對應的解輸出，算法結束；對應的解輸出，算法結束； 4.2.4 若若(結點結點x是葉子結點但結點是葉子結點但結點x的的value值在表值在表PT中不是最大中不是最大)， 則令則令down=value，并且將表，并且將表PT中所有小于中所有小于value的結點刪除；的結點刪除；來源：http:/ 來源：http:/ 對每個擴展結點保存該結點到根結點的路徑；對每個

16、擴展結點保存該結點到根結點的路徑； 在搜索過程中構建搜索經(jīng)過的樹結構，在求得最優(yōu)解時，在搜索過程中構建搜索經(jīng)過的樹結構，在求得最優(yōu)解時，從葉子結點不斷回溯到根結點，以確定最優(yōu)解中的各個分量。從葉子結點不斷回溯到根結點，以確定最優(yōu)解中的各個分量。 來源：http:/ (1,0,0)64 (1,0,1,0)65(a) 擴展根結點后表擴展根結點后表PT狀態(tài)狀態(tài) (b) 擴展結點擴展結點2后表后表PT狀態(tài)狀態(tài)(c) 擴展結點擴展結點5后表后表PT狀態(tài)狀態(tài) (d) 擴展結點擴展結點6后表后表PT狀態(tài)，最優(yōu)解為狀態(tài)，最優(yōu)解為(1,0,1,0)65圖圖9.2 方法確定方法確定0/1背包問題最優(yōu)解的各分量背包

17、問題最優(yōu)解的各分量(0)60 (1,0,1)69 (1,0,0)64(1)76 (0)60(0)60 (1,0)70 例如圖例如圖9.1所示所示0/1背包問題，為了對每個擴展結點保存該結背包問題，為了對每個擴展結點保存該結點到根結點的路徑，將部分解點到根結點的路徑，將部分解(x1, , xi)和該部分解的目標和該部分解的目標函數(shù)值都存儲在待處理結點表函數(shù)值都存儲在待處理結點表PT中，在搜索過程中表中，在搜索過程中表PT的狀態(tài)如圖的狀態(tài)如圖9.2所示。所示。來源：http:/ 擴展根結點后擴展根結點后 (b) 擴展結點擴展結點2后后(c) 擴展結點擴展結點5后后 (d) 擴展結點擴展結點6后，最

18、優(yōu)解為后，最優(yōu)解為(1,0,1,0)65 圖圖9.3 方法確定方法確定0/1背包問題最優(yōu)解的各分量背包問題最優(yōu)解的各分量(0,76) (0,60)PTST(0,60) (1,70)PTST(0,76)(0,60) (0,69) (0,64)PTST(0,76) (1,70)(0,60) (0,64) (1,65)PTST(0,76) (1,70) (0,69)圖圖9.1所示所示0/1背包問題，為了在搜索過程中構建搜索經(jīng)過的背包問題，為了在搜索過程中構建搜索經(jīng)過的樹結構，設一個表樹結構，設一個表ST，在表，在表PT中取出最小值結點進行擴充中取出最小值結點進行擴充時，將最小值結點存儲到表時，將最小

19、值結點存儲到表ST中，表中，表PT和表和表ST的數(shù)據(jù)結構的數(shù)據(jù)結構為為(物品物品i-1的選擇結果，的選擇結果，ub)，在搜，在搜索過程中表索過程中表PT和表和表ST的狀態(tài)如圖的狀態(tài)如圖9.3所示。所示。來源：http:/ 分支限界法的時間性能分支限界法的時間性能 分支限界法和回溯法實際上都屬于蠻力窮舉法，當分支限界法和回溯法實際上都屬于蠻力窮舉法，當然不能指望它有很好的最壞時間復雜性，遍歷具有指數(shù)然不能指望它有很好的最壞時間復雜性，遍歷具有指數(shù)階個結點的解空間樹，在最壞情況下，時間復雜性肯定階個結點的解空間樹，在最壞情況下，時間復雜性肯定為指數(shù)階。為指數(shù)階。 與回溯法不同的是，分支限界法首先擴

20、展解空間樹與回溯法不同的是，分支限界法首先擴展解空間樹中的上層結點，并采用限界函數(shù)，有利于實行大范圍剪中的上層結點，并采用限界函數(shù)，有利于實行大范圍剪枝，同時，根據(jù)限界函數(shù)不斷調(diào)整搜索方向，選擇最有枝，同時，根據(jù)限界函數(shù)不斷調(diào)整搜索方向，選擇最有可能取得最優(yōu)解的子樹優(yōu)先進行搜索。所以，如果選擇可能取得最優(yōu)解的子樹優(yōu)先進行搜索。所以，如果選擇了結點的合理擴展順序以及設計了一個好的限界函數(shù)，了結點的合理擴展順序以及設計了一個好的限界函數(shù)，分支界限法可以快速得到問題的解。分支界限法可以快速得到問題的解。來源：http:/ 分支限界法的較高效率是以付出一定代價為基礎的，其分支限界法的較高效率是以付出一

21、定代價為基礎的，其工作方式也造成了算法設計的復雜性。首先，一個更好的限工作方式也造成了算法設計的復雜性。首先，一個更好的限界函數(shù)通常需要花費更多的時間計算相應的目標函數(shù)值，而界函數(shù)通常需要花費更多的時間計算相應的目標函數(shù)值，而且對于具體的問題實例，通常需要進行大量實驗，才能確定且對于具體的問題實例，通常需要進行大量實驗，才能確定一個好的限界函數(shù)；其次，由于分支限界法對解空間樹中結一個好的限界函數(shù)；其次，由于分支限界法對解空間樹中結點的處理是跳躍式的，因此，在搜索到某個葉子結點得到最點的處理是跳躍式的，因此，在搜索到某個葉子結點得到最優(yōu)值時，為了從該葉子結點求出對應的最優(yōu)解中的各個分量，優(yōu)值時，

22、為了從該葉子結點求出對應的最優(yōu)解中的各個分量，需要對每個擴展結點保存該結點到根結點的路徑，或者在搜需要對每個擴展結點保存該結點到根結點的路徑，或者在搜索過程中構建搜索經(jīng)過的樹結構，這使得算法的設計較為復索過程中構建搜索經(jīng)過的樹結構，這使得算法的設計較為復雜；再次，算法要維護一個待處理結點表雜；再次，算法要維護一個待處理結點表PTPT，并且需要在表，并且需要在表PTPT中快速查找取得極值的結點，等等。這都需要較大的存儲中快速查找取得極值的結點，等等。這都需要較大的存儲空間，在最壞情況下，分支限界法需要的空間復雜性是指數(shù)空間，在最壞情況下，分支限界法需要的空間復雜性是指數(shù)階。階。 來源：http:

23、/ 圖問題中的分支限界法圖問題中的分支限界法 9.2.1 TSP問題問題 9.2.2 多段圖的最短路徑問題多段圖的最短路徑問題來源：http:/ TSP問題問題 TSP TSP問題是指旅行家要旅行問題是指旅行家要旅行n n個城市，要求各個城個城市，要求各個城市經(jīng)歷且僅經(jīng)歷一次然后回到出發(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 無向圖及其代價矩陣無向圖及其

24、代價矩陣來源：http:/ 采用貪心法求得近似解為采用貪心法求得近似解為135421，其路徑，其路徑長度為長度為1+2+3+7+3=16，這可以作為，這可以作為TSP問題的上界。問題的上界。 把矩陣中每一行最小的元素相加，可以得到一個簡單的把矩陣中每一行最小的元素相加，可以得到一個簡單的下界，其路徑長度為下界，其路徑長度為1+3+1+3+2=10，但是還有一個信息量，但是還有一個信息量更大的下界：考慮一個更大的下界：考慮一個TSP問題的完整解，在每條路徑上，問題的完整解，在每條路徑上，每個城市都有兩條鄰接邊，一條是進入這個城市的，另一每個城市都有兩條鄰接邊，一條是進入這個城市的，另一條是離開這

25、個城市的，那么，如果把矩陣中每一行最小的條是離開這個城市的，那么，如果把矩陣中每一行最小的兩個元素相加再除以兩個元素相加再除以2，如果圖中所有的代價都是整數(shù)，再，如果圖中所有的代價都是整數(shù)，再對這個結果向上取整，就得到了一個合理的下界。對這個結果向上取整，就得到了一個合理的下界。 lb=(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14 于是，得到了目標函數(shù)的界于是，得到了目標函數(shù)的界14, 16。需要強調(diào)的是，這個解并不是一個合法的選擇（可能沒有需要強調(diào)的是，這個解并不是一個合法的選擇（可能沒有構成哈密頓回路），它僅僅給出了一個參考下界。構成哈密頓回路），它僅僅給出了一個參

26、考下界。 來源：http:/ 例如圖例如圖9.4所示無向圖，如果部分解包含邊所示無向圖，如果部分解包含邊(1, 4)，則該部分，則該部分解的下界是解的下界是lb=(1+5)+(3+6)+(1+2)+(3+5)+(2+3)/2=16。 UrUrjikiiiijrrrrclb2/ )2(111行最小的兩個元素素行不在路徑上的最小元來源：http:/ 來源：http:/ （9）在表PT中選取目標函數(shù)值極小的結點13優(yōu)先進行搜索；（10）在結點14，從城市4到城市2，目標函數(shù)值為(1+3)+(3+7)+(1+2)+(3+7)+(2+3)/2=16，最后從城市2回到城市1，目標函數(shù)值為(1+3)+(3+

27、7)+(1+2)+(3+7)+(2+3)/2=16，由于結點14為葉子結點，得到一個可行解，其路徑長度為16；來源：http:/ 擴展結點擴展結點16后的狀態(tài)，最優(yōu)解為后的狀態(tài)，最優(yōu)解為135421圖圖9.6 TSP問題最優(yōu)解的確定問題最優(yōu)解的確定(1, 2)14 (1, 3)14 (1, 4)16(a) 擴展根結點后的狀態(tài)擴展根結點后的狀態(tài) (b) 擴展結點擴展結點2后的狀態(tài)后的狀態(tài)(c) 擴展結點擴展結點3后的狀態(tài)后的狀態(tài)(d) 擴展結點擴展結點11后的狀態(tài)后的狀態(tài)(e) 擴展結點擴展結點13后的狀態(tài)后的狀態(tài)(1, 3)14 (1, 4)16 (1, 2, 3)16 (1, 2, 4)16

28、 (1, 4)16 (1, 2, 3)16 (1, 2, 4)16 (1, 3, 2)16 (1, 3, 4)15 (1, 3, 5)14(1, 4)16 (1, 2, 3)16 (1, 2, 4)16 (1, 3, 2)16 (1, 3, 4)15 (1, 3, 5, 4)14 (1, 4)16 (1, 2, 3)16 (1, 2, 4)16 (1, 3, 2)16 (1, 3, 4)15 (1, 3, 5, 4, 2)16(1, 4)16 (1, 2, 3)16 (1, 2, 4)16 (1, 3, 2)16 (1, 3, 5, 4, 2)16 (1, 3, 4, 5)15(1, 4)16

29、 (1, 2, 3)16 (1, 2, 4)16 (1, 3, 2)16 (1, 3, 5, 4, 2)16 (1, 3, 4, 5)15(f) 擴展結點擴展結點10后的狀態(tài)后的狀態(tài)來源：http:/ 1根據(jù)限界函數(shù)計算目標函數(shù)的下界根據(jù)限界函數(shù)計算目標函數(shù)的下界down；采用貪心法得到上界；采用貪心法得到上界up； 2將待處理結點表將待處理結點表PT初始化為空；初始化為空； 3for (i=1; i=1) 5.1 i=k+1; 5.2 xi=1; 5.3 while (xi=n) 5.3.1 如果路徑上頂點不重復，則如果路徑上頂點不重復，則 根據(jù)式根據(jù)式9.2計算目標函數(shù)值計

30、算目標函數(shù)值lb； if (lb kijpiEvrijjjjvrcrrclbpi21,11min1段的最短邊段的最短邊第第來源：http:/ 應用分支限界法求解圖9.7所示多段圖的最短路徑問題，其搜索空間如圖9.8所示，具體的搜索過程如下（加黑表示該路徑上已經(jīng)確定的邊）：（1）在根結點1，根據(jù)限界函數(shù)計算目標函數(shù)的值為18；（2）在結點2，第1段選擇邊，目標函數(shù)值為lb=4+8+5+3=20，超出目標函數(shù)的界，將結點2丟棄；在結點3，第1段選擇邊，目標函數(shù)值為lb=2+6+5+3=16，將結點3加入待處理結點表PT中；在結點4，第1段選擇邊，目標函數(shù)值為lb=3+4+5+3=1

31、5，將結點4加入表PT中；（3）在表PT中選取目標函數(shù)值極小的結點4優(yōu)先進行搜索；來源：http:/ 分支限界法求解多段圖的最短路徑問題示例分支限界法求解多段圖的最短路徑問題示例(表示該結點被丟棄，結點上方的數(shù)組表示搜索順序表示該結點被丟棄，結點上方的數(shù)組表示搜索順序)724lb=16825lb=18926lb=18535lb=1636lb=181110 57lb=2258lb=16來源：http:/ 為了在搜索過程中構建搜索經(jīng)過的樹結構，設一個表為了在搜索過程中構建搜索經(jīng)過的樹結構，設一個表ST，在表在表PT中取出最小值結點進行擴充時，將最小值結點存儲到表中取出最小值結點進行擴充時，將最小值

32、結點存儲到表ST中，表中，表PT和表和表ST的數(shù)據(jù)結構為的數(shù)據(jù)結構為(第第i段，段，lb)，在搜索過程中表，在搜索過程中表PT和表和表ST的狀態(tài)如下：的狀態(tài)如下：(b) 擴展結點擴展結點3后的狀態(tài)后的狀態(tài)(d) 擴展結點擴展結點5后的狀態(tài)，最優(yōu)解為后的狀態(tài)，最優(yōu)解為03589圖圖9.9 多段圖的最短路徑問題最優(yōu)解的確定多段圖的最短路徑問題最優(yōu)解的確定(1,16) (1,15)(1,16) (2,16) (2,18) (2,18)(1,15)(2,16) (2,18) (2,18) (2,16) (2,18)(1,15) (1,16)(2,16) (2,18) (2,18) (2,18) (3,

33、16)(1,15) (1,16) (2,16)(a) 擴展根結點后的狀態(tài)擴展根結點后的狀態(tài) PT ST ST PT (c) 擴展結點擴展結點4后的狀態(tài)后的狀態(tài)ST ST 回溯過程是：(3,16)(2,16)(1,15)。來源：http:/ 1根據(jù)限界函數(shù)計算目標函數(shù)的下界根據(jù)限界函數(shù)計算目標函數(shù)的下界down；采用貪心法得到上界；采用貪心法得到上界up； 2將待處理結點表將待處理結點表PT初始化為空；初始化為空； 3for (i=1; i=1) 5.1 對頂點對頂點u的所有鄰接點的所有鄰接點v 5.1.1 根據(jù)式根據(jù)式9.3計算目標函數(shù)值計算目標函數(shù)值lb; 5.1.2 若若lb=up，則將，

34、則將i,lb存儲在表存儲在表PT中；中； 5.2 如果如果i= =k-1且葉子結點的且葉子結點的lb值在表值在表PT中最小，中最小， 則輸出該葉子結點對應的最優(yōu)解；則輸出該葉子結點對應的最優(yōu)解； 5.3 否則，如果否則，如果i= =k-1且表且表PT中的葉子結點的中的葉子結點的lb值不是最小，則值不是最小，則 5.3.1 up=表表PT中的葉子結點最小的中的葉子結點最小的lb值值; 5.3.2 將表將表PT中目標函數(shù)值超出中目標函數(shù)值超出up的結點刪除；的結點刪除； 5.4 u=表表PT中中l(wèi)b最小的結點的最小的結點的v值；值； 5.5 i=表表PT中中l(wèi)b最小的結點的最小的結點的i值；值；i

35、+;來源：http:/ 9.3 組合問題中的分支限界法組合問題中的分支限界法 9.3.1 9.3.1 任務分配問題任務分配問題 9.3.2 9.3.2 批處理作業(yè)調(diào)度問題批處理作業(yè)調(diào)度問題來源：http:/ 任務分配問題任務分配問題 任務分配問題要求把任務分配問題要求把n項任務分配給項任務分配給n個人，個人，每個人完成每項任務的成本不同，要求分配總成本每個人完成每項任務的成本不同，要求分配總成本最小的最優(yōu)分配方案。如圖最小的最優(yōu)分配方案。如圖9.10所示是一個任務分所示是一個任務分配的成本矩陣。配的成本矩陣。 C9 2 7 86 4 3 75 8 1 87 6 9 4任務任務1 任務任務2 任

36、務任務3 任務任務4人員人員a人員人員b人員人員c人員人員d圖圖9.10 任務分配問題的成本矩陣任務分配問題的成本矩陣來源：http:/ 14之間的某個值。之間的某個值。來源：http:/ （式（式9.4） nikkvlb1行的最小值第來源：http:/ + (3+1+4)=17，超出目標函數(shù)的界10, 14，將結點2丟棄；在結點3，將任務2分配給人員a，獲得的成本為2，目標函數(shù)值為2 + (3+1+4)=10，將結點3加入待處理結點表PT中；在結點4，將任務3分配給人員a，獲得的成本為7，目標函數(shù)值為7 + (3+1+4)=15，超出目標函數(shù)的界10, 14，將結點4丟棄；在結點5，將任務4

37、分配給人員a，獲得的成本為8，目標函數(shù)值為8 + (3+1+4)=16，超出目標函數(shù)的界10, 14，將結點5丟棄； 應用分支限界法求解圖9.10所示任務分配問題，對解空間樹的搜索如圖9.11所示，具體的搜索過程如下：（1）在根結點1，沒有分配任務，根據(jù)限界函數(shù)估算目標函數(shù)值為2+3+1+4=10； 來源：http:/ （5）在表PT中選取目標函數(shù)值極小的結點7優(yōu)先進行搜索；（6）在結點9，將任務1分配給人員c，獲得的成本為5+5=10，目標函數(shù)值為10+4=14，將結點9加入表PT中；在結點10，將任務4分配給人員c，獲得的成本為5+8=13，目標函數(shù)值為13+4=17，超出目標函數(shù)的界10

38、, 14，將結點10丟棄；來源：http:/ 14，將結點12丟棄；（9）在表PT中選取目標函數(shù)值極小的結點11優(yōu)先進行搜索；（10）在結點13，將任務4分配給人員d，獲得的成本為9+4=13，目標函數(shù)值為13，由于結點13是葉子結點，同時結點13的目標函數(shù)值是表PT中的極小值，所以，結點13對應的解即是問題的最優(yōu)解，搜索結束。來源：http:/ 分支限界法求解任務分配問題示例分支限界法求解任務分配問題示例(表示該結點被丟棄，結點上方的數(shù)組表示搜索順序表示該結點被丟棄，結點上方的數(shù)組表示搜索順序)23567891213111來源：http:/ 為了在搜索過程中構建搜索經(jīng)過的樹結構，設一個表為了

39、在搜索過程中構建搜索經(jīng)過的樹結構，設一個表ST，在表，在表PT中取出最小值結點進行擴充時，將最小值結點中取出最小值結點進行擴充時，將最小值結點存儲到表存儲到表ST中，表中，表PT和表和表ST的數(shù)據(jù)結構為的數(shù)據(jù)結構為(人員人員i- -1分配的分配的任務任務,lb)(e) 擴展結點擴展結點11后的狀態(tài)，最優(yōu)解為后的狀態(tài)，最優(yōu)解為2a 1b 3c 4d圖圖9.12 任務分配問題最優(yōu)解的確定任務分配問題最優(yōu)解的確定(0,10)(2,13) (2,10) (2,14)(0,10)(2,13) (2,14) (3,14)(0,10) (2,10) (2,14) (3,14) (1,13)(0,10) (2

40、,10) (2,13) (0,10) (2,10) (2,13) (1,13)(a) 擴展根結點后的狀態(tài)擴展根結點后的狀態(tài) (b) 擴展結點擴展結點3后的狀態(tài)后的狀態(tài) PTSTPTST PT (c) 擴展結點擴展結點7后的狀態(tài)后的狀態(tài) (d) 擴展結點擴展結點6后的狀態(tài)后的狀態(tài)(2,14) (3,14) (3,13)PTSTPTST ST 回溯過程是：(3,13)(1,13)(2,13)(0,10) 。來源：http:/ 1根據(jù)限界函數(shù)計算目標函數(shù)的下界根據(jù)限界函數(shù)計算目標函數(shù)的下界down；采用貪心法得到上界；采用貪心法得到上界up； 2將待處理結點表將待處理結點表PT初始化為空；初始化為空

41、； 3for (i=1; i=1) 5.1 xk=1; 5.2 while (xk=n) 5.2.1 如果人員如果人員k分配任務分配任務xk不發(fā)生沖突，則不發(fā)生沖突，則 根據(jù)式根據(jù)式9.4計算目標函數(shù)值計算目標函數(shù)值lb; 若若lb=up，則將，則將i,lb存儲在表存儲在表PT中；中； 5.2.2 xk=xk+1; 5.3 如果如果k= =n且葉子結點的且葉子結點的lb值在表值在表PT中最小，中最小， 則輸出該葉子結點對應的最優(yōu)解；則輸出該葉子結點對應的最優(yōu)解； 5.4 否則，如果否則，如果k= =n且表且表PT中的葉子結點的中的葉子結點的lb值不是最小，則值不

42、是最小，則 5.4.1 up=表表PT中的葉子結點最小的中的葉子結點最小的lb值值; 5.4.2 將表將表PT中超出目標函數(shù)界的結點刪除；中超出目標函數(shù)界的結點刪除； 5.5 i=表表PT中中l(wèi)b最小的結點的最小的結點的xk值；值； 5.6 k=表表PT中中l(wèi)b最小的結點的最小的結點的k值；值；k+;來源：http:/ 批處理作業(yè)調(diào)度問題批處理作業(yè)調(diào)度問題 給定給定n個作業(yè)的集合個作業(yè)的集合J=J1, J2, , Jn，每個作業(yè)都有，每個作業(yè)都有3項項任務分別在任務分別在3臺機器上完成，作業(yè)臺機器上完成，作業(yè)Ji需要機器需要機器j的處理時間為的處理時間為tij（1in, 1j3），每個作業(yè)必須

43、先由機器），每個作業(yè)必須先由機器1處理，再由機器處理，再由機器2處理，最后由機器處理，最后由機器3處理。批處理作業(yè)調(diào)度問題要求確定這處理。批處理作業(yè)調(diào)度問題要求確定這n個作業(yè)的最優(yōu)處理順序，使得從第個作業(yè)的最優(yōu)處理順序，使得從第1個作業(yè)在機器個作業(yè)在機器1上處理開上處理開始，到最后一個作業(yè)在機器始，到最后一個作業(yè)在機器3上處理結束所需的時間最少。上處理結束所需的時間最少。 顯然，批處理作業(yè)的一個最優(yōu)調(diào)度應使機器顯然，批處理作業(yè)的一個最優(yōu)調(diào)度應使機器1沒有空閑沒有空閑時間，且機器時間，且機器2和機器和機器3的空閑時間最小。可以證明，存在一的空閑時間最小。可以證明，存在一個最優(yōu)作業(yè)調(diào)度使得在機器個

44、最優(yōu)作業(yè)調(diào)度使得在機器1、機器、機器2和機器和機器3上作業(yè)以相同上作業(yè)以相同次序完成。次序完成。 來源：http:/ 5 7 910 5 2 9 9 5 7 8 10J1J2J3J4機器1 機器2 機器3 若處理順序為若處理順序為(J2, J3, J1, J4)，則從作業(yè)，則從作業(yè)2在機器在機器1處理開始處理開始到作業(yè)到作業(yè)4在機器在機器3處理完成的調(diào)度方案如圖處理完成的調(diào)度方案如圖9.14所示。所示。 J2:10 J3:9 J1:5 J4:7機器機器1機器機器2機器機器3 圖圖9.14 批處理調(diào)度問題的調(diào)度方案批處理調(diào)度問題的調(diào)度方案空閑空閑:10 J2:5 J3:9 J1:7 J4:8空閑空閑:15 J2:2 J3:5 J1:9 J4:10 設設J=J1, J2, J3, J4是是4個待處理的作業(yè)，每個作業(yè)的處個待處理的作業(yè)，每個作業(yè)的處理順序相