分支限界法課件

1、分支限界法分支限界法分支限界法的基本思想分支限界法在各種問題中的應(yīng)用分支限界法的基本思想 分支限界法首先確定一個合理的限界函數(shù)，并根據(jù)限界函數(shù)確定目標(biāo)函數(shù)的界down, up 。然后，按照廣度優(yōu)先策略遍歷問題的解空間樹，在分支結(jié)點(diǎn)上，依次搜索該結(jié)點(diǎn)的所有孩子結(jié)點(diǎn)，分別估算這些孩子結(jié)點(diǎn)的目標(biāo)函數(shù)的可能取值，如果某孩子結(jié)點(diǎn)的目標(biāo)函數(shù)可能取得的值超出目標(biāo)函數(shù)的界，則將其丟棄；否則，將其加入待處理結(jié)點(diǎn)表（表PT）中。依次從表PT中選取使目標(biāo)函數(shù)的值取得極值的結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，重復(fù)上述過程，直到找到最優(yōu)解。9.1 概述9.1.1 解空間樹的動態(tài)搜索（2） 分支限界法首先確定一個合理的限界函數(shù)，并根據(jù)

2、 隨著遍歷過程的深入，表PT中所估算的目標(biāo)函數(shù)的界越來越接近問題的最優(yōu)解。當(dāng)搜索到一個葉子結(jié)點(diǎn)時，如果該結(jié)點(diǎn)的目標(biāo)函數(shù)值是表PT中的極值，則該葉子結(jié)點(diǎn)對應(yīng)的解就是問題的最優(yōu)解；否則，根據(jù)這個葉子結(jié)點(diǎn)調(diào)整目標(biāo)函數(shù)的界（對于最小化問題，調(diào)整上界；對于最大化問題，調(diào)整下界），依次考察表PT中的結(jié)點(diǎn)，將超出目標(biāo)函數(shù)界的結(jié)點(diǎn)丟棄，然后從表PT中選取使目標(biāo)函數(shù)取得極值的結(jié)點(diǎn)繼續(xù)進(jìn)行擴(kuò)展。 隨著遍歷過程的深入，表PT中所估算的目標(biāo)函數(shù) 例：0/1背包問題。假設(shè)有4個物品，其重量分別為(4, 7, 5, 3)，價值分別為(40, 42, 25, 12)，背包容量W=10。首先，將給定物品按單位重量價值從大到小

3、排序：物品重量(w)價值(v)價值/重量(v/w)144010274263525543124 例：0/1背包問題。假設(shè)有4個物品，其重量分別（1）應(yīng)用貪心法求得近似解為(1, 0, 0, 0)，獲得的價值為40-作為0/1背包問題的下界。（2）0/1背包問題的上界：最好情況下，背包中裝入的全部是第1個物品且可以將背包裝滿，則ub=W(v1/w1)=1010=100。（3）目標(biāo)函數(shù)的界40, 100。 限界函數(shù)為： （1）應(yīng)用貪心法求得近似解為(1, 0, 0, 0)，獲得的w=0, v=0ub=100w=4, v=40ub=76w=0, v=0ub=60w=11無效解w=4, v=40ub=7

4、0w=9, v=65ub=69w=4, v=40ub=64w=12無效解w=9, v=65ub=65234567891分支限界法求解0/1背包問題w=0, v=0w=4, v=40w=0, v=0w=11 分支限界法求解0/1背包問題，其搜索空間如圖9.1所示，具體的搜索過程如下：（1）在根結(jié)點(diǎn)1，沒有將任何物品裝入背包，因此，背包的重量和獲得的價值均為0，根據(jù)限界函數(shù)計算結(jié)點(diǎn)1的目標(biāo)函數(shù)值為1010=100；（2）在結(jié)點(diǎn)2，將物品1裝入背包，因此，背包的重量為4，獲得的價值為40，目標(biāo)函數(shù)值為40 + (10-4)6=76，將結(jié)點(diǎn)2加入待處理結(jié)點(diǎn)表PT中；在結(jié)點(diǎn)3，沒有將物品1裝入背包，因此

5、，背包的重量和獲得的價值仍為0，目標(biāo)函數(shù)值為10660，將結(jié)點(diǎn)3加入表PT中；（3）在表PT中選取目標(biāo)函數(shù)值取得極大的結(jié)點(diǎn)2優(yōu)先進(jìn)行搜索； 分支限界法求解0/1背包問題，其搜索空間如圖（4）在結(jié)點(diǎn)4，將物品2裝入背包，因此，背包的重量為11，不滿足約束條件，將結(jié)點(diǎn)4丟棄；在結(jié)點(diǎn)5，沒有將物品2裝入背包，因此，背包的重量和獲得的價值與結(jié)點(diǎn)2相同，目標(biāo)函數(shù)值為40 + (10-4)5=70，將結(jié)點(diǎn)5加入表PT中；（5）在表PT中選取目標(biāo)函數(shù)值取得極大的結(jié)點(diǎn)5優(yōu)先進(jìn)行搜索；（6）在結(jié)點(diǎn)6，將物品3裝入背包，因此，背包的重量為9，獲得的價值為65，目標(biāo)函數(shù)值為65 + (10-9)4=69，將結(jié)點(diǎn)6加

