算法設(shè)計(jì)及分析 王紅梅 第二版 第9章 分支限界法

1、教學(xué)重點(diǎn)教學(xué)重點(diǎn)分支限界法的設(shè)計(jì)思想，各種經(jīng)典問題的限界函數(shù)分支限界法的設(shè)計(jì)思想，各種經(jīng)典問題的限界函數(shù)教學(xué)難點(diǎn)教學(xué)難點(diǎn)各種經(jīng)典問題的限界函數(shù)以及限界算法各種經(jīng)典問題的限界函數(shù)以及限界算法教學(xué)內(nèi)容及目教學(xué)內(nèi)容及目標(biāo)標(biāo)知識點(diǎn)知識點(diǎn)教學(xué)要求教學(xué)要求了解了解理解理解掌握掌握熟練掌握熟練掌握分支限界法的設(shè)計(jì)思想分支限界法的設(shè)計(jì)思想分支限界法的時(shí)空性能分支限界法的時(shí)空性能TSP問題問題多段圖的最短路徑問題多段圖的最短路徑問題0/1背包問題背包問題任務(wù)分配問題任務(wù)分配問題批處理作業(yè)調(diào)度問題批處理作業(yè)調(diào)度問題學(xué)習(xí)目標(biāo)第第9章章 分支限界法分支限界法 9.1 概概 述述 9.2 圖圖問題中的分支限界法問題中的

2、分支限界法9.3 組合問題中的分支限界法組合問題中的分支限界法回溯法回溯法：按深度優(yōu)先策略遍歷問題的解空間：按深度優(yōu)先策略遍歷問題的解空間樹，應(yīng)用約束條件、目標(biāo)函數(shù)等剪枝函數(shù)實(shí)樹，應(yīng)用約束條件、目標(biāo)函數(shù)等剪枝函數(shù)實(shí)行剪枝行剪枝分支限界法分支限界法：按廣度優(yōu)先策略遍歷問題的解：按廣度優(yōu)先策略遍歷問題的解空間樹，在遍歷過程中，對已經(jīng)處理的每一空間樹，在遍歷過程中，對已經(jīng)處理的每一個(gè)結(jié)點(diǎn)根據(jù)限界函數(shù)估算目標(biāo)函數(shù)的可能取個(gè)結(jié)點(diǎn)根據(jù)限界函數(shù)估算目標(biāo)函數(shù)的可能取值，從中選取使目標(biāo)函數(shù)取得極值的結(jié)點(diǎn)優(yōu)值，從中選取使目標(biāo)函數(shù)取得極值的結(jié)點(diǎn)優(yōu)先進(jìn)行廣度優(yōu)先搜索，從而不斷調(diào)整搜索方先進(jìn)行廣度優(yōu)先搜索，從而不斷調(diào)整

