分支限界法 (1)

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

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

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

4、題，是極大值），則該葉子結(jié)題，是極小值；對(duì)于最大化問(wèn)題，是極大值），則該葉子結(jié)點(diǎn)對(duì)應(yīng)的解就是問(wèn)題的最優(yōu)解；否則，根據(jù)這個(gè)葉子結(jié)點(diǎn)調(diào)點(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ì)于最大化整目標(biāo)函數(shù)的界（對(duì)于最小化問(wèn)題，調(diào)整上界；對(duì)于最大化問(wèn)題，調(diào)整下界），依次考察表問(wèn)題，調(diào)整下界），依次考察表PT中的結(jié)點(diǎn)，將超出目標(biāo)函中的結(jié)點(diǎn)，將超出目標(biāo)函數(shù)界的結(jié)點(diǎn)丟棄，然后從表數(shù)界的結(jié)點(diǎn)丟棄，然后從表PT中選取使目標(biāo)函數(shù)取得極值的中選取使目標(biāo)函數(shù)取得極值的結(jié)點(diǎn)繼續(xù)進(jìn)行擴(kuò)展。結(jié)點(diǎn)繼續(xù)進(jìn)行擴(kuò)展。來(lái)源：http:/ 例：例：0/1背包問(wèn)題。假設(shè)有背包問(wèn)題。假設(shè)有4個(gè)

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

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

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

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

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

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

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

12、標(biāo)函數(shù)取得極大值的結(jié)點(diǎn)作為下一次擴(kuò)展的根結(jié)點(diǎn)，重復(fù)上述過(guò)程，當(dāng)?shù)竭_(dá)一個(gè)葉子結(jié)點(diǎn)一次擴(kuò)展的根結(jié)點(diǎn)，重復(fù)上述過(guò)程，當(dāng)?shù)竭_(dá)一個(gè)葉子結(jié)點(diǎn)時(shí)，就得到了一個(gè)可行解時(shí)，就得到了一個(gè)可行解X=(x1, x2, , xn)及其目標(biāo)函數(shù)值及其目標(biāo)函數(shù)值bound(x1, x2, , xn)。 如果如果bound(x1, x2, , xn)是表是表PT中目標(biāo)函數(shù)值最大的結(jié)點(diǎn)，中目標(biāo)函數(shù)值最大的結(jié)點(diǎn)，則則bound(x1, x2, , xn)就是所求問(wèn)題的最大值，就是所求問(wèn)題的最大值，(x1, x2, , xn)就是問(wèn)題的最優(yōu)解；就是問(wèn)題的最優(yōu)解； 如果如果bound(x1, x2, , xn)不是表不是表PT中目標(biāo)

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

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

15、目標(biāo)函數(shù)值value; 4.2.2 若若(value=down)，則將結(jié)點(diǎn)，則將結(jié)點(diǎn)x加入表加入表PT中；中； 4.2.3 若若(結(jié)點(diǎn)結(jié)點(diǎn)x是葉子結(jié)點(diǎn)且結(jié)點(diǎn)是葉子結(jié)點(diǎn)且結(jié)點(diǎn)x的的value值在表值在表PT中最大中最大)， 則將結(jié)點(diǎn)則將結(jié)點(diǎn)x對(duì)應(yīng)的解輸出，算法結(jié)束；對(duì)應(yīng)的解輸出，算法結(jié)束； 4.2.4 若若(結(jié)點(diǎn)結(jié)點(diǎn)x是葉子結(jié)點(diǎn)但結(jié)點(diǎn)是葉子結(jié)點(diǎn)但結(jié)點(diǎn)x的的value值在表值在表PT中不是最大中不是最大)， 則令則令down=value，并且將表，并且將表PT中所有小于中所有小于value的結(jié)點(diǎn)刪除；的結(jié)點(diǎn)刪除；來(lái)源：http:/ 來(lái)源：http:/ 對(duì)每個(gè)擴(kuò)展結(jié)點(diǎn)保存該結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑；對(duì)每個(gè)

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

17、問(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é)背包問(wèn)題，為了對(duì)每個(gè)擴(kuò)展結(jié)點(diǎn)保存該結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑，將部分解點(diǎn)到根結(jié)點(diǎn)的路徑，將部分解(x1, , xi)和該部分解的目標(biāo)和該部分解的目標(biāo)函數(shù)值都存儲(chǔ)在待處理結(jié)點(diǎn)表函數(shù)值都存儲(chǔ)在待處理結(jié)點(diǎn)表PT中，在搜索過(guò)程中表中，在搜索過(guò)程中表PT的狀態(tài)如圖的狀態(tài)如圖9.2所示。所示。來(lái)源：http:/ 擴(kuò)展根結(jié)點(diǎn)后擴(kuò)展根結(jié)點(diǎn)后 (b) 擴(kuò)展結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)2后后(c) 擴(kuò)展結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)5后后 (d) 擴(kuò)展結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)6后，最