6、入表PT中；在結(jié)點(diǎn)7，沒有將物品3裝入背包，因此，背包的重量和獲得的價值與結(jié)點(diǎn)5相同，目標(biāo)函數(shù)值為40 + (10-4)464，將結(jié)點(diǎn)7加入表PT中；（4）在結(jié)點(diǎn)4，將物品2裝入背包，因此，背包的重量為11，不（7）在表PT中選取目標(biāo)函數(shù)值取得極大的結(jié)點(diǎn)6優(yōu)先進(jìn)行搜索；（8）在結(jié)點(diǎn)8，將物品4裝入背包，因此，背包的重量為12，不滿足約束條件，將結(jié)點(diǎn)8丟棄；在結(jié)點(diǎn)9，沒有將物品4裝入背包，因此，背包的重量和獲得的價值與結(jié)點(diǎn)6相同，目標(biāo)函數(shù)值為65；（9）由于結(jié)點(diǎn)9是葉子結(jié)點(diǎn)，同時結(jié)點(diǎn)9的目標(biāo)函數(shù)值是表PT中的極大值，所以，結(jié)點(diǎn)9對應(yīng)的解即是問題的最優(yōu)解，搜索結(jié)束。（7）在表PT中選取目標(biāo)函數(shù)值取

7、得極大的結(jié)點(diǎn)6優(yōu)先進(jìn)行搜索；9.1.2 分支限界法的設(shè)計思想 假設(shè)求解最大化問題，解向量為X=(x1, x2, , xn)，其中，xi的取值范圍為某個有窮集合Si，|Si|=ri（1in）。在使用分支限界法搜索問題的解空間樹時，首先根據(jù)限界函數(shù)估算目標(biāo)函數(shù)的界down, up，然后從根結(jié)點(diǎn)出發(fā)，擴(kuò)展根結(jié)點(diǎn)的r1個孩子結(jié)點(diǎn)，從而構(gòu)成分量x1的r1種可能的取值方式。對這r1個孩子結(jié)點(diǎn)分別估算可能取得的目標(biāo)函數(shù)值bound(x1)，其含義是以該孩子結(jié)點(diǎn)為根的子樹所可能取得的目標(biāo)函數(shù)值不大于bound(x1)，也就是部分解應(yīng)滿足： bound(x1)bound(x1, x2) bound(x1, x2

8、, , xk) bound(x1, x2, , xn)9.1.2 分支限界法的設(shè)計思想 假設(shè)求解最大化問題，解向若某孩子結(jié)點(diǎn)的目標(biāo)函數(shù)值超出目標(biāo)函數(shù)的界，則將該孩子結(jié)點(diǎn)丟棄；否則，將該孩子結(jié)點(diǎn)保存在待處理結(jié)點(diǎn)表PT中。從表PT中選取使目標(biāo)函數(shù)取得極大值的結(jié)點(diǎn)作為下一次擴(kuò)展的根結(jié)點(diǎn)，重復(fù)上述過程，當(dāng)?shù)竭_(dá)一個葉子結(jié)點(diǎn)時，就得到了一個可行解X=(x1, x2, , xn)及其目標(biāo)函數(shù)值bound(x1, x2, , xn)。 如果bound(x1, x2, , xn)是表PT中目標(biāo)函數(shù)值最大的結(jié)點(diǎn)，則bound(x1, x2, , xn)就是所求問題的最大值，(x1, x2, , xn)就是問題的最

9、優(yōu)解；如果bound(x1, x2, , xn)不是表PT中目標(biāo)函數(shù)值最大的結(jié)點(diǎn)，說明還存在某個部分解對應(yīng)的結(jié)點(diǎn)，其上界大于bound(x1, x2, , xn)。于是，用bound(x1, x2, , xn)調(diào)整目標(biāo)函數(shù)的下界，即令down=bound(x1, x2, , xn)，并將表PT中超出目標(biāo)函數(shù)下界down的結(jié)點(diǎn)刪除，然后選取目標(biāo)函數(shù)值取得極大值的結(jié)點(diǎn)作為下一次擴(kuò)展的根結(jié)點(diǎn)，繼續(xù)搜索，直到某個葉子結(jié)點(diǎn)的目標(biāo)函數(shù)值在表PT中最大。 若某孩子結(jié)點(diǎn)的目標(biāo)函數(shù)值超出目標(biāo)函數(shù)的界，則將該孩子結(jié)點(diǎn)丟棄分支限界法求解最大化問題的一般過程分支限界法的一般過程1根據(jù)限界函數(shù)確定目標(biāo)函數(shù)的界down,