3、搜索方向，盡快找到問題的解。向，盡快找到問題的解。 9.1 概概 述述 9.1 概概 述述 9.1.1 分支限界法的設(shè)計(jì)思想分支限界法的設(shè)計(jì)思想9.1.2 分支限界法的時(shí)間性能分支限界法的時(shí)間性能分支限界法的設(shè)計(jì)思想分支限界法的設(shè)計(jì)思想分支限界法的設(shè)計(jì)思想分支限界法的設(shè)計(jì)思想物品物品重量重量(w)價(jià)值價(jià)值(v)價(jià)值價(jià)值/重量重量(v/w)144010274263525543124分支限界法的設(shè)計(jì)思想分支限界法的設(shè)計(jì)思想)()(11iiwvwWvub分支限界法的設(shè)計(jì)思想分支限界法的設(shè)計(jì)思想w=0, v=0ub=100w=4, v=40ub=76w=0, v=0ub=60w=11無效解無效解w=4

4、, v=40ub=70w=9, v=65ub=69w=4, v=40ub=64w=12無效解無效解w=9, v=65ub=65234567891PT表圖9.1 0/1背包問題分支限界法的設(shè)計(jì)思想分支限界法的設(shè)計(jì)思想n在表在表PT中選取目標(biāo)函數(shù)值取得中選取目標(biāo)函數(shù)值取得極大的結(jié)點(diǎn)極大的結(jié)點(diǎn)2 優(yōu)先進(jìn)行搜索；優(yōu)先進(jìn)行搜索； 分支限界法的設(shè)計(jì)思想分支限界法的設(shè)計(jì)思想在表在表PT中選取目標(biāo)函數(shù)值取得極大的結(jié)點(diǎn)中選取目標(biāo)函數(shù)值取得極大的結(jié)點(diǎn)5 優(yōu)先進(jìn)行搜索優(yōu)先進(jìn)行搜索分支限界法的設(shè)計(jì)思想分支限界法的設(shè)計(jì)思想在表在表PT 中選取目標(biāo)函數(shù)值取得極大的結(jié)點(diǎn)中選取目標(biāo)函數(shù)值取得極大的結(jié)點(diǎn)6 優(yōu)先進(jìn)行搜索優(yōu)先進(jìn)行

5、搜索分支限界法的設(shè)計(jì)思想分支限界法的設(shè)計(jì)思想分支限界法的設(shè)計(jì)思想分支限界法的設(shè)計(jì)思想(c) 擴(kuò)展結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)5后后 (d) 擴(kuò)展結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)6 后，最優(yōu)解為后，最優(yōu)解為(1,0,1,0)65 圖圖9.2 方法確定方法確定0/1背包問題最優(yōu)解的各分量背包問題最優(yōu)解的各分量(a) 擴(kuò)展根結(jié)點(diǎn)后擴(kuò)展根結(jié)點(diǎn)后 (b) 擴(kuò)展結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)2后后(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)3792567分支限界法

6、的設(shè)計(jì)思想分支限界法的設(shè)計(jì)思想分支限界法的設(shè)計(jì)思想分支限界法的設(shè)計(jì)思想分支限界法的一般過程分支限界法的一般過程 1根據(jù)限界函數(shù)計(jì)算目標(biāo)函數(shù)的根據(jù)限界函數(shù)計(jì)算目標(biāo)函數(shù)的 down，up； 2將待處理結(jié)點(diǎn)表將待處理結(jié)點(diǎn)表PT 初始化為空；初始化為空； 3. 對根結(jié)點(diǎn)的每個(gè)孩子結(jié)點(diǎn)對根結(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)；

7、中值最大的結(jié)點(diǎn)；4.2 對結(jié)點(diǎn)對結(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ù)值的目標(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)且value值在表值在表PT中最大），則將結(jié)點(diǎn)中最大），則將結(jié)點(diǎn)x對對應(yīng)的解輸出，算法結(jié)束；應(yīng)的解輸出，算法結(jié)束；4.2.4 若若(結(jié)點(diǎn)結(jié)點(diǎn)x是葉子結(jié)點(diǎn)但是葉子結(jié)點(diǎn)但value值在表值在表PT中不是最大中不是最大),則令則令down=value，并且將表，并且將表PT中所有小于中所有小于value的結(jié)點(diǎn)

8、刪除；的結(jié)點(diǎn)刪除；分支限界法的設(shè)計(jì)思想分支限界法的設(shè)計(jì)思想),()(211kxxxx),(),(211kxxxboundxbound),(),()(21211kxxxboundxxboundxbound分支限界法的設(shè)計(jì)思想分支限界法的設(shè)計(jì)思想),(21kxxxX),(),()(21211kxxxboundxxboundxbound分支限界法的設(shè)計(jì)思想分支限界法的設(shè)計(jì)思想分支限界法的設(shè)計(jì)思想分支限界法的設(shè)計(jì)思想分支限界法的設(shè)計(jì)思想分支限界法的設(shè)計(jì)思想分支限界法的設(shè)計(jì)思想分支限界法的設(shè)計(jì)思想(c) 擴(kuò)展結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)5后后 (d) 擴(kuò)展結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)6 后，最優(yōu)解為后，最優(yōu)解為(1,0,1,0)65