18、優(yōu)解為后，最優(yōu)解為(1,0,1,0)65 圖圖9.3 方法確定方法確定0/1背包問(wèn)題最優(yōu)解的各分量背包問(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)建搜索經(jīng)過(guò)的背包問(wèn)題，為了在搜索過(guò)程中構(gòu)建搜索經(jīng)過(guò)的樹(shù)結(jié)構(gòu)，設(shè)一個(gè)表樹(shù)結(jié)構(gòu)，設(shè)一個(gè)表ST，在表，在表PT中取出最小值結(jié)點(diǎn)進(jìn)行擴(kuò)充中取出最小值結(jié)點(diǎn)進(jìn)行擴(kuò)充時(shí)，將最小值結(jié)點(diǎn)存儲(chǔ)到表時(shí)，將最小

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

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

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

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

23、/ 圖問(wèn)題中的分支限界法圖問(wèn)題中的分支限界法 9.2.1 TSP問(wèn)題問(wèn)題 9.2.2 多段圖的最短路徑問(wèn)題多段圖的最短路徑問(wèn)題來(lái)源：http:/ TSP問(wèn)題問(wèn)題 TSP TSP問(wèn)題是指旅行家要旅行問(wèn)題是指旅行家要旅行n n個(gè)城市，要求各個(gè)城個(gè)城市，要求各個(gè)城市經(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) 一個(gè)無(wú)向圖一個(gè)無(wú)向圖 (b) 無(wú)向圖的代價(jià)矩陣無(wú)向圖的代價(jià)矩陣圖圖9.4 無(wú)向圖及其代價(jià)矩陣無(wú)向圖及其

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

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

26、考下界。 來(lái)源：http:/ 例如圖例如圖9.4所示無(wú)向圖，如果部分解包含邊所示無(wú)向圖，如果部分解包含邊(1, 4)，則該部分，則該部分解的下界是解的下界是lb=(1+5)+(3+6)+(1+2)+(3+5)+(2+3)/2=16。 UrUrjikiiiijrrrrclb2/ )2(111行最小的兩個(gè)元素素行不在路徑上的最小元來(lái)源：http:/ 來(lái)源：http:/ （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)/2=16，最后從城市2回到城市1，目標(biāo)函數(shù)值為(1+3)+(3+

27、7)+(1+2)+(3+7)+(2+3)/2=16，由于結(jié)點(diǎn)14為葉子結(jié)點(diǎn)，得到一個(gè)可行解，其路徑長(zhǎng)度為16；來(lái)源：http:/ 擴(kuò)展結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)16后的狀態(tài)，最優(yōu)解為后的狀態(tài)，最優(yōu)解為135421圖圖9.6 TSP問(wèn)題最優(yōu)解的確定問(wèn)題最優(yōu)解的確定(1, 2)14 (1, 3)14 (1, 4)16(a) 擴(kuò)展根結(jié)點(diǎn)后的狀態(tài)擴(kuò)展根結(jié)點(diǎn)后的狀態(tài) (b) 擴(kuò)展結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)2后的狀態(tài)后的狀態(tài)(c) 擴(kuò)展結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)3后的狀態(tài)后的狀態(tài)(d) 擴(kuò)展結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)11后的狀態(tài)后的狀態(tài)(e) 擴(kuò)展結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)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) 擴(kuò)展結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)10后的狀態(tài)后的狀態(tài)來(lái)源：http:/ 1根據(jù)限界函數(shù)計(jì)算目標(biāo)函數(shù)的下界根據(jù)限界函數(shù)計(jì)算目標(biāo)函數(shù)的下界down；采用貪心法得到上界；采用貪心法得到上界up； 2將待處理結(jié)點(diǎn)表將待處理結(jié)點(diǎn)表PT初始化為空；初始化為空； 3for (i=1; i=1) 5.1 i=k+1; 5.2 xi=1; 5.3 while (xi=n) 5.3.1 如果路徑上頂點(diǎn)不重復(fù)，則如果路徑上頂點(diǎn)不重復(fù)，則 根據(jù)式根據(jù)式9.2計(jì)算目標(biāo)函數(shù)值計(jì)