10、 up；2將待處理結(jié)點(diǎn)表PT初始化為空；3對根結(jié)點(diǎn)的每個孩子結(jié)點(diǎn)x執(zhí)行下列操作 3.1 估算結(jié)點(diǎn)x的目標(biāo)函數(shù)值value; 3.2 若(value=down)，則將結(jié)點(diǎn)x加入表PT中；4循環(huán)直到某個葉子結(jié)點(diǎn)的目標(biāo)函數(shù)值在表PT中最大 4.1 i=表PT中值最大的結(jié)點(diǎn)； 4.2 對結(jié)點(diǎn)i的每個孩子結(jié)點(diǎn)x執(zhí)行下列操作 4.2.1 估算結(jié)點(diǎn)x的目標(biāo)函數(shù)值value; 4.2.2 若(value=down)，則將結(jié)點(diǎn)x加入表PT中； 4.2.3 若(結(jié)點(diǎn)x是葉子結(jié)點(diǎn)且結(jié)點(diǎn)x的value值在表PT中最大)， 則將結(jié)點(diǎn)x對應(yīng)的解輸出，算法結(jié)束； 4.2.4 若(結(jié)點(diǎn)x是葉子結(jié)點(diǎn)但結(jié)點(diǎn)x的value值在表P

11、T中不是最大)， 則令down=value，并且將表PT中所有小于value的結(jié)點(diǎn)刪除；分支限界法求解最大化問題的一般過程分支限界法的一般過程應(yīng)用分支限界法的關(guān)鍵問題（1）確定合適的限界函數(shù)（2）組織待處理結(jié)點(diǎn)表PT（3）確定最優(yōu)解中的各個分量 應(yīng)用分支限界法的關(guān)鍵問題分支限界法對問題的解空間樹中結(jié)點(diǎn)的處理是跳躍式的，回溯也不是單純地沿著雙親結(jié)點(diǎn)一層一層向上回溯。當(dāng)搜索到某個葉子結(jié)點(diǎn)且該葉子結(jié)點(diǎn)的目標(biāo)函數(shù)值在表PT中最大時（假設(shè)求解最大化問題），求得了問題的最優(yōu)值。但是，卻無法求得該葉子結(jié)點(diǎn)對應(yīng)的最優(yōu)解中的各個分量。這個問題可以用如下2種方法解決： 對每個擴(kuò)展結(jié)點(diǎn)保存該結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑； 在