9、圖圖9.3 方法確定方法確定0/1背包問題最優(yōu)解的各分量背包問題最優(yōu)解的各分量(a) 擴(kuò)展根結(jié)點(diǎn)后擴(kuò)展根結(jié)點(diǎn)后 (b) 擴(kuò)展結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)2后后(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)3792567分支限界法的設(shè)計(jì)思想分支限界法的設(shè)計(jì)思想9.1 概概 述述 9.1.1 分支限界法的設(shè)計(jì)思想分支限界法的設(shè)計(jì)思想9.1.2 分支限界法的時(shí)間性能分支限界法的時(shí)間性能9.1.2 分支限界法的時(shí)間性能分支限

10、界法的時(shí)間性能 9.1.2 分支限界法的時(shí)間性能分支限界法的時(shí)間性能 第第9章章 分支限界法分支限界法 9.1 概概 述述 9.2 圖問題中的分支限界法圖問題中的分支限界法9.3 組合問題中的分支限界法組合問題中的分支限界法9.2 圖問題中的分支限界法圖問題中的分支限界法 9.2.1 TSP問題問題 9.2.2 多段圖的最短路徑問題多段圖的最短路徑問題9.2.1 TSP問題問題 TSP TSP問題是指旅行家要旅行問題是指旅行家要旅行n個(gè)城市，要求各個(gè)城個(gè)城市，要求各個(gè)城市經(jīng)歷且僅經(jīng)歷一次然后回到出發(fā)城市，并要求所走市經(jīng)歷且僅經(jīng)歷一次然后回到出發(fā)城市，并要求所走的路程最短。的路程最短。27156

11、3134253984C= 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 (a) 一個(gè)無向圖一個(gè)無向圖 (b) 無向圖的代價(jià)矩陣無向圖的代價(jià)矩陣圖圖9.4 無向圖及其代價(jià)矩陣無向圖及其代價(jià)矩陣9.2 TSP問題問題271563134253984n 部分解的目標(biāo)函數(shù)值的計(jì)算方法部分解的目標(biāo)函數(shù)值的計(jì)算方法n假設(shè)當(dāng)前已確定的路徑為假設(shè)當(dāng)前已確定的路徑為U=(r1,r2,rk), 則：則： 例如圖例如圖10.4所示無向圖，如果部分解包含頂點(diǎn)所示無向圖，如果部分解包含頂點(diǎn)U=(1, 4)，則該，則該部分解的下界是部分解的下界是: lb=(2*5+(1+3)+(3+6)+

12、(1+2)+(2+3)/2=16UrUrjikiiiijrrrrclb2/ )2(111行最小的兩個(gè)元素素行不在路徑上的最小元分支限界法求解分支限界法求解TSP問題示例問題示例271563134253984C= 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 1111,(2 )/ 2jkiiijiikrUlbc rrrr行不在路徑上的最小元素行最小的兩個(gè)元素分支限界法求解分支限界法求解TSP問題示例問題示例在表在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)2優(yōu)先進(jìn)行搜索

