分支限界法課件

1、分支限界法分支限界法分支限界法的基本思想分支限界法在各種問(wèn)題中的應(yīng)用分支限界法的基本思想 分支限界法首先確定一個(gè)合理的限界函數(shù)，并根據(jù)限界函數(shù)確定目標(biāo)函數(shù)的界down, up 。然后，按照廣度優(yōu)先策略遍歷問(wèn)題的解空間樹(shù)，在分支結(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ù)上述過(guò)程，直到找到最優(yōu)解。9.1 概述9.1.1 解空間樹(shù)的動(dòng)態(tài)搜索（2） 分支限界法首先確定一個(gè)合理的限界函數(shù)，并根據(jù)

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

3、排序：物品重量(w)價(jià)值(v)價(jià)值/重量(v/w)144010274263525543124 例：0/1背包問(wèn)題。假設(shè)有4個(gè)物品，其重量分別（1）應(yīng)用貪心法求得近似解為(1, 0, 0, 0)，獲得的價(jià)值為40-作為0/1背包問(wèn)題的下界。（2）0/1背包問(wèn)題的上界：最好情況下，背包中裝入的全部是第1個(gè)物品且可以將背包裝滿(mǎn)，則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ú)效解w=4, v=40ub=7

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

5、，背包的重量和獲得的價(jià)值仍為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背包問(wèn)題，其搜索空間如圖（4）在結(jié)點(diǎn)4，將物品2裝入背包，因此，背包的重量為11，不滿(mǎn)足約束條件，將結(jié)點(diǎn)4丟棄；在結(jié)點(diǎn)5，沒(méi)有將物品2裝入背包，因此，背包的重量和獲得的價(jià)值與結(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，獲得的價(jià)值為65，目標(biāo)函數(shù)值為65 + (10-9)4=69，將結(jié)點(diǎn)6加

6、入表PT中；在結(jié)點(diǎn)7，沒(méi)有將物品3裝入背包，因此，背包的重量和獲得的價(jià)值與結(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，不滿(mǎn)足約束條件，將結(jié)點(diǎn)8丟棄；在結(jié)點(diǎn)9，沒(méi)有將物品4裝入背包，因此，背包的重量和獲得的價(jià)值與結(jié)點(diǎn)6相同，目標(biāo)函數(shù)值為65；（9）由于結(jié)點(diǎn)9是葉子結(jié)點(diǎn)，同時(shí)結(jié)點(diǎn)9的目標(biāo)函數(shù)值是表PT中的極大值，所以，結(jié)點(diǎn)9對(duì)應(yīng)的解即是問(wèn)題的最優(yōu)解，搜索結(jié)束。（7）在表PT中選取目標(biāo)函數(shù)值取

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

8、, , xk) bound(x1, x2, , xn)9.1.2 分支限界法的設(shè)計(jì)思想 假設(shè)求解最大化問(wèn)題，解向若某孩子結(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ù)上述過(guò)程，當(dāng)?shù)竭_(dá)一個(gè)葉子結(jié)點(diǎn)時(shí)，就得到了一個(gè)可行解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)就是所求問(wèn)題的最大值，(x1, x2, , xn)就是問(wèn)題的最

9、優(yōu)解；如果bound(x1, x2, , xn)不是表PT中目標(biāo)函數(shù)值最大的結(jié)點(diǎn)，說(shuō)明還存在某個(gè)部分解對(duì)應(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ù)搜索，直到某個(gè)葉子結(jié)點(diǎn)的目標(biāo)函數(shù)值在表PT中最大。 若某孩子結(jié)點(diǎn)的目標(biāo)函數(shù)值超出目標(biāo)函數(shù)的界，則將該孩子結(jié)點(diǎn)丟棄分支限界法求解最大化問(wèn)題的一般過(guò)程分支限界法的一般過(guò)程1根據(jù)限界函數(shù)確定目標(biāo)函數(shù)的界down,