12、搜索過程中構(gòu)建搜索經(jīng)過的樹結(jié)構(gòu)，在求得最優(yōu)解時，從葉子結(jié)點(diǎn)不斷回溯到根結(jié)點(diǎn)，以確定最優(yōu)解中的各個分量。 分支限界法對問題的解空間樹中結(jié)點(diǎn)的處理是跳躍式的，回溯也不是(0)60 (1,0,0)64 (1,0,1,0)65(a) 擴(kuò)展根結(jié)點(diǎn)后表PT狀態(tài) (b) 擴(kuò)展結(jié)點(diǎn)2后表PT狀態(tài)(c) 擴(kuò)展結(jié)點(diǎn)5后表PT狀態(tài) (d) 擴(kuò)展結(jié)點(diǎn)6后表PT狀態(tài)，最優(yōu)解為(1,0,1,0)65圖9.2 方法確定0/1背包問題最優(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背包問題，為了對每個擴(kuò)展結(jié)點(diǎn)保存該結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑，將部

13、分解(x1, , xi)和該部分解的目標(biāo)函數(shù)值都存儲在待處理結(jié)點(diǎn)表PT中，在搜索過程中表PT的狀態(tài)如圖9.2所示。(0)60 (1,0,0)6(a) 擴(kuò)展根結(jié)點(diǎn)后 (b) 擴(kuò)展結(jié)點(diǎn)2后(c) 擴(kuò)展結(jié)點(diǎn)5后 (d) 擴(kuò)展結(jié)點(diǎn)6后，最優(yōu)解為(1,0,1,0)65 圖9.3 方法確定0/1背包問題最優(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背包問題，為了在搜索過程中構(gòu)建搜索

14、經(jīng)過的樹結(jié)構(gòu)，設(shè)一個表ST，在表PT中取出最大值結(jié)點(diǎn)進(jìn)行擴(kuò)充時，將最大值結(jié)點(diǎn)存儲到表ST中，表PT和表ST的數(shù)據(jù)結(jié)構(gòu)為(物品i-1的選擇結(jié)果，ub)，在搜索過程中表PT和表ST的狀態(tài)如圖9.3所示。(a) 擴(kuò)展根結(jié)點(diǎn)后 9.1.3 分支限界法的時間性能 分支限界法和回溯法實(shí)際上都屬于蠻力窮舉法。與回溯法不同的是，分支限界法首先擴(kuò)展解空間樹中的上層結(jié)點(diǎn)（廣度優(yōu)先），并采用限界函數(shù)，有利于實(shí)行大范圍剪枝，同時，根據(jù)限界函數(shù)不斷調(diào)整搜索方向，選擇最有可能取得最優(yōu)解的子樹優(yōu)先進(jìn)行搜索。關(guān)鍵點(diǎn)：結(jié)點(diǎn)的合理擴(kuò)展順序、好的限界函數(shù)9.1.3 分支限界法的時間性能 分支限界法和回溯法實(shí)際上分支限界法的較高效率

15、是以付出一定代價為基礎(chǔ)的，其工作方式也造成了算法設(shè)計的復(fù)雜性。首先，通常需要進(jìn)行大量實(shí)驗(yàn)確定限界函數(shù)其次，由于分支限界法對解空間樹中結(jié)點(diǎn)的處理是跳躍式的，因此，在搜索到某個葉子結(jié)點(diǎn)得到最優(yōu)值時，為了從該葉子結(jié)點(diǎn)求出對應(yīng)的最優(yōu)解中的各個分量，需要對每個擴(kuò)展結(jié)點(diǎn)保存該結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑，或者在搜索過程中構(gòu)建搜索經(jīng)過的樹結(jié)構(gòu)，這使得算法的設(shè)計較為復(fù)雜；再次，算法要維護(hù)一個待處理結(jié)點(diǎn)表PT，并且需要在表PT中快速查找取得極值的結(jié)點(diǎn)，等等。這都需要較大的存儲空間，在最壞情況下，分支限界法需要的空間復(fù)雜性是指數(shù)階。 分支限界法的較高效率是以付出一定代價為基礎(chǔ)的，其工作方式也造9.2 圖問題中的分支限界法

16、9.2.1 TSP問題 9.2.2 多段圖的最短路徑問題9.2 圖問題中的分支限界法 9.2.1 TSP問題 99.2.1 TSP問題 TSP問題是指旅行家要旅行n個城市，要求各個城市經(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 無向圖及其代價矩陣9.2.1 TSP問題 TSP問題是指旅行家要旅行n 采用貪心法求得近似解為135421，其路徑長度為1+2+3+7+3=16，這可以作為TSP問題的上界。 把矩陣中每一行

17、最小的元素相加，可以得到一個簡單的下界，其路徑長度為1+3+1+3+2=10，但是還有一個信息量更大的下界：考慮一個TSP問題的完整解，在每條路徑上，每個城市都有兩條鄰接邊，一條是進(jìn)入這個城市的，另一條是離開這個城市的，那么，如果把矩陣中每一行最小的兩個元素相加再除以2，如果圖中所有的代價都是整數(shù)，再對這個結(jié)果向上取整，就得到了一個合理的下界。 lb=(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14 于是，得到了目標(biāo)函數(shù)的界14, 16。需要強(qiáng)調(diào)的是，這個解并不是一個合法的選擇（可能沒有構(gòu)成哈密頓回路），它僅僅給出了一個參考下界。 采用貪心法求得近似解為135421部分解的

18、目標(biāo)函數(shù)值的計算方法 圖9.4所示無向圖，如果部分解包含邊(1, 4)，則該部分解的下界是lb=(1+5)+(3+6)+(1+2)+(3+5)+(2+3)/2=16。 部分解的目標(biāo)函數(shù)值的計算方法412lb=142356781startlb=1413lb=1414lb=1615lb=1923lb=1624lb=1625lb=1932lb=1634lb=1535lb=149101152lb=1954lb=14121342lb=161442lb=1845lb=15151652lb=2017分支限界法求解TSP問題示例4122356781start131415232應(yīng)用分支限界法求解圖9.4所示無向

19、圖的TSP問題，其搜索空間如圖9.5所示，具體的搜索過程如下（加黑表示該路徑上已經(jīng)確定的邊）：（1）在根結(jié)點(diǎn)1，根據(jù)限界函數(shù)計算目標(biāo)函數(shù)的值為lb=(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14；（2）在結(jié)點(diǎn)2，從城市1到城市2，路徑長度為3，目標(biāo)函數(shù)的值為(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14，將結(jié)點(diǎn)2加入待處理結(jié)點(diǎn)表PT中；在結(jié)點(diǎn)3，從城市1到城市3，路徑長度為1，目標(biāo)函數(shù)的值為(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14，將結(jié)點(diǎn)3加入表PT中；在結(jié)點(diǎn)4，從城市1到城市4，路徑長度為5，目標(biāo)函數(shù)的值為(1+5)+(

20、3+6)+(1+2)+(3+5)+(2+3)/2=16，將結(jié)點(diǎn)4加入表PT中；在結(jié)點(diǎn)5，從城市1到城市5，路徑長度為8，目標(biāo)函數(shù)的值為(1+8)+(3+6)+(1+2)+(3+4)+(2+8)/2=19，超出目標(biāo)函數(shù)的界，將結(jié)點(diǎn)5丟棄； 應(yīng)用分支限界法求解圖9.4所示無向圖的TSP問題，其搜索空間（3）在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)2優(yōu)先進(jìn)行搜索；（4）在結(jié)點(diǎn)6，從城市2到城市3，目標(biāo)函數(shù)值為(1+3)+(3+6)+(1+6)+(3+4)+(2+3)/2=16，將結(jié)點(diǎn)6加入表PT中；在結(jié)點(diǎn)7，從城市2到城市4，目標(biāo)函數(shù)值為(1+3)+(3+7)+(1+2)+(3+7)+(2+3)/2=16

21、，將結(jié)點(diǎn)7加入表PT中；在結(jié)點(diǎn)8，從城市2到城市5，目標(biāo)函數(shù)值為(1+3)+(3+9)+(1+2)+(3+4)+(2+9)/2=19，超出目標(biāo)函數(shù)的界，將結(jié)點(diǎn)8丟棄；（5）在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)3優(yōu)先進(jìn)行搜索；（6）在結(jié)點(diǎn)9，從城市3到城市2，目標(biāo)函數(shù)值為(1+3)+(3+6)+(1+6)+(3+4)+(2+3)/2=16，將結(jié)點(diǎn)9加入表PT中；在結(jié)點(diǎn)10，從城市3到城市4，目標(biāo)函數(shù)值為(1+3)+(3+6)+(1+4)+(3+4)+(2+3)/2=15，將結(jié)點(diǎn)10加入表PT中；在結(jié)點(diǎn)11，從城市3到城市5，目標(biāo)函數(shù)值為(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2

22、=14，將結(jié)點(diǎn)11加入表PT中；（3）在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)2優(yōu)先進(jìn)行搜索；（7）在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)11優(yōu)先進(jìn)行搜索；（8）在結(jié)點(diǎn)12，從城市5到城市2，目標(biāo)函數(shù)值為(1+3)+(3+9)+(1+2)+(3+4)+(2+9)/2=19，超出目標(biāo)函數(shù)的界，將結(jié)點(diǎn)12丟棄；在結(jié)點(diǎn)13，從城市5到城市4，目標(biāo)函數(shù)值為(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14，將結(jié)點(diǎn)13加入表PT中； （9）在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)13優(yōu)先進(jìn)行搜索；（10）在結(jié)點(diǎn)14，從城市4到城市2，目標(biāo)函數(shù)值為(1+3)+(3+7)+(1+2)+(3+7)+(2+3

23、)/2=16，最后從城市2回到城市1，目標(biāo)函數(shù)值為(1+3)+(3+7)+(1+2)+(3+7)+(2+3)/2=16，由于結(jié)點(diǎn)14為葉子結(jié)點(diǎn)，得到一個可行解，其路徑長度為16；（7）在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)11優(yōu)先進(jìn)行搜索；（11）在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)10優(yōu)先進(jìn)行搜索；（12）在結(jié)點(diǎn)15，從城市4到城市2，目標(biāo)函數(shù)的值為(1+3)+(3+7)+(1+4)+(7+4)+(2+3)/2=18，超出目標(biāo)函數(shù)的界，將結(jié)點(diǎn)15丟棄；在結(jié)點(diǎn)16，從城市4到城市5，目標(biāo)函數(shù)值為(1+3)+(3+6)+(1+4)+(3+4)+(2+3)/2=15，將結(jié)點(diǎn)16加入表PT中；（13）在表

24、PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)16優(yōu)先進(jìn)行搜索；（14）在結(jié)點(diǎn)17，從城市5到城市2，目標(biāo)函數(shù)的值為(1+3)+(3+9)+(1+4)+(3+4)+(9+3)/2=20，超出目標(biāo)函數(shù)的界，將結(jié)點(diǎn)17丟棄；（15）表PT中目標(biāo)函數(shù)值均為16，且有一個是葉子結(jié)點(diǎn)14，所以，結(jié)點(diǎn)14對應(yīng)的解135421即是TSP問題的最優(yōu)解，搜索過程結(jié)束。（11）在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)10優(yōu)先進(jìn)行搜索；(g) 擴(kuò)展結(jié)點(diǎn)16后的狀態(tài)，最優(yōu)解為135421圖9.6 TSP問題最優(yōu)解的確定(1, 2)14 (1, 3)14 (1, 4)16(a) 擴(kuò)展根結(jié)點(diǎn)后的狀態(tài) (b) 擴(kuò)展結(jié)點(diǎn)2后的狀態(tài)(c) 擴(kuò)展結(jié)點(diǎn)