13、優(yōu)先進(jìn)行搜索 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 分支限界法求解分支限界法求解TSP問題示例問題示例在表在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)3優(yōu)先進(jìn)行搜索優(yōu)先進(jìn)行搜索 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 在表在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)11優(yōu)先進(jìn)行搜索優(yōu)先進(jìn)行搜索n處理結(jié)點(diǎn)處理結(jié)點(diǎn)11的孩子。結(jié)點(diǎn)的孩子。結(jié)點(diǎn)12，C1C3C5C2 ，路徑長度為1+2+9，目標(biāo)函數(shù)值:lb=(2*12+(3+3)+(3+4)/2=19 超出目標(biāo)函數(shù)的界，將結(jié)點(diǎn)12丟棄n

14、在結(jié)點(diǎn)在結(jié)點(diǎn)13， C1C3 C5C4 ，路徑長度為1+2+3 目標(biāo)函數(shù)值：lb=(2*6+(3+4)+(3+6)/2=14,將結(jié)點(diǎn)13加入表PT中在表在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)13優(yōu)先進(jìn)行搜索優(yōu)先進(jìn)行搜索 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 在表在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)10優(yōu)先進(jìn)行搜索優(yōu)先進(jìn)行搜索n處理結(jié)點(diǎn)處理結(jié)點(diǎn)13的孩子。結(jié)點(diǎn)的孩子。結(jié)點(diǎn)14， C1C3 C5C4C2 ，路徑長度為1+2+3+7，目標(biāo)函數(shù)值:lb=(2*13+(3+3)/2=16由于結(jié)點(diǎn)14為葉子結(jié)點(diǎn)，得到一

15、個(gè)可行解其路徑長度為16 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 分支限界法求解分支限界法求解TSP問題示例問題示例分支限界法求解分支限界法求解TSP問題示例問題示例在表在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)16優(yōu)先進(jìn)行搜索優(yōu)先進(jìn)行搜索n處理結(jié)點(diǎn)處理結(jié)點(diǎn)10的孩子。結(jié)點(diǎn)的孩子。結(jié)點(diǎn)15，C1C3 C4C2，長，長度度12。 目標(biāo)函數(shù):lb=(2*12+(3+3)+(2+3)/2=18 超出目標(biāo)函數(shù)的界，將結(jié)點(diǎn)15丟棄n結(jié)點(diǎn)結(jié)點(diǎn)16， C1C3 C4C5 ，長度，長度8 目標(biāo)函數(shù):lb=(2*8+(3+2)+(3+6)/2=15 將結(jié)

16、點(diǎn)16加入表PT中n處理結(jié)點(diǎn)處理結(jié)點(diǎn)16的孩子。結(jié)點(diǎn)的孩子。結(jié)點(diǎn)17,C1C3C4C5C2,長度長度17，目標(biāo)函數(shù):lb =(2*17+(3+3)/2=20,超目標(biāo)函數(shù)的界，結(jié)點(diǎn)17丟棄表表PT中目標(biāo)函數(shù)值均為中目標(biāo)函數(shù)值均為16，且已找到葉子結(jié)點(diǎn)，且已找到葉子結(jié)點(diǎn)14的長度是的長度是16，故這是最優(yōu)解，搜索過程結(jié)束。故這是最優(yōu)解，搜索過程結(jié)束。 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 412lb=142356781startlb=1413lb=1414lb=1615lb=1923lb=1624lb=1625lb=1932lb=1634lb=1535lb

17、=1491152lb=1954lb=141142lb=16142lb=1845lb=151152lb=201分支限界法求解分支限界法求解TSP問題示例問題示例C2C1C3C5C4C3C5C4C2C4C5C4C2C2 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 (g) 擴(kuò)展結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)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) 擴(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)后的

18、狀態(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 (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)

19、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 (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)算法算法9.1TSP問題問題輸入：圖輸入：圖G（V，E）輸出：最短哈密爾頓回路輸出：最短哈密爾頓回路 1根據(jù)限界函數(shù)計(jì)算目標(biāo)函數(shù)的下界根據(jù)限界函數(shù)計(jì)算目標(biāo)函數(shù)的下界down；采用貪心法得到上界；采用貪心法得到上界up； 2計(jì)算根結(jié)點(diǎn)的目標(biāo)函數(shù)值

20、并加入待處理結(jié)點(diǎn)表計(jì)算根結(jié)點(diǎn)的目標(biāo)函數(shù)值并加入待處理結(jié)點(diǎn)表PT； 3循環(huán)直到某個(gè)葉子結(jié)點(diǎn)的目標(biāo)函數(shù)值在表循環(huán)直到某個(gè)葉子結(jié)點(diǎn)的目標(biāo)函數(shù)值在表PT中取得極小值中取得極小值 3.1 i=表表PT中具有最小值的結(jié)點(diǎn)；中具有最小值的結(jié)點(diǎn)； 3.2 對結(jié)點(diǎn)對結(jié)點(diǎn)i的每個(gè)孩子結(jié)點(diǎn)的每個(gè)孩子結(jié)點(diǎn)x執(zhí)行下列操作：執(zhí)行下列操作：3.2.1 估算結(jié)點(diǎn)估算結(jié)點(diǎn)x的目標(biāo)函數(shù)值的目標(biāo)函數(shù)值lb;3.2.2 若（若（lb kijpiEvrijjjjvrcrrclbpi21,11min1段的最短邊段的最短邊第第 應(yīng)用分支限界法求解圖9.7所示多段圖的最短路徑問題，其搜索空間如圖9.8所示，具體的搜索過程如下（加黑表示該路徑

21、上已經(jīng)確定的邊）：（1）在根結(jié)點(diǎn)1，計(jì)算目標(biāo)函數(shù)的值為14，將根結(jié)點(diǎn)加入表PT；（2）處理根結(jié)點(diǎn)每個(gè)孩子結(jié)點(diǎn)。結(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+7+5+3=17，將結(jié)點(diǎn)3加入表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)行搜索；1203456789492387884756866537（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段選擇邊

22、，目標(biāo)函數(shù)值為lb=3+7+5+3=18，將結(jié)點(diǎn)6加入表PT；（5）在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)5優(yōu)先進(jìn)行搜索；（6）處理結(jié)點(diǎn)5的每個(gè)孩子結(jié)點(diǎn)。結(jié)點(diǎn)7，已確定路徑是0357，可直接確定第4段的邊，目標(biāo)函數(shù)值為lb=3+4+8+7=22，超界丟棄；在結(jié)點(diǎn)8，已確定路徑是0358，可直接確定第4段的邊，目標(biāo)函數(shù)值為lb=3+4+6+3=16，為一個(gè)可行解；由于結(jié)點(diǎn)8是葉子結(jié)點(diǎn)，并且其目標(biāo)函數(shù)值是PT中最小的，所以它是最優(yōu)解，搜索結(jié)束。12034567894923878847568665376401lb=20231startlb=1802lb=1603lb=15圖圖9.8 分支限界法求解多段圖

23、的最短路徑問題示例分支限界法求解多段圖的最短路徑問題示例(表示該結(jié)點(diǎn)被丟棄，結(jié)點(diǎn)上方的數(shù)組表示搜索順序表示該結(jié)點(diǎn)被丟棄，結(jié)點(diǎn)上方的數(shù)組表示搜索順序)535lb=1636lb=1887lb=22lb=165857第第9章章 分支限界法分支限界法 9.1 概概 述述 9.2 圖問題中的分支限界法圖問題中的分支限界法9.3 組合問題中的分支限界法組合問題中的分支限界法9.3 9.3 組合問題中的分支限界法組合問題中的分支限界法 9.3.2 9.3.2 任務(wù)分配問題任務(wù)分配問題 9.3.3 9.3.3 批處理作業(yè)調(diào)度問題批處理作業(yè)調(diào)度問題9.3.1 9.3.1 0/1背包問題背包問題9.3.2 任務(wù)分

24、配問題任務(wù)分配問題 C9 2 7 86 4 3 75 8 1 87 6 9 4任務(wù)任務(wù)1 任務(wù)任務(wù)2 任務(wù)任務(wù)3 任務(wù)任務(wù)4人員人員a人員人員b人員人員c人員人員d圖圖9.10 任務(wù)分配問題的成本矩陣任務(wù)分配問題的成本矩陣9.3.2 任務(wù)分配問題任務(wù)分配問題 C9 2 7 86 4 3 75 8 1 87 6 9 4任務(wù)任務(wù)1 任務(wù)任務(wù)2 任務(wù)任務(wù)3 任務(wù)任務(wù)4人員人員a人員人員b人員人員c人員人員d圖圖9.10 任務(wù)分配問題的成本矩陣任務(wù)分配問題的成本矩陣9.3.2 任務(wù)分配問題任務(wù)分配問題 nikkvlb1行的最小值第9.3.2 任務(wù)分配問題任務(wù)分配問題 C9 2 7 86 4 3 75

25、8 1 87 6 9 4人員人員a人員人員b人員人員c人員人員d圖圖9.11 分支限界法求解任務(wù)分配問題示例分支限界法求解任務(wù)分配問題示例(表示該結(jié)點(diǎn)被丟棄，結(jié)點(diǎn)上方的數(shù)組表示搜索順序表示該結(jié)點(diǎn)被丟棄，結(jié)點(diǎn)上方的數(shù)組表示搜索順序)4alb=16104startlb=101alb=172alb=103alb=151blb=133blb=104blb=141clb=144clb=174clb=173clb=134dlb=1323567891213111nikkvlb1行的最小值第 C9 2 7 86 4 3 75 8 1 87 6 9 4任務(wù)任務(wù)1 任務(wù)任務(wù)2 任務(wù)任務(wù)3 任務(wù)任務(wù)4人員人員a人員

26、人員b人員人員c人員人員d任務(wù)1任務(wù)4任務(wù)2任務(wù)1任務(wù)3任務(wù)4任務(wù)1任務(wù)49.3.2 任務(wù)分配問題任務(wù)分配問題 9.3.2 任務(wù)分配問題任務(wù)分配問題 C9 2 7 86 4 3 75 8 1 87 6 9 4任務(wù)任務(wù)1 任務(wù)任務(wù)2 任務(wù)任務(wù)3 任務(wù)任務(wù)4人員人員a人員人員b人員人員c人員人員dn在結(jié)點(diǎn)在結(jié)點(diǎn)6 將J2人員a,J1人員b，獲得的成本為2+6=8 目標(biāo)函數(shù)值:lb=8+(1+4)13 將結(jié)點(diǎn)6加入表PT中在表在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)3優(yōu)先進(jìn)行搜索優(yōu)先進(jìn)行搜索9.3.2 任務(wù)分配問題任務(wù)分配問題 9 2 7 86 4 3 75 8 1 87 6 9