10、 up；2將待處理結(jié)點(diǎn)表PT初始化為空；3對(duì)根結(jié)點(diǎn)的每個(gè)孩子結(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)直到某個(gè)葉子結(jié)點(diǎn)的目標(biāo)函數(shù)值在表PT中最大 4.1 i=表PT中值最大的結(jié)點(diǎn)； 4.2 對(duì)結(jié)點(diǎn)i的每個(gè)孩子結(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對(duì)應(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)刪除；分支限界法求解最大化問(wèn)題的一般過(guò)程分支限界法的一般過(guò)程應(yīng)用分支限界法的關(guān)鍵問(wèn)題（1）確定合適的限界函數(shù)（2）組織待處理結(jié)點(diǎn)表PT（3）確定最優(yōu)解中的各個(gè)分量 應(yīng)用分支限界法的關(guān)鍵問(wèn)題分支限界法對(duì)問(wèn)題的解空間樹(shù)中結(jié)點(diǎn)的處理是跳躍式的，回溯也不是單純地沿著雙親結(jié)點(diǎn)一層一層向上回溯。當(dāng)搜索到某個(gè)葉子結(jié)點(diǎn)且該葉子結(jié)點(diǎn)的目標(biāo)函數(shù)值在表PT中最大時(shí)（假設(shè)求解最大化問(wèn)題），求得了問(wèn)題的最優(yōu)值。但是，卻無(wú)法求得該葉子結(jié)點(diǎn)對(duì)應(yīng)的最優(yōu)解中的各個(gè)分量。這個(gè)問(wèn)題可以用如下2種方法解決： 對(duì)每個(gè)擴(kuò)展結(jié)點(diǎn)保存該結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑； 在

12、搜索過(guò)程中構(gòu)建搜索經(jīng)過(guò)的樹(shù)結(jié)構(gòu)，在求得最優(yōu)解時(shí)，從葉子結(jié)點(diǎn)不斷回溯到根結(jié)點(diǎn)，以確定最優(yōu)解中的各個(gè)分量。 分支限界法對(duì)問(wèn)題的解空間樹(shù)中結(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背包問(wèn)題最優(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背包問(wèn)題，為了對(duì)每個(gè)擴(kuò)展結(jié)點(diǎn)保存該結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑，將部

13、分解(x1, , xi)和該部分解的目標(biāo)函數(shù)值都存儲(chǔ)在待處理結(jié)點(diǎn)表PT中，在搜索過(guò)程中表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背包問(wèn)題最優(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背包問(wèn)題，為了在搜索過(guò)程中構(gòu)建搜索

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

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

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

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

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

19、圖的TSP問(wèn)題，其搜索空間如圖9.5所示，具體的搜索過(guò)程如下（加黑表示該路徑上已經(jīng)確定的邊）：（1）在根結(jié)點(diǎn)1，根據(jù)限界函數(shù)計(jì)算目標(biāo)函數(shù)的值為lb=(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14；（2）在結(jié)點(diǎn)2，從城市1到城市2，路徑長(zhǎng)度為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，路徑長(zhǎng)度為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，路徑長(zhǎng)度為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，路徑長(zhǎng)度為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所示無(wú)向圖的TSP問(wèn)題，其搜索空間（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)，得到一個(gè)可行解，其路徑長(zhǎng)度為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，且有一個(gè)是葉子結(jié)點(diǎn)14，所以，結(jié)點(diǎn)14對(duì)應(yīng)的解135421即是TSP問(wèn)題的最優(yōu)解，搜索過(guò)程結(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問(wèn)題最優(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問(wèn)題 1根據(jù)限界函數(shù)計(jì)算目標(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計(jì)算目標(biāo)函數(shù)值lb； 5.3.1.2 if (lb=+=+kijpiEvrijjjjvrcrrclbpi21,11min1段的最短邊第 對(duì)圖9.7所示多段圖應(yīng)用貪心法求得近似解為0 應(yīng)用分支限界法求解圖9.7所示多段圖的最短路徑問(wèn)題，其搜索空間如圖9.8所示，具體的搜索過(guò)程如下（加黑表示該路徑上已經(jīng)確定的邊）：（1）在根結(jié)點(diǎn)1，根據(jù)限界函數(shù)計(jì)算目標(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，為一個(gè)可行解但超出目標(biāo)函數(shù)的界，將其丟棄；在結(jié)點(diǎn)11，第3段選擇邊，可直接確定第4段的邊，目標(biāo)函數(shù)值為lb=3+4+6+3=16，為一個(gè)較好的可行解。由于結(jié)點(diǎn)11是葉子結(jié)點(diǎn)，并且其目標(biāo)函數(shù)值是表PT中最小的，所以，結(jié)點(diǎn)11代表的解即是問(wèn)題的最優(yōu)解，搜索過(guò)程結(jié)束。（7）在表PT中選取目標(biāo)函數(shù)

30、值極小的結(jié)點(diǎn)5優(yōu)先進(jìn)行搜索；6401lb=20231startlb=1802lb=1603lb=15圖9.8 分支限界法求解多段圖的最短路徑問(wèn)題示例(表示該結(jié)點(diǎn)被丟棄，結(jié)點(diǎn)上方的數(shù)組表示搜索順序)724lb=16825lb=18926lb=18535lb=1636lb=18111057lb=2258lb=166401231start0203圖9.8 分支限界 為了在搜索過(guò)程中構(gòu)建搜索經(jīng)過(guò)的樹(shù)結(jié)構(gòu)，設(shè)一個(gè)表ST，在表PT中取出最小值結(jié)點(diǎn)進(jìn)行擴(kuò)充時(shí)，將最小值結(jié)點(diǎn)存儲(chǔ)到表ST中，表PT和表ST的數(shù)據(jù)結(jié)構(gòu)為(第i段，lb)，在搜索過(guò)程中表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 多段圖的最短路徑問(wèn)題最優(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 回溯過(guò)程是：(3,16)(2,16)(1,15)。 為了在搜索過(guò)程中構(gòu)建搜索經(jīng)過(guò)的樹(shù)結(jié)構(gòu)，設(shè)一個(gè)表ST，算法9.2多段圖的最短路徑問(wèn)題 1根據(jù)

32、限界函數(shù)計(jì)算目標(biāo)函數(shù)的下界down；采用貪心法得到上界up； 2將待處理結(jié)點(diǎn)表PT初始化為空； 3for (i=1; i=1) 5.1 對(duì)頂點(diǎn)u的所有鄰接點(diǎn)v 5.1.1 根據(jù)式9.3計(jì)算目標(biāo)函數(shù)值lb; 5.1.2 若lb=up，則將i,lb存儲(chǔ)在表PT中； 5.2 如果i= =k-1且葉子結(jié)點(diǎn)的lb值在表PT中最小， 則輸出該葉子結(jié)點(diǎn)對(duì)應(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多段圖的最短路徑問(wèn)題偽代碼9.3 組合問(wèn)題中的分支限界法 9.3.1 任務(wù)分配問(wèn)題 9.3.2 批處理作業(yè)調(diào)度問(wèn)題9.3 組合問(wèn)題中的分支限界法 9.3.1 任務(wù)分配問(wèn)題9.3.1 任務(wù)分配問(wèn)題 任務(wù)分配問(wèn)題要求把n項(xiàng)任務(wù)分配給n個(gè)人，每個(gè)人完成每項(xiàng)任務(wù)的成本不同，要求分配總成本最小的最優(yōu)分配方案。如圖9.10所示是一個(gè)任務(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ù)分配問(wèn)題的成本矩陣9.3.1 任務(wù)分配問(wèn)題 任務(wù)分配問(wèn)題要求把n項(xiàng)任務(wù)分配求最優(yōu)分配

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

35、，這個(gè)解并不是一個(gè)合法的選擇（3和1來(lái)自于矩陣的同一列），它僅僅給出了一個(gè)參考下界，這樣，最優(yōu)值一定是10, 14之間的某個(gè)值。求最優(yōu)分配成本的上界和下界設(shè)當(dāng)前已對(duì)人員1i分配了任務(wù)，并且獲得了成本v，則限界函數(shù)可以定義為： （式9.4） 設(shè)當(dāng)前已對(duì)人員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ù)分配問(wèn)題，對(duì)解空間樹(shù)的搜索如圖9.11所示，具體的搜索過(guò)程如下：（1）在根結(jié)點(diǎn)1，沒(méi)有分配任務(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)，同時(shí)結(jié)點(diǎn)13的目標(biāo)函數(shù)值是表PT中的極小值，所以，結(jié)點(diǎn)13對(duì)應(yīng)的解即是問(wèn)題的最優(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ù)分配問(wèn)題示例(表示該結(jié)點(diǎn)被丟棄，結(jié)點(diǎn)上方的數(shù)組表示搜索順序)235678912131114a104start1a2a3a1b3b4b為了在搜索過(guò)程中構(gòu)建搜索經(jīng)過(guò)的樹(shù)結(jié)構(gòu)，設(shè)一個(gè)表ST，在表PT中取出最小值結(jié)點(diǎn)進(jìn)行擴(kuò)充時(shí)，將最小值結(jié)點(diǎn)存儲(chǔ)到表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ù)分配問(wèn)題最優(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 回溯過(guò)程是：(3,13)(1,13)(2,13)(0,10)

41、 。為了在搜索過(guò)程中構(gòu)建搜索經(jīng)過(guò)的樹(shù)結(jié)構(gòu)，設(shè)一個(gè)表ST，在表PT算法9.3任務(wù)分配問(wèn)題 1根據(jù)限界函數(shù)計(jì)算目標(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計(jì)算目標(biāo)函數(shù)值lb; 5.2.1.2 若lb=up，則將i,lb存儲(chǔ)在表PT中； 5.2.2 xk=xk+1; 5.3 如果k= =n且葉子結(jié)點(diǎn)的lb值在表PT中最小， 則輸出該葉子結(jié)點(diǎn)對(duì)應(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ù)分配問(wèn)題偽代碼9.3.2 批處理作業(yè)調(diào)度問(wèn)題 給定n個(gè)作業(yè)的集合J=J1, J2, , Jn，每個(gè)作業(yè)都有3項(xiàng)任務(wù)分別在3臺(tái)機(jī)器上完成，作業(yè)Ji需要機(jī)器j的處理時(shí)間為tij（1in, 1j3），每個(gè)作業(yè)必須先由機(jī)器1處理，再由機(jī)器2處理，最后由機(jī)器3處理。批處理作業(yè)調(diào)度問(wèn)題要求確定這n個(gè)作業(yè)的最優(yōu)處理順序，使得從第1個(gè)作業(yè)在機(jī)器1上處理開(kāi)始，到最后一個(gè)作業(yè)

43、在機(jī)器3上處理結(jié)束所需的時(shí)間最少。 顯然，批處理作業(yè)的一個(gè)最優(yōu)調(diào)度應(yīng)使機(jī)器1沒(méi)有空閑時(shí)間，且機(jī)器2和機(jī)器3的空閑時(shí)間最小?？梢宰C明，存在一個(gè)最優(yōu)作業(yè)調(diào)度使得在機(jī)器1、機(jī)器2和機(jī)器3上作業(yè)以相同次序完成。 9.3.2 批處理作業(yè)調(diào)度問(wèn)題 給定n個(gè)作業(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處理開(kāi)始到作業(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)度問(wèn)題的調(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個(gè)待處理的作業(yè)，每個(gè)作業(yè)的處理順序相同，即先在機(jī)器1上處理，然后在機(jī)器2上處理，最后在機(jī)器3上處理，需要的處理時(shí)間如圖9.13所示。5 7 9J1機(jī)器1 機(jī)器2 一般情況下，對(duì)于一個(gè)已安排的作業(yè)集合M 1, 2, , n，|M|=k，即已安排了k個(gè)作業(yè)，設(shè)sum1k表示機(jī)器1完成k個(gè)作業(yè)的處理時(shí)間，sum2k表示機(jī)器2完成k個(gè)作業(yè)的處理時(shí)間，現(xiàn)在要處理作業(yè)k+1，此時(shí)，該部分解的目標(biāo)函數(shù)值的下界計(jì)算方法如下：（1）sum1k+1=sum1k+ tk1（2）（3）sum2k+1=maxsum1k+1, sum2k + tk2 批處理作業(yè)調(diào)度問(wèn)題的限界函數(shù)考慮理想情況，機(jī)器1和機(jī)器2無(wú)空閑，最后處理的恰好是在機(jī)器3上處理時(shí)間最短的作業(yè)。例如，以作業(yè)Ji