25、3后的狀態(tài)(d) 擴(kuò)展結(jié)點(diǎn)11后的狀態(tài)(e) 擴(kuò)展結(jié)點(diǎn)13后的狀態(tài)(1, 3)14 (1, 4)16 (1, 2, 3)16 (1, 2, 4)16 (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

26、, 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 (1, 2, 3)16 (1, 2, 4)16 (1, 3, 2)16 (1, 3, 5, 4, 2)16 (1, 3, 4, 5)15(f) 擴(kuò)展結(jié)點(diǎn)10后的狀態(tài)(g) 擴(kuò)展結(jié)點(diǎn)16后的狀態(tài)，最優(yōu)解為135421算法9.1TSP問題 1根據(jù)限界函數(shù)計算目標(biāo)函數(shù)的下界down；采用貪心法得到上界up； 2將待處理結(jié)點(diǎn)表PT初始化為空； 3for (i=1; i=1) 5.1 i=k+1; 5.2 xi=1; 5.3 while (xi=n) 5.

27、3.1 如果路徑上頂點(diǎn)不重復(fù)，則 5.3.1.1 根據(jù)式9.2計算目標(biāo)函數(shù)值lb； 5.3.1.2 if (lb=+=+kijpiEvrijjjjvrcrrclbpi21,11min1段的最短邊第 對圖9.7所示多段圖應(yīng)用貪心法求得近似解為0 應(yīng)用分支限界法求解圖9.7所示多段圖的最短路徑問題，其搜索空間如圖9.8所示，具體的搜索過程如下（加黑表示該路徑上已經(jīng)確定的邊）：（1）在根結(jié)點(diǎn)1，根據(jù)限界函數(shù)計算目標(biāo)函數(shù)的值為18；（2）在結(jié)點(diǎn)2，第1段選擇邊，目標(biāo)函數(shù)值為lb=4+8+5+3=20，超出目標(biāo)函數(shù)的界，將結(jié)點(diǎn)2丟棄；在結(jié)點(diǎn)3，第1段選擇邊，目標(biāo)函數(shù)值為lb=2+6+5+3=16，將結(jié)點(diǎn)

28、3加入待處理結(jié)點(diǎn)表PT中；在結(jié)點(diǎn)4，第1段選擇邊，目標(biāo)函數(shù)值為lb=3+4+5+3=15，將結(jié)點(diǎn)4加入表PT中；（3）在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)4優(yōu)先進(jìn)行搜索； 應(yīng)用分支限界法求解圖9.7所示多段圖的最短路（4）在結(jié)點(diǎn)5，第2段選擇邊，目標(biāo)函數(shù)值為lb=3+4+6+3=16，將結(jié)點(diǎn)5加入表PT中；在結(jié)點(diǎn)6，第2段選擇邊，目標(biāo)函數(shù)值為lb=3+7+5+3=18，將結(jié)點(diǎn)6加入表PT中；（5）在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)3優(yōu)先進(jìn)行搜索；（6）在結(jié)點(diǎn)7，第2段選擇邊，目標(biāo)函數(shù)值為lb=2+6+5+3=16，將結(jié)點(diǎn)7加入表PT中；在結(jié)點(diǎn)8，第2段選擇邊，目標(biāo)函數(shù)值為lb=2+7+6+3=1