27、 4任務(wù)任務(wù)1 任務(wù)任務(wù)2 任務(wù)任務(wù)3 任務(wù)任務(wù)4人員人員a人員人員b人員人員c人員人員d在表在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)7優(yōu)先進(jìn)行搜索優(yōu)先進(jìn)行搜索9.3.2 任務(wù)分配問題任務(wù)分配問題 9 2 7 86 4 3 75 8 1 87 6 9 4任務(wù)任務(wù)1 任務(wù)任務(wù)2 任務(wù)任務(wù)3 任務(wù)任務(wù)4人員人員a人員人員b人員人員c人員人員d在表在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)6 6優(yōu)先進(jìn)行搜索優(yōu)先進(jìn)行搜索9.3.2 任務(wù)分配問題任務(wù)分配問題 在表在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)1111優(yōu)先進(jìn)行搜索優(yōu)先進(jìn)行搜索9.3.2

28、任務(wù)分配問題任務(wù)分配問題 9 2 7 86 4 3 75 8 1 87 6 9 4任務(wù)任務(wù)1 任務(wù)任務(wù)2 任務(wù)任務(wù)3 任務(wù)任務(wù)49.3.2 任務(wù)分配問題任務(wù)分配問題 (人員人員i-1分配的任務(wù)分配的任務(wù),lb)(e) 擴(kuò)展結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)11后的狀態(tài)，后的狀態(tài)，最優(yōu)解為最優(yōu)解為2a，1b，3c，4d(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)擴(kuò)展根結(jié)點(diǎn)