30、算目標(biāo)函數(shù)值lb； if (lb kijpiEvrijjjjvrcrrclbpi21,11min1段的最短邊段的最短邊第第來(lái)源：http:/ 應(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)3加入待處理結(jié)點(diǎn)表PT中；在結(jié)點(diǎn)4，第1段選擇邊，目標(biāo)函數(shù)值為lb=3+4+5+3=1

31、5，將結(jié)點(diǎn)4加入表PT中；（3）在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)4優(yōu)先進(jìn)行搜索；來(lái)源：http:/ 分支限界法求解多段圖的最短路徑問(wèn)題示例分支限界法求解多段圖的最短路徑問(wèn)題示例(表示該結(jié)點(diǎn)被丟棄，結(jié)點(diǎn)上方的數(shù)組表示搜索順序表示該結(jié)點(diǎn)被丟棄，結(jié)點(diǎn)上方的數(shù)組表示搜索順序)724lb=16825lb=18926lb=18535lb=1636lb=181110 57lb=2258lb=16來(lái)源：http:/ 為了在搜索過(guò)程中構(gòu)建搜索經(jīng)過(guò)的樹(shù)結(jié)構(gòu)，設(shè)一個(gè)表為了在搜索過(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ǔ)到表中取出最小值結(jié)點(diǎn)進(jìn)行擴(kuò)充時(shí)，將最小值

32、結(jié)點(diǎn)存儲(chǔ)到表ST中，表中，表PT和表和表ST的數(shù)據(jù)結(jié)構(gòu)為的數(shù)據(jù)結(jié)構(gòu)為(第第i段，段，lb)，在搜索過(guò)程中表，在搜索過(guò)程中表PT和表和表ST的狀態(tài)如下：的狀態(tài)如下：(b) 擴(kuò)展結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)3后的狀態(tài)后的狀態(tài)(d) 擴(kuò)展結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)5后的狀態(tài)，最優(yōu)解為后的狀態(tài)，最優(yōu)解為03589圖圖9.9 多段圖的最短路徑問(wèn)題最優(yōu)解的確定多段圖的最短路徑問(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,

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

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

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

36、務(wù)任務(wù)3 任務(wù)任務(wù)4人員人員a人員人員b人員人員c人員人員d圖圖9.10 任務(wù)分配問(wèn)題的成本矩陣任務(wù)分配問(wèn)題的成本矩陣來(lái)源：http:/ 14之間的某個(gè)值。之間的某個(gè)值。來(lái)源：http:/ （式（式9.4） nikkvlb1行的最小值第來(lái)源：http:/ + (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，獲得的成本為7，目標(biāo)函數(shù)值為7 + (3+1+4)=15，超出目標(biāo)函數(shù)的界10, 14，將結(jié)點(diǎn)4丟棄；在結(jié)點(diǎn)5，將任務(wù)4

37、分配給人員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； 來(lái)源：http:/ （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

38、, 14，將結(jié)點(diǎn)10丟棄；來(lái)源：http:/ 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é)束。來(lái)源：http:/ 分支限界法求解任務(wù)分配問(wèn)題示例分支限界法求解任務(wù)分配問(wèn)題示例(表示該結(jié)點(diǎn)被丟棄，結(jié)點(diǎn)上方的數(shù)組表示搜索順序表示該結(jié)點(diǎn)被丟棄，結(jié)點(diǎn)上方的數(shù)組表示搜索順序)23567891213111來(lái)源：http:/ 為了在搜索過(guò)程中構(gòu)建搜索經(jīng)過(guò)的樹(shù)結(jié)構(gòu)，設(shè)一個(gè)表為了

39、在搜索過(guò)程中構(gòu)建搜索經(jīng)過(guò)的樹(shù)結(jié)構(gòu)，設(shè)一個(gè)表ST，在表，在表PT中取出最小值結(jié)點(diǎn)進(jìn)行擴(kuò)充時(shí)，將最小值結(jié)點(diǎn)中取出最小值結(jié)點(diǎn)進(jìn)行擴(kuò)充時(shí)，將最小值結(jié)點(diǎn)存儲(chǔ)到表存儲(chǔ)到表ST中，表中，表PT和表和表ST的數(shù)據(jù)結(jié)構(gòu)為的數(shù)據(jù)結(jié)構(gòu)為(人員人員i- -1分配的分配的任務(wù)任務(wù),lb)(e) 擴(kuò)展結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)11后的狀態(tài)，最優(yōu)解為后的狀態(tài)，最優(yōu)解為2a 1b 3c 4d圖圖9.12 任務(wù)分配問(wèn)題最優(yōu)解的確定任務(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

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

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

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

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

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