29、8，將結(jié)點(diǎn)8加入表PT中；在結(jié)點(diǎn)9，第2段選擇邊，目標(biāo)函數(shù)值為lb=2+8+5+3=18，將結(jié)點(diǎn)9加入表PT中；（4）在結(jié)點(diǎn)5，第2段選擇邊，目標(biāo)函數(shù)值為lb=（7）在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)5優(yōu)先進(jìn)行搜索；（8）在結(jié)點(diǎn)10，第3段選擇邊，可直接確定第4段的邊，目標(biāo)函數(shù)值為lb=3+4+8+7=22，為一個可行解但超出目標(biāo)函數(shù)的界，將其丟棄；在結(jié)點(diǎn)11，第3段選擇邊，可直接確定第4段的邊，目標(biāo)函數(shù)值為lb=3+4+6+3=16，為一個較好的可行解。由于結(jié)點(diǎn)11是葉子結(jié)點(diǎn)，并且其目標(biāo)函數(shù)值是表PT中最小的，所以，結(jié)點(diǎn)11代表的解即是問題的最優(yōu)解，搜索過程結(jié)束。（7）在表PT中選取目標(biāo)函數(shù)

30、值極小的結(jié)點(diǎn)5優(yōu)先進(jìn)行搜索；6401lb=20231startlb=1802lb=1603lb=15圖9.8 分支限界法求解多段圖的最短路徑問題示例(表示該結(jié)點(diǎn)被丟棄，結(jié)點(diǎn)上方的數(shù)組表示搜索順序)724lb=16825lb=18926lb=18535lb=1636lb=18111057lb=2258lb=166401231start0203圖9.8 分支限界 為了在搜索過程中構(gòu)建搜索經(jīng)過的樹結(jié)構(gòu)，設(shè)一個表ST，在表PT中取出最小值結(jié)點(diǎn)進(jìn)行擴(kuò)充時，將最小值結(jié)點(diǎn)存儲到表ST中，表PT和表ST的數(shù)據(jù)結(jié)構(gòu)為(第i段，lb)，在搜索過程中表PT和表ST的狀態(tài)如下：(b) 擴(kuò)展結(jié)點(diǎn)3后的狀態(tài)(d) 擴(kuò)展結(jié)

31、點(diǎn)5后的狀態(tài)，最優(yōu)解為03589圖9.9 多段圖的最短路徑問題最優(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,16)(1,15) (1,16) (2,16)(a) 擴(kuò)展根結(jié)點(diǎn)后的狀態(tài) PT ST ST PT (c) 擴(kuò)展結(jié)點(diǎn)4后的狀態(tài)ST ST 回溯過程是：(3,16)(2,16)(1,15)。 為了在搜索過程中構(gòu)建搜索經(jīng)過的樹結(jié)構(gòu)，設(shè)一個表ST，算法9.2多段圖的最短路徑問題 1根據(jù)

32、限界函數(shù)計算目標(biāo)函數(shù)的下界down；采用貪心法得到上界up； 2將待處理結(jié)點(diǎn)表PT初始化為空； 3for (i=1; i=1) 5.1 對頂點(diǎn)u的所有鄰接點(diǎn)v 5.1.1 根據(jù)式9.3計算目標(biāo)函數(shù)值lb; 5.1.2 若lb=up，則將i,lb存儲在表PT中； 5.2 如果i= =k-1且葉子結(jié)點(diǎn)的lb值在表PT中最小， 則輸出該葉子結(jié)點(diǎn)對應(yīng)的最優(yōu)解； 5.3 否則，如果i= =k-1且表PT中的葉子結(jié)點(diǎn)的lb值不是最小，則 5.3.1 up=表PT中的葉子結(jié)點(diǎn)最小的lb值; 5.3.2 將表PT中目標(biāo)函數(shù)值超出up的結(jié)點(diǎn)刪除； 5.4 u=表PT中l(wèi)b最小的結(jié)點(diǎn)的v值； 5.5 i=表PT中

33、lb最小的結(jié)點(diǎn)的i值；i+;偽代碼算法9.2多段圖的最短路徑問題偽代碼9.3 組合問題中的分支限界法 9.3.1 任務(wù)分配問題 9.3.2 批處理作業(yè)調(diào)度問題9.3 組合問題中的分支限界法 9.3.1 任務(wù)分配問題9.3.1 任務(wù)分配問題 任務(wù)分配問題要求把n項(xiàng)任務(wù)分配給n個人，每個人完成每項(xiàng)任務(wù)的成本不同，要求分配總成本最小的最優(yōu)分配方案。如圖9.10所示是一個任務(wù)分配的成本矩陣。 C9 2 7 86 4 3 75 8 1 87 6 9 4任務(wù)1 任務(wù)2 任務(wù)3 任務(wù)4人員a人員b人員c人員d圖9.10 任務(wù)分配問題的成本矩陣9.3.1 任務(wù)分配問題 任務(wù)分配問題要求把n項(xiàng)任務(wù)分配求最優(yōu)分配

34、成本的上界和下界考慮任意一個可行解，例如矩陣中的對角線是一個合法的選擇，表示將任務(wù)1分配給人員a、任務(wù)2分配給人員b、任務(wù)3分配給人員c、任務(wù)4分配給人員d，其成本是9+4+1+4=18；或者應(yīng)用貪心法求得一個近似解：將任務(wù)2分配給人員a、任務(wù)3分配給人員b、任務(wù)1分配給人員c、任務(wù)4分配給人員d，其成本是2+3+5+4=14。顯然，14是一個更好的上界。為了獲得下界，考慮人員a執(zhí)行所有任務(wù)的最小代價是2，人員b執(zhí)行所有任務(wù)的最小代價是3，人員c執(zhí)行所有任務(wù)的最小代價是1，人員d執(zhí)行所有任務(wù)的最小代價是4。因此，將每一行的最小元素加起來就得到解的下界，其成本是2+3+1+4=10。需要強(qiáng)調(diào)的是