29、后的狀態(tài) (b) 擴(kuò)展結(jié)點(diǎn)擴(kuò)展結(jié)點(diǎn)3后的狀態(tài)后的狀態(tài) PTSTPTST PTST (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 9.3.2 任務(wù)分配問題任務(wù)分配問題 算法算法9.3任務(wù)分配問題任務(wù)分配問題 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 xk=1; 5.2 while (xk=n) 5.2.1 如果人員如果人員k 分配任務(wù)分配

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

31、表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+;9.3.2 任務(wù)分配問題任務(wù)分配問題 9.3 9.3 組合問題中的分支限界法組合問題中的分支限界法 9.3.2 9.3.2 任務(wù)分配問題任務(wù)分配問題 9.3.3 9.3.3 批處理作業(yè)調(diào)度問題批處理作業(yè)調(diào)度問題9.3.1 9.3.1 0/1背包問題背包問題9.3.3 批處理作業(yè)調(diào)度問題批處理作業(yè)調(diào)度問題T 5 7 910 5 2

32、 9 9 5 7 8 10J1J2J3J4機(jī)器1 機(jī)器2 機(jī)器3 設(shè)設(shè) J=J1, J2, J3, J4 是是 4 個(gè)待處理的作業(yè)，每個(gè)作業(yè)的處個(gè)待處理的作業(yè)，每個(gè)作業(yè)的處理順序相同理順序相同: 機(jī)器機(jī)器1上處理上處理機(jī)器機(jī)器2上處理上處理機(jī)器機(jī)器3上處理上處理需要的處理時(shí)間如下矩陣所示需要的處理時(shí)間如下矩陣所示:9.3.3 批處理作業(yè)調(diào)度問題批處理作業(yè)調(diào)度問題上界？隨機(jī)產(chǎn)生幾個(gè)方案，從中選取最短完成時(shí)間為問題的上界？隨機(jī)產(chǎn)生幾個(gè)方案，從中選取最短完成時(shí)間為問題的上界。如若處理順序?yàn)樯辖纭Ｈ缛籼幚眄樞驗(yàn)? :J4 J1 J3 J2，調(diào)度方案，調(diào)度方案: :J4:7 J1:5 J3:9 J2:1