35、，這個解并不是一個合法的選擇（3和1來自于矩陣的同一列），它僅僅給出了一個參考下界，這樣，最優(yōu)值一定是10, 14之間的某個值。求最優(yōu)分配成本的上界和下界設(shè)當(dāng)前已對人員1i分配了任務(wù)，并且獲得了成本v，則限界函數(shù)可以定義為： （式9.4） 設(shè)當(dāng)前已對人員1i分配了任務(wù)，并且獲得了成本v，則限界函數(shù)（2）在結(jié)點(diǎn)2，將任務(wù)1分配給人員a，獲得的成本為9，目標(biāo)函數(shù)值為9 + (3+1+4)=17，超出目標(biāo)函數(shù)的界10, 14，將結(jié)點(diǎn)2丟棄；在結(jié)點(diǎn)3，將任務(wù)2分配給人員a，獲得的成本為2，目標(biāo)函數(shù)值為2 + (3+1+4)=10，將結(jié)點(diǎn)3加入待處理結(jié)點(diǎn)表PT中；在結(jié)點(diǎn)4，將任務(wù)3分配給人員a，獲得的成

36、本為7，目標(biāo)函數(shù)值為7 + (3+1+4)=15，超出目標(biāo)函數(shù)的界10, 14，將結(jié)點(diǎn)4丟棄；在結(jié)點(diǎn)5，將任務(wù)4分配給人員a，獲得的成本為8，目標(biāo)函數(shù)值為8 + (3+1+4)=16，超出目標(biāo)函數(shù)的界10, 14，將結(jié)點(diǎn)5丟棄； 應(yīng)用分支限界法求解圖9.10所示任務(wù)分配問題，對解空間樹的搜索如圖9.11所示，具體的搜索過程如下：（1）在根結(jié)點(diǎn)1，沒有分配任務(wù)，根據(jù)限界函數(shù)估算目標(biāo)函數(shù)值為2+3+1+4=10； （2）在結(jié)點(diǎn)2，將任務(wù)1分配給人員a，獲得的成本為9，目標(biāo)函（3）在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)3優(yōu)先進(jìn)行搜索；（4）在結(jié)點(diǎn)6，將任務(wù)1分配給人員b，獲得的成本為2+6=8，目標(biāo)函數(shù)

37、值為8+(1+4)13，將結(jié)點(diǎn)6加入表PT中；在結(jié)點(diǎn)7，將任務(wù)3分配給人員b，獲得的成本為2+3=5，目標(biāo)函數(shù)值為5+(1+4)10，將結(jié)點(diǎn)7加入表PT中；在結(jié)點(diǎn)8，將任務(wù)4分配給人員b，獲得的成本為2+7=9，目標(biāo)函數(shù)值為9+(1+4)14，將結(jié)點(diǎn)8加入表PT中； （5）在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)7優(yōu)先進(jìn)行搜索；（6）在結(jié)點(diǎn)9，將任務(wù)1分配給人員c，獲得的成本為5+5=10，目標(biāo)函數(shù)值為10+4=14，將結(jié)點(diǎn)9加入表PT中；在結(jié)點(diǎn)10，將任務(wù)4分配給人員c，獲得的成本為5+8=13，目標(biāo)函數(shù)值為13+4=17，超出目標(biāo)函數(shù)的界10, 14，將結(jié)點(diǎn)10丟棄；（3）在表PT中選取目標(biāo)函數(shù)

38、值極小的結(jié)點(diǎn)3優(yōu)先進(jìn)行搜索；（7）在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)6優(yōu)先進(jìn)行搜索；（8）在結(jié)點(diǎn)11，將任務(wù)3分配給人員c，獲得的成本為8+1=9，目標(biāo)函數(shù)值為9+4=13，將結(jié)點(diǎn)11加入表PT中；在結(jié)點(diǎn)12，將任務(wù)4分配給人員c，獲得的成本為8+8=16，目標(biāo)函數(shù)值為16+4=20，超出目標(biāo)函數(shù)的界10, 14，將結(jié)點(diǎn)12丟棄；（9）在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)11優(yōu)先進(jìn)行搜索；（10）在結(jié)點(diǎn)13，將任務(wù)4分配給人員d，獲得的成本為9+4=13，目標(biāo)函數(shù)值為13，由于結(jié)點(diǎn)13是葉子結(jié)點(diǎn)，同時結(jié)點(diǎn)13的目標(biāo)函數(shù)值是表PT中的極小值，所以，結(jié)點(diǎn)13對應(yīng)的解即是問題的最優(yōu)解，搜索結(jié)束。（7）

39、在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)6優(yōu)先進(jìn)行搜索；4alb=16104startlb=101alb=172alb=103alb=151blb=133blb=104blb=141clb=144clb=174clb=173clb=134dlb=13圖9.11 分支限界法求解任務(wù)分配問題示例(表示該結(jié)點(diǎn)被丟棄，結(jié)點(diǎn)上方的數(shù)組表示搜索順序)235678912131114a104start1a2a3a1b3b4b為了在搜索過程中構(gòu)建搜索經(jīng)過的樹結(jié)構(gòu)，設(shè)一個表ST，在表PT中取出最小值結(jié)點(diǎn)進(jìn)行擴(kuò)充時，將最小值結(jié)點(diǎn)存儲到表ST中，表PT和表ST的數(shù)據(jù)結(jié)構(gòu)為(人員i-1分配的任務(wù),lb)(e) 擴(kuò)展結(jié)點(diǎn)11后