33、0機(jī)器機(jī)器1機(jī)器機(jī)器2機(jī)器機(jī)器3 圖圖9.13 批處理調(diào)度問題的調(diào)度方案批處理調(diào)度問題的調(diào)度方案空閑空閑:7 J4:8 J1:7 J3:9 J2:5空閑空閑:15 J4:10 J1:9 J3:5 J2:29.3.3 批處理作業(yè)調(diào)度問題批處理作業(yè)調(diào)度問題上界：41min3121kiknjjitttn批處理作業(yè)調(diào)度問題的限界函數(shù)批處理作業(yè)調(diào)度問題的限界函數(shù)ndown理想情況機(jī)器1和機(jī)器2開始作業(yè)后無空閑，最后處理的恰好是在機(jī)器3上處理時(shí)間最短的作業(yè)。例如，以作業(yè) Ji 開始的處理順序，估算處理所需的最短時(shí)間是最短時(shí)間是：tij: 表示表示 Ji 需要機(jī)器需要機(jī)器 j 的處理時(shí)間的處理時(shí)間(1in,

34、 1j3)9.3.3 批處理作業(yè)調(diào)度問題批處理作業(yè)調(diào)度問題作業(yè)Ji在機(jī)器1上的處理時(shí)間作業(yè)作業(yè)1作業(yè)作業(yè)n在機(jī)器2上的處理時(shí)間總和在機(jī)器3上處理時(shí)間最短的作業(yè)n目標(biāo)函數(shù)下界計(jì)算目標(biāo)函數(shù)下界計(jì)算lb若已安排了k-1個(gè)作業(yè)集合，即：M 1, 2, , k-1，|M|=k-1sum1k-1：機(jī)器機(jī)器1 1完成k-1個(gè)作業(yè)的處理時(shí)間sum2k-1：機(jī)器2完成k-1個(gè)作業(yè)的處理時(shí)間現(xiàn)要處理作業(yè)k，此時(shí)，該部分解的目標(biāo)函數(shù)值的下界lb計(jì)算方法如下：（1）sum1k=sum1k-1+ tk1（2）（3）sum2k=maxsum1k, sum2k-1 + tk2 23,maxsum1k,sum2k-1min ijj k j Mi Mlbtt9.3.3 批