40、的狀態(tài)，最優(yōu)解為2a 1b 3c 4d圖9.12 任務(wù)分配問題最優(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,10) (2,13) (0,10) (2,10) (2,13) (1,13)(a) 擴(kuò)展根結(jié)點(diǎn)后的狀態(tài) (b) 擴(kuò)展結(jié)點(diǎn)3后的狀態(tài) PTSTPTST PT (c) 擴(kuò)展結(jié)點(diǎn)7后的狀態(tài) (d) 擴(kuò)展結(jié)點(diǎn)6后的狀態(tài)(2,14) (3,14) (3,13)PTSTPTST ST 回溯過程是：(3,13)(1,13)(2,13)(0,10)

41、 。為了在搜索過程中構(gòu)建搜索經(jīng)過的樹結(jié)構(gòu)，設(shè)一個表ST，在表PT算法9.3任務(wù)分配問題 1根據(jù)限界函數(shù)計算目標(biāo)函數(shù)的下界down；采用貪心法得到上界up； 2將待處理結(jié)點(diǎn)表PT初始化為空； 3for (i=1; i=1) 5.1 xk=1; 5.2 while (xk=n) 5.2.1 如果人員k分配任務(wù)xk不發(fā)生沖突，則 5.2.1.1 根據(jù)式9.4計算目標(biāo)函數(shù)值lb; 5.2.1.2 若lb=up，則將i,lb存儲在表PT中； 5.2.2 xk=xk+1; 5.3 如果k= =n且葉子結(jié)點(diǎn)的lb值在表PT中最小， 則輸出該葉子結(jié)點(diǎn)對應(yīng)的最優(yōu)解； 5.4 否則，如果k= =n且表PT中的葉子

42、結(jié)點(diǎn)的lb值不是最小，則 5.4.1 up=表PT中的葉子結(jié)點(diǎn)最小的lb值; 5.4.2 將表PT中超出目標(biāo)函數(shù)界的結(jié)點(diǎn)刪除； 5.5 i=表PT中l(wèi)b最小的結(jié)點(diǎn)的xk值； 5.6 k=表PT中l(wèi)b最小的結(jié)點(diǎn)的k值；k+;偽代碼算法9.3任務(wù)分配問題偽代碼9.3.2 批處理作業(yè)調(diào)度問題 給定n個作業(yè)的集合J=J1, J2, , Jn，每個作業(yè)都有3項(xiàng)任務(wù)分別在3臺機(jī)器上完成，作業(yè)Ji需要機(jī)器j的處理時間為tij（1in, 1j3），每個作業(yè)必須先由機(jī)器1處理，再由機(jī)器2處理，最后由機(jī)器3處理。批處理作業(yè)調(diào)度問題要求確定這n個作業(yè)的最優(yōu)處理順序，使得從第1個作業(yè)在機(jī)器1上處理開始，到最后一個作業(yè)

43、在機(jī)器3上處理結(jié)束所需的時間最少。 顯然，批處理作業(yè)的一個最優(yōu)調(diào)度應(yīng)使機(jī)器1沒有空閑時間，且機(jī)器2和機(jī)器3的空閑時間最小?？梢宰C明，存在一個最優(yōu)作業(yè)調(diào)度使得在機(jī)器1、機(jī)器2和機(jī)器3上作業(yè)以相同次序完成。 9.3.2 批處理作業(yè)調(diào)度問題 給定n個作業(yè)T 5 7 910 5 2 9 9 5 7 8 10J1J2J3J4機(jī)器1 機(jī)器2 機(jī)器3 若處理順序?yàn)?J2, J3, J1, J4)，則從作業(yè)2在機(jī)器1處理開始到作業(yè)4在機(jī)器3處理完成的調(diào)度方案如圖9.14所示。 J2:10 J3:9 J1:5 J4:7機(jī)器1機(jī)器2機(jī)器3 圖9.14 批處理調(diào)度問題的調(diào)度方案空閑:10 J2:5 J3:9 J1:

44、7 J4:8空閑:15 J2:2 J3:5 J1:9 J4:10 設(shè)J=J1, J2, J3, J4是4個待處理的作業(yè)，每個作業(yè)的處理順序相同，即先在機(jī)器1上處理，然后在機(jī)器2上處理，最后在機(jī)器3上處理，需要的處理時間如圖9.13所示。5 7 9J1機(jī)器1 機(jī)器2 一般情況下，對于一個已安排的作業(yè)集合M 1, 2, , n，|M|=k，即已安排了k個作業(yè)，設(shè)sum1k表示機(jī)器1完成k個作業(yè)的處理時間，sum2k表示機(jī)器2完成k個作業(yè)的處理時間，現(xiàn)在要處理作業(yè)k+1，此時，該部分解的目標(biāo)函數(shù)值的下界計算方法如下：（1）sum1k+1=sum1k+ tk1（2）（3）sum2k+1=maxsum1k+1, sum2k + tk2 批處理作業(yè)調(diào)度問題的限界函數(shù)考慮理想情況，機(jī)器1和機(jī)器2無空閑，最后處理的恰好是在機(jī)器3上處理時間最短的作業(yè)。例如，以作業(yè)Ji