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

1、教學(xué)重點教學(xué)重點分支限界法的設(shè)計思想，各種經(jīng)典問題的限界函數(shù)分支限界法的設(shè)計思想，各種經(jīng)典問題的限界函數(shù)教學(xué)難點教學(xué)難點各種經(jīng)典問題的限界函數(shù)以及限界算法各種經(jīng)典問題的限界函數(shù)以及限界算法教學(xué)內(nèi)容及目教學(xué)內(nèi)容及目標(biāo)標(biāo)知識點知識點教學(xué)要求教學(xué)要求了解了解理解理解掌握掌握熟練掌握熟練掌握分支限界法的設(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ù)實樹，應(yīng)用約束條件、目標(biāo)函數(shù)等剪枝函數(shù)實行剪枝行剪枝分支限界法分支限界法：按廣度優(yōu)先策略遍歷問題的解：按廣度優(yōu)先策略遍歷問題的解空間樹，在遍歷過程中，對已經(jīng)處理的每一空間樹，在遍歷過程中，對已經(jīng)處理的每一個結(jié)點根據(jù)限界函數(shù)估算目標(biāo)函數(shù)的可能取個結(jié)點根據(jù)限界函數(shù)估算目標(biāo)函數(shù)的可能取值，從中選取使目標(biāo)函數(shù)取得極值的結(jié)點優(yōu)值，從中選取使目標(biāo)函數(shù)取得極值的結(jié)點優(yōu)先進(jìn)行廣度優(yōu)先搜索，從而不斷調(diào)整搜索方先進(jìn)行廣度優(yōu)先搜索，從而不斷調(diào)整

3、搜索方向，盡快找到問題的解。向，盡快找到問題的解。 9.1 概概 述述 9.1 概概 述述 9.1.1 分支限界法的設(shè)計思想分支限界法的設(shè)計思想9.1.2 分支限界法的時間性能分支限界法的時間性能n回溯法存在的問題回溯法存在的問題n雖用雖用剪枝剪枝減少了搜索空間，但減少了搜索空間，但按深度優(yōu)先策略機(jī)械地進(jìn)按深度優(yōu)先策略機(jī)械地進(jìn)行行，搜索是盲目的，搜索是盲目的。如。如0/1背包問題。背包問題。n首先將目標(biāo)函數(shù)初始化為最大值，目標(biāo)函數(shù)只有在首先將目標(biāo)函數(shù)初始化為最大值，目標(biāo)函數(shù)只有在有一有一個可行解（第一個葉子）后才有意義個可行解（第一個葉子）后才有意義，此后的搜索相對，此后的搜索相對來說才有方向

4、，所以從搜索的整個過程來看還是盲目的。來說才有方向，所以從搜索的整個過程來看還是盲目的。如如TSP問題（圖問題（圖8.6）。）。n分支限界法分支限界法n先確定一個合理的先確定一個合理的限界函數(shù)限界函數(shù)n由限界函數(shù)確定目標(biāo)函數(shù)的界由限界函數(shù)確定目標(biāo)函數(shù)的界down, upn仍以仍以窮舉法的解空間樹窮舉法的解空間樹為基礎(chǔ)，但以為基礎(chǔ)，但以廣度優(yōu)先的原理廣度優(yōu)先的原理搜搜索該結(jié)點的所有孩子結(jié)點，分別估算這些索該結(jié)點的所有孩子結(jié)點，分別估算這些孩子結(jié)點的目孩子結(jié)點的目標(biāo)函數(shù)的可能取值標(biāo)函數(shù)的可能取值分支限界法的設(shè)計思想分支限界法的設(shè)計思想n如果某孩子結(jié)點的目標(biāo)函數(shù)如果某孩子結(jié)點的目標(biāo)函數(shù)可能取值超出目

5、標(biāo)函數(shù)的界，則可能取值超出目標(biāo)函數(shù)的界，則將其丟棄，將其丟棄，因為從這個結(jié)點生成的解不會比目前已經(jīng)得到的因為從這個結(jié)點生成的解不會比目前已經(jīng)得到的解更好；否則，將其加入待處理結(jié)點表（表解更好；否則，將其加入待處理結(jié)點表（表PT）n依次從表依次從表PT中選取使目標(biāo)函數(shù)的值取極值的結(jié)點成為當(dāng)前擴(kuò)中選取使目標(biāo)函數(shù)的值取極值的結(jié)點成為當(dāng)前擴(kuò)展結(jié)點，重復(fù)上述過程，直到找到最優(yōu)解。展結(jié)點，重復(fù)上述過程，直到找到最優(yōu)解。n目標(biāo)函數(shù)的界目標(biāo)函數(shù)的界down, up的確定的確定n對最大化問題對最大化問題UpUp由限界函數(shù)確定，由限界函數(shù)確定，downdown由某種啟發(fā)方式得到由某種啟發(fā)方式得到, ,如貪心算法如

6、貪心算法n對最小化問題對最小化問題downdown由限界函數(shù)確定，由限界函數(shù)確定，upup由某種啟發(fā)方式得到由某種啟發(fā)方式得到, ,如貪心算法如貪心算法分支限界法的設(shè)計思想分支限界法的設(shè)計思想n例：例：0/1背包問題。假設(shè)有背包問題。假設(shè)有4個物品，其重量分別個物品，其重量分別為為(4, 7, 5, 3)，價值分別為，價值分別為(40, 42, 25, 12)，背包容，背包容量量W=10。首先，將給定物品按單位重量價值從大。首先，將給定物品按單位重量價值從大到小排序，結(jié)果如下：到小排序，結(jié)果如下：物品物品重量重量(w)價值價值(v)價值價值/重量重量(v/w)14401027426352554

7、3124分支限界法的設(shè)計思想分支限界法的設(shè)計思想n確定上下界確定上下界 ndowndown：應(yīng)用貪心法求得近似解為應(yīng)用貪心法求得近似解為(1, 0, 0, 0)，獲得的價值，獲得的價值為為40，這可以作為，這可以作為0/1背包問題的背包問題的下界下界。nupup：考慮最好情況，背包中全部裝入第考慮最好情況，背包中全部裝入第1個物品且可以個物品且可以將背包裝滿，則可得到一個將背包裝滿，則可得到一個簡單上界簡單上界的計算方法：的計算方法： up=W(v1/w1)=1010=100n則目標(biāo)函數(shù)的界：則目標(biāo)函數(shù)的界：40, 100n限界函數(shù)為限界函數(shù)為：)()(11iiwvwWvub分支限界法的設(shè)計思

8、想分支限界法的設(shè)計思想w=0, 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無效解無效解w=9, v=65ub=65234567891PT表圖9.1 0/1背包問題分支限界法的設(shè)計思想分支限界法的設(shè)計思想n分支限界法的搜索過程如下：分支限界法的搜索過程如下：n在根結(jié)點在根結(jié)點1 沒有物品裝入背包，沒有物品裝入背包，w=0,v=0 限界函數(shù)值：限界函數(shù)值：ub=0+(10-0)=1010=100n在結(jié)點在結(jié)點2 物品物品1裝入背包，裝入背包，w=w1=4，v

9、=40 目標(biāo)函數(shù)值目標(biāo)函數(shù)值:ub=40 + (10-4)6=76 將結(jié)點將結(jié)點2加入待處理結(jié)點表加入待處理結(jié)點表PT中中n在結(jié)點在結(jié)點3 物品物品1不裝入背包，不裝入背包， w=0,v=0 目標(biāo)函數(shù)值目標(biāo)函數(shù)值: 10ub=0+(10-0)660， 將結(jié)點將結(jié)點3加入表加入表PT中中n在表在表PT中選取目標(biāo)函數(shù)值取得中選取目標(biāo)函數(shù)值取得極大的結(jié)點極大的結(jié)點2 優(yōu)先進(jìn)行搜索；優(yōu)先進(jìn)行搜索； 分支限界法的設(shè)計思想分支限界法的設(shè)計思想n在結(jié)點在結(jié)點4 物品物品2裝入背包，裝入背包，w=11W，不滿足約束條件，不滿足約束條件， 將結(jié)點將結(jié)點4丟棄丟棄n在結(jié)點在結(jié)點5 物品物品2不裝入背包，不裝入背包

10、， w=4,v=40 與結(jié)點與結(jié)點2相同相同 目標(biāo)函數(shù)值為目標(biāo)函數(shù)值為: ub=40 + (10-4)5=70 將結(jié)點將結(jié)點5加入表加入表PT中中n在結(jié)點在結(jié)點6 物品物品3裝入背包，裝入背包，w=4+5=9，v=40+25=65 目標(biāo)函數(shù)值為目標(biāo)函數(shù)值為: ub=65 + (10-9)4=69 將結(jié)點將結(jié)點6加入表加入表PT中中在表在表PT中選取目標(biāo)函數(shù)值取得極大的結(jié)點中選取目標(biāo)函數(shù)值取得極大的結(jié)點5 優(yōu)先進(jìn)行搜索優(yōu)先進(jìn)行搜索分支限界法的設(shè)計思想分支限界法的設(shè)計思想n在結(jié)點在結(jié)點7 物品物品3不裝入背包，不裝入背包，w=4,v=40,與結(jié)點與結(jié)點5相同相同 目標(biāo)函數(shù)值為：目標(biāo)函數(shù)值為：ub=

11、40 + (10-4)464 將結(jié)點將結(jié)點7加入表加入表PT中中n在結(jié)點在結(jié)點8 物品物品4裝入背包，裝入背包，w=12W, 不滿足約束條件，將結(jié)點不滿足約束條件，將結(jié)點8丟棄；丟棄；n在結(jié)點在結(jié)點9 物品物品4 4不裝入背包，不裝入背包，w=9, v=65, ,與結(jié)點與結(jié)點6相同相同 目標(biāo)函數(shù)值為目標(biāo)函數(shù)值為: :ub=65+(W-w)*0=65 將結(jié)點將結(jié)點7加入表加入表PT中中在表在表PT 中選取目標(biāo)函數(shù)值取得極大的結(jié)點中選取目標(biāo)函數(shù)值取得極大的結(jié)點6 優(yōu)先進(jìn)行搜索優(yōu)先進(jìn)行搜索分支限界法的設(shè)計思想分支限界法的設(shè)計思想n結(jié)點結(jié)點9是葉子結(jié)點是葉子結(jié)點 同時結(jié)點同時結(jié)點9 的目標(biāo)函數(shù)值是表的

12、目標(biāo)函數(shù)值是表PT 中的極大值，中的極大值， 結(jié)點結(jié)點9 對應(yīng)的解即是問題的最優(yōu)解，對應(yīng)的解即是問題的最優(yōu)解，搜索結(jié)束搜索結(jié)束n在圖在圖9.1的的0/1背包問題中，為了在搜索過程中背包問題中，為了在搜索過程中構(gòu)建搜索構(gòu)建搜索經(jīng)過的樹結(jié)構(gòu)經(jīng)過的樹結(jié)構(gòu)，設(shè)一個表，設(shè)一個表PTPT，記錄搜索過程，如圖，記錄搜索過程，如圖9.2。n再設(shè)計了一表再設(shè)計了一表ST，從，從PTPT中中取出最大值結(jié)點進(jìn)行擴(kuò)充取出最大值結(jié)點進(jìn)行擴(kuò)充時，時，將最大值結(jié)點存儲到表將最大值結(jié)點存儲到表ST中，表中，表PT和表和表ST的數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)為：為： ( (物品物品i-1的選擇結(jié)果，的選擇結(jié)果， ub) ) 在搜索過程中表

13、在搜索過程中表PTPT和表和表ST 的狀態(tài)如圖的狀態(tài)如圖9.2所示所示分支限界法的設(shè)計思想分支限界法的設(shè)計思想(c) 擴(kuò)展結(jié)點擴(kuò)展結(jié)點5后后 (d) 擴(kuò)展結(jié)點擴(kuò)展結(jié)點6 后，最優(yōu)解為后，最優(yōu)解為(1,0,1,0)65 圖圖9.2 方法確定方法確定0/1背包問題最優(yōu)解的各分量背包問題最優(yōu)解的各分量(a) 擴(kuò)展根結(jié)點后擴(kuò)展根結(jié)點后 (b) 擴(kuò)展結(jié)點擴(kuò)展結(jié)點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

14、)3792567分支限界法的設(shè)計思想分支限界法的設(shè)計思想分支限界法的設(shè)計思想分支限界法的設(shè)計思想分支限界法的一般過程分支限界法的一般過程 1根據(jù)限界函數(shù)計算目標(biāo)函數(shù)的根據(jù)限界函數(shù)計算目標(biāo)函數(shù)的 down，up； 2將待處理結(jié)點表將待處理結(jié)點表PT 初始化為空；初始化為空； 3. 對根結(jié)點的每個孩子結(jié)點對根結(jié)點的每個孩子結(jié)點x執(zhí)行下列操作執(zhí)行下列操作 3.1 估算結(jié)點估算結(jié)點x的目標(biāo)函數(shù)值的目標(biāo)函數(shù)值value; 3.2 若（若（value=down）,則將結(jié)點則將結(jié)點x加入表加入表PT中；中； 4循環(huán)直到某個葉子結(jié)點的目標(biāo)函數(shù)值在表循環(huán)直到某個葉子結(jié)點的目標(biāo)函數(shù)值在表PT中最大中最大4.1 i

15、=表表PT中值最大的結(jié)點；中值最大的結(jié)點；4.2 對結(jié)點對結(jié)點i的每個孩子結(jié)點的每個孩子結(jié)點x執(zhí)行下列操作執(zhí)行下列操作4.2.1 估算結(jié)點估算結(jié)點x的目標(biāo)函數(shù)值的目標(biāo)函數(shù)值value；4.2.2 若若(value=down)，則將結(jié)點，則將結(jié)點x加入表加入表PT中；中；4.2.3 若（結(jié)點若（結(jié)點x是葉子結(jié)點且是葉子結(jié)點且value值在表值在表PT中最大），則將結(jié)中最大），則將結(jié)點點x對應(yīng)的解輸出，算法結(jié)束；對應(yīng)的解輸出，算法結(jié)束；4.2.4 若若(結(jié)點結(jié)點x是葉子結(jié)點但是葉子結(jié)點但value值在表值在表PT中不是最大中不是最大),則令則令down=value，并且將表，并且將表PT中所有小于

16、中所有小于value的結(jié)點刪除；的結(jié)點刪除；分支限界法的設(shè)計思想分支限界法的設(shè)計思想n目標(biāo)函數(shù)目標(biāo)函數(shù)“界界”的特性的特性n問題的解向量為問題的解向量為X=(x1, x2, , xn)，其中，其中，xi 的取值范圍的取值范圍為某個有窮集合為某個有窮集合Si，|Si|=ri（1in）n 是部分解，是部分解， 是相應(yīng)的界是相應(yīng)的界n對最小值問題對最小值問題，稱為下界，意思是，稱為下界，意思是向下搜索所可能取向下搜索所可能取得得的值的值最小不會小于這些下界最小不會小于這些下界。若。若X=(x1, x2, , xn)是是所得到的部分解，滿足：所得到的部分解，滿足：),()(211kxxxx),(),(

17、211kxxxboundxbound),(),()(21211kxxxboundxxboundxbound分支限界法的設(shè)計思想分支限界法的設(shè)計思想n對最大值問題對最大值問題，稱為上界，意思是向下搜索所可能取，稱為上界，意思是向下搜索所可能取得的值最大不會大于這些上界。若得的值最大不會大于這些上界。若 是所得到的部分解，滿足：是所得到的部分解，滿足：),(21kxxxX),(),()(21211kxxxboundxxboundxbound分支限界法的設(shè)計思想分支限界法的設(shè)計思想分支限界法的設(shè)計思想分支限界法的設(shè)計思想n用分支限界法求解問題的關(guān)鍵用分支限界法求解問題的關(guān)鍵n如何確定合適的如何確定合

18、適的限界函數(shù)限界函數(shù)限界函數(shù)用于估算結(jié)點的目標(biāo)函數(shù)的可能取值。好的限界函數(shù)用于估算結(jié)點的目標(biāo)函數(shù)的可能取值。好的限界函數(shù)不僅計算簡單，還要保證最優(yōu)解在搜索空間限界函數(shù)不僅計算簡單，還要保證最優(yōu)解在搜索空間中，更重要的是能盡早對超出目標(biāo)函數(shù)界的結(jié)點進(jìn)行中，更重要的是能盡早對超出目標(biāo)函數(shù)界的結(jié)點進(jìn)行剪枝，減少搜索空間。有時需要對具體的問題實例進(jìn)剪枝，減少搜索空間。有時需要對具體的問題實例進(jìn)行大量實驗才能確定一個合理的限界函數(shù)。行大量實驗才能確定一個合理的限界函數(shù)。n如何組織如何組織待處理結(jié)點表待處理結(jié)點表為提高查找極值的效率，待處理結(jié)點表為提高查找極值的效率，待處理結(jié)點表PT可采用堆或可采用堆或優(yōu)

19、先隊列的形式存儲。優(yōu)先隊列的形式存儲。分支限界法的設(shè)計思想分支限界法的設(shè)計思想n用分支限界法求解問題的關(guān)鍵（續(xù)）用分支限界法求解問題的關(guān)鍵（續(xù)）n如何確定最優(yōu)解中如何確定最優(yōu)解中的各個分量的各個分量分支限界法對問題的解空間樹中結(jié)點的處理是跳躍式分支限界法對問題的解空間樹中結(jié)點的處理是跳躍式的，回溯也不是單純地沿著雙親結(jié)點一層一層向上回的，回溯也不是單純地沿著雙親結(jié)點一層一層向上回溯，因此當(dāng)搜索到最優(yōu)解（葉子結(jié)點）時，卻無法求溯，因此當(dāng)搜索到最優(yōu)解（葉子結(jié)點）時，卻無法求得該葉子結(jié)點對應(yīng)的最優(yōu)解中的各個分量。解決方法：得該葉子結(jié)點對應(yīng)的最優(yōu)解中的各個分量。解決方法：n對每個擴(kuò)展結(jié)點保存根結(jié)點到該

20、結(jié)點的路徑；對每個擴(kuò)展結(jié)點保存根結(jié)點到該結(jié)點的路徑；n在搜索過程中構(gòu)建搜索經(jīng)過的樹結(jié)構(gòu)，在求得最優(yōu)在搜索過程中構(gòu)建搜索經(jīng)過的樹結(jié)構(gòu)，在求得最優(yōu)解時，從葉子結(jié)點不斷回溯到根結(jié)點，以確定最優(yōu)解時，從葉子結(jié)點不斷回溯到根結(jié)點，以確定最優(yōu)解中的各個分量。解中的各個分量。分支限界法的設(shè)計思想分支限界法的設(shè)計思想(c) 擴(kuò)展結(jié)點擴(kuò)展結(jié)點5后后 (d) 擴(kuò)展結(jié)點擴(kuò)展結(jié)點6 后，最優(yōu)解為后，最優(yōu)解為(1,0,1,0)65 圖圖9.3 方法確定方法確定0/1背包問題最優(yōu)解的各分量背包問題最優(yōu)解的各分量(a) 擴(kuò)展根結(jié)點后擴(kuò)展根結(jié)點后 (b) 擴(kuò)展結(jié)點擴(kuò)展結(jié)點2后后(0,76) (0,60)PTST(0,60)

21、(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è)計思想分支限界法的設(shè)計思想9.1 概概 述述 9.1.1 分支限界法的設(shè)計思想分支限界法的設(shè)計思想9.1.2 分支限界法的時間性能分支限界法的時間性能n與回溯法相同點與回溯法相同點n分支限界法分支限界法和和回溯法回溯法實際上都是基于蠻力法，遍歷具有實際上都是基于蠻力法，遍歷具有指數(shù)階個結(jié)點的解空間樹指數(shù)階個結(jié)點的解空間樹n在最壞情況下，時間復(fù)雜性肯定為指數(shù)階在最壞情況下，時間

22、復(fù)雜性肯定為指數(shù)階2n或或nnn與回溯法不同點與回溯法不同點n分支限界法分支限界法首先擴(kuò)展解空間樹中的上層結(jié)點首先擴(kuò)展解空間樹中的上層結(jié)點，并用，并用限界限界函數(shù)大范圍剪枝函數(shù)大范圍剪枝n根據(jù)限界函數(shù)根據(jù)限界函數(shù)不斷調(diào)整搜索方向不斷調(diào)整搜索方向，選擇最有可能取得最，選擇最有可能取得最優(yōu)解的子樹優(yōu)先進(jìn)行搜索優(yōu)解的子樹優(yōu)先進(jìn)行搜索n如果選擇了結(jié)點的合理如果選擇了結(jié)點的合理擴(kuò)展順序擴(kuò)展順序以及設(shè)計以及設(shè)計好的限界函數(shù)好的限界函數(shù)，分支界限法分支界限法可以快速得到問題的解可以快速得到問題的解9.1.2 分支限界法的時間性能分支限界法的時間性能 n分支限界法的代價分支限界法的代價n首先，設(shè)計首先，設(shè)計一

23、個好的限界函數(shù)通常需要花費更多的時間一個好的限界函數(shù)通常需要花費更多的時間計算相應(yīng)的目標(biāo)函數(shù)值計算相應(yīng)的目標(biāo)函數(shù)值，而且對于具體的問題實例，通，而且對于具體的問題實例，通常需要進(jìn)行大量實驗，才能確定一個好的限界函數(shù)；常需要進(jìn)行大量實驗，才能確定一個好的限界函數(shù)；n其次，分支限界法其次，分支限界法對解空間樹中結(jié)點的處理是跳躍式的對解空間樹中結(jié)點的處理是跳躍式的，因此，在搜索到某個葉子結(jié)點得到最優(yōu)值時，為了從該因此，在搜索到某個葉子結(jié)點得到最優(yōu)值時，為了從該葉子結(jié)點求出對應(yīng)的最優(yōu)解中的各個分量，需要對每個葉子結(jié)點求出對應(yīng)的最優(yōu)解中的各個分量，需要對每個擴(kuò)展結(jié)點保存該結(jié)點到根結(jié)點的路徑擴(kuò)展結(jié)點保存該

24、結(jié)點到根結(jié)點的路徑，或者在搜索過程，或者在搜索過程中構(gòu)建搜索經(jīng)過的樹結(jié)構(gòu)，這使得中構(gòu)建搜索經(jīng)過的樹結(jié)構(gòu)，這使得算法的設(shè)計較為復(fù)雜算法的設(shè)計較為復(fù)雜；n再次，分支限界法為維護(hù)再次，分支限界法為維護(hù)PT 表表需要較大的存儲空間需要較大的存儲空間，在，在最壞情況下，分支限界法需要的最壞情況下，分支限界法需要的空間復(fù)雜性是指數(shù)階空間復(fù)雜性是指數(shù)階。 9.1.2 分支限界法的時間性能分支限界法的時間性能 第第9章章 分支限界法分支限界法 9.1 概概 述述 9.2 圖問題中的分支限界法圖問題中的分支限界法9.3 組合問題中的分支限界法組合問題中的分支限界法9.2 圖問題中的分支限界法圖問題中的分支限界法

25、 9.2.1 TSP問題問題 9.2.2 多段圖的最短路徑問題多段圖的最短路徑問題9.2.1 TSP問題問題 TSP TSP問題是指旅行家要旅行問題是指旅行家要旅行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 無向圖及其代價矩陣無向圖及其代價矩陣n確定上界確定上界ubn采用貪心法求得近似解為采

26、用貪心法求得近似解為: :135421 ub=1+2+3+7+3=16 這可以作為這可以作為TSP問題的上界問題的上界n確定下界確定下界lbn把矩陣中每一行最小的元素相加，可以得到一個簡單的下界把矩陣中每一行最小的元素相加，可以得到一個簡單的下界: : lb=1+3+1+3+2=10n一個信息量更大的下界：把矩陣中每一行最小的兩個元素相加再一個信息量更大的下界：把矩陣中每一行最小的兩個元素相加再除以除以2，再對這個結(jié)果向上取整，就得到了一個合理的下界，再對這個結(jié)果向上取整，就得到了一個合理的下界: : lb=(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14 則，目標(biāo)函數(shù)的界

27、則，目標(biāo)函數(shù)的界:lb, ub=14, 16注意：該解并不是一個合法的選擇（即沒構(gòu)成哈密頓回路），僅給注意：該解并不是一個合法的選擇（即沒構(gòu)成哈密頓回路），僅給出了一個出了一個參考下界參考下界。9.2 TSP問題問題271563134253984n 部分解的目標(biāo)函數(shù)值的計算方法部分解的目標(biāo)函數(shù)值的計算方法n假設(shè)當(dāng)前已確定的路徑為假設(shè)當(dāng)前已確定的路徑為U=(r1,r2,rk), 則：則： 例如圖例如圖10.4所示無向圖，如果部分解包含頂點所示無向圖，如果部分解包含頂點U=(1, 4)，則該，則該部分解的下界是部分解的下界是: lb=(2*5+(1+3)+(3+6)+(1+2)+(2+3)/2=1

28、6UrUrjikiiiijrrrrclb2/ )2(111行最小的兩個元素素行不在路徑上的最小元分支限界法求解分支限界法求解TSP問題示例問題示例271563134253984C= 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 nTSP問題的搜索過程問題的搜索過程n根結(jié)點根結(jié)點1，加入表，加入表PT，為擴(kuò)展結(jié)點，為擴(kuò)展結(jié)點 目標(biāo)函數(shù): lb=(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14n考察孩子結(jié)點。結(jié)點考察孩子結(jié)點。結(jié)點2:C1C2, 路徑長度為3 目標(biāo)函數(shù):lb=(2*3+(1+6)+(1+2)+(3+4)+(2+3)/2=14 將

29、結(jié)點2加入待處理結(jié)點表PT中；n在結(jié)點在結(jié)點3：C1C3，路徑長度為1 目標(biāo)函數(shù):lb=(2*1+(3+2)+(3+6)+(3+4)+(2+3)/2=14 將結(jié)點3加入表PT中n在結(jié)點在結(jié)點4：C1C4，路徑長度為5 目標(biāo)函數(shù):lb=(2*5+(1+3)+(3+6)+(1+2)+(2+3)/2=16 將結(jié)點4加入表PT中 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 1111,(2 ) / 2jkiiijiikrUlbc rrrr行不在路徑上的最小元素行最小的兩個元素n在結(jié)點在結(jié)點5：C1C5，路徑長度為8 目標(biāo)函數(shù)：lb=(2*8+(1+2)+(3+6)+(

30、1+2)+(3+4)/2=19 超出目標(biāo)函數(shù)的界，將結(jié)點5丟棄；n處理結(jié)點處理結(jié)點2的孩子結(jié)點。結(jié)點的孩子結(jié)點。結(jié)點6,C1C2C3,路徑長度為3+6 目標(biāo)函數(shù):lb=(2*9+(1+1)+(3+4)+(2+3)/2=16 將結(jié)點6加入表PT中n在結(jié)點在結(jié)點7， C1 C2C4，路徑長度為3+7 目標(biāo)函數(shù)lb=(2*10+(1+3)+(1+2)+(2+3)/2=16 將結(jié)點7加入表PT中分支限界法求解分支限界法求解TSP問題示例問題示例在表在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點中選取目標(biāo)函數(shù)值極小的結(jié)點2優(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

31、9 2 3 n在結(jié)點在結(jié)點8， C1 C2C5 ，路徑長度為3+9目標(biāo)函數(shù)目標(biāo)函數(shù): lb=(2*12+(1+2)+(1+2)+(3+4)/2=19超出目標(biāo)函數(shù)的界，將結(jié)點超出目標(biāo)函數(shù)的界，將結(jié)點8丟棄丟棄n處理結(jié)點處理結(jié)點3的孩子。結(jié)點的孩子。結(jié)點9， C1 C3C2 ，路徑長度為1+6 目標(biāo)函數(shù)值目標(biāo)函數(shù)值:lb=(2*7+(3+3)+(3+4)+(2+3)/2=16 將結(jié)點將結(jié)點9加入表加入表PT中中n在結(jié)點在結(jié)點10， C1 C3C4 ，路徑長度為1+4 目標(biāo)函數(shù)目標(biāo)函數(shù):lb=(2*5+(3+3)+(3+6)+(2+3)/2=15 將結(jié)點將結(jié)點10加入表加入表PT中中分支限界法求解分

32、支限界法求解TSP問題示例問題示例在表在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點中選取目標(biāo)函數(shù)值極小的結(jié)點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 n在結(jié)點在結(jié)點11， C1C3C5 ，路徑長度為1+2 目標(biāo)函數(shù)值:lb=(2*3+(3+3)+(3+6)+(3+4)/2=14 將結(jié)點11加入表PT中在表在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點中選取目標(biāo)函數(shù)值極小的結(jié)點11優(yōu)先進(jìn)行搜索優(yōu)先進(jìn)行搜索n處理結(jié)點處理結(jié)點11的孩子。結(jié)點的孩子。結(jié)點12，C1C3C5C2 ，路徑長度為1+2+9，目標(biāo)函數(shù)值:lb=(2*12+(3+3)+(3+4)/2

33、=19 超出目標(biāo)函數(shù)的界，將結(jié)點12丟棄n在結(jié)點在結(jié)點13， C1C3 C5C4 ，路徑長度為1+2+3 目標(biāo)函數(shù)值：lb=(2*6+(3+4)+(3+6)/2=14,將結(jié)點13加入表PT中在表在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點中選取目標(biāo)函數(shù)值極小的結(jié)點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é)點中選取目標(biāo)函數(shù)值極小的結(jié)點10優(yōu)先進(jìn)行搜索優(yōu)先進(jìn)行搜索n處理結(jié)點處理結(jié)點13的孩子。結(jié)點的孩子。結(jié)點14， C1C3 C5C4C2 ，路徑長度為1+2+3+7，目標(biāo)函數(shù)值:lb=(2*13+(3+3

34、)/2=16由于結(jié)點14為葉子結(jié)點，得到一個可行解其路徑長度為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é)點中選取目標(biāo)函數(shù)值極小的結(jié)點16優(yōu)先進(jìn)行搜索優(yōu)先進(jìn)行搜索n處理結(jié)點處理結(jié)點10的孩子。結(jié)點的孩子。結(jié)點15，C1C3 C4C2，長，長度度12。 目標(biāo)函數(shù):lb=(2*12+(3+3)+(2+3)/2=18 超出目標(biāo)函數(shù)的界，將結(jié)點15丟棄n結(jié)點結(jié)點16， C1C3 C4C5 ，長度，長度8 目標(biāo)函數(shù):lb=(2*

35、8+(3+2)+(3+6)/2=15 將結(jié)點16加入表PT中n處理結(jié)點處理結(jié)點16的孩子。結(jié)點的孩子。結(jié)點17,C1C3C4C5C2,長度長度17，目標(biāo)函數(shù):lb =(2*17+(3+3)/2=20,超目標(biāo)函數(shù)的界，結(jié)點17丟棄表表PT中目標(biāo)函數(shù)值均為中目標(biāo)函數(shù)值均為16，且已找到葉子結(jié)點，且已找到葉子結(jié)點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

36、=1932lb=1634lb=1535lb=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é)點擴(kuò)展結(jié)點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é)點后的狀態(tài)擴(kuò)展根結(jié)點后的狀態(tài) (b) 擴(kuò)展結(jié)點擴(kuò)展結(jié)點2后的狀態(tài)后的

37、狀態(tài)(c) 擴(kuò)展結(jié)點擴(kuò)展結(jié)點3后的狀態(tài)后的狀態(tài)(d) 擴(kuò)展結(jié)點擴(kuò)展結(jié)點11后的狀態(tài)后的狀態(tài)(e) 擴(kuò)展結(jié)點擴(kuò)展結(jié)點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,

38、 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 (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é)點擴(kuò)展結(jié)點10后的狀態(tài)后的狀態(tài)算法算法9.1TSP問題問題輸入：圖輸入：圖G（V，E）輸出：最短哈密爾頓回路輸出：最短哈密爾頓回路 1根據(jù)限界函數(shù)計算目標(biāo)函數(shù)的下界根據(jù)限界函數(shù)計算目標(biāo)函數(shù)的下界down；采用貪心法得到上界；采用貪心

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

40、8所示，具體的搜索過程如下（加黑表示該路徑上已經(jīng)確定的邊）：（1）在根結(jié)點1，計算目標(biāo)函數(shù)的值為14，將根結(jié)點加入表PT；（2）處理根結(jié)點每個孩子結(jié)點。結(jié)點2，第1段選擇邊，目標(biāo)函數(shù)值為lb=4+8+5+3=20，超出目標(biāo)函數(shù)的界，將結(jié)點2丟棄；在結(jié)點3，第1段選擇邊，目標(biāo)函數(shù)值為lb=2+7+5+3=17，將結(jié)點3加入表PT；在結(jié)點4，第1段選擇邊，目標(biāo)函數(shù)值為lb=3+4+5+3=15，將結(jié)點4加入表PT中；（3）在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點4優(yōu)先進(jìn)行搜索；1203456789492387884756866537（4）在結(jié)點5，第2段選擇邊，目標(biāo)函數(shù)值為lb=3+4+6+3=16，將

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

42、lb=15圖圖9.8 分支限界法求解多段圖的最短路徑問題示例分支限界法求解多段圖的最短路徑問題示例(表示該結(jié)點被丟棄，結(jié)點上方的數(shù)組表示搜索順序表示該結(jié)點被丟棄，結(jié)點上方的數(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

43、 0/1背包問題背包問題n問題描述問題描述 任務(wù)分配問題要求把任務(wù)分配問題要求把n項任務(wù)分配給項任務(wù)分配給n個人，每個人完成個人，每個人完成每項任務(wù)的成本不同，要求分配總成本最小的最優(yōu)分配方每項任務(wù)的成本不同，要求分配總成本最小的最優(yōu)分配方案。如圖案。如圖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ù)分配問題的成本矩陣n如何求最優(yōu)分配成本的上界如何求最

44、優(yōu)分配成本的上界Up和下界和下界Downn獲得上界獲得上界UPn如考慮以如考慮以矩陣的對角線矩陣的對角線作為一個可行解作為一個可行解:任務(wù)任務(wù)1人員人員a、任務(wù)、任務(wù)2給人員給人員b任務(wù)任務(wù)3人員人員c、任務(wù)、任務(wù)4人員人員d 成本成本： 9+4+1+4=18n或應(yīng)用貪心法求得一個近似解：或應(yīng)用貪心法求得一個近似解： 任務(wù)任務(wù)2人員人員a、任務(wù)、任務(wù)3人員人員b 任務(wù)任務(wù)1人員人員c、任務(wù)、任務(wù)4人員人員d成本成本: :2+3+5+4=14 14 是一個更好的上界是一個更好的上界9.3.2 任務(wù)分配問題任務(wù)分配問題 C9 2 7 86 4 3 75 8 1 87 6 9 4任務(wù)任務(wù)1 任務(wù)任務(wù)

45、2 任務(wù)任務(wù)3 任務(wù)任務(wù)4人員人員a人員人員b人員人員c人員人員d圖圖9.10 任務(wù)分配問題的成本矩陣任務(wù)分配問題的成本矩陣n獲得下界獲得下界Downn考慮考慮n人員人員a所有任務(wù)的最小代價是所有任務(wù)的最小代價是2n人員人員b執(zhí)行所有任務(wù)的最小代價是執(zhí)行所有任務(wù)的最小代價是3n人員人員c執(zhí)行所有任務(wù)的最小代價是執(zhí)行所有任務(wù)的最小代價是1n人員人員d執(zhí)行所有任務(wù)的最小代價是執(zhí)行所有任務(wù)的最小代價是4 每行取最小元素，其成本下界：每行取最小元素，其成本下界：2+3+1+4=10 則上下界為：則上下界為：10, 14 注意：這個解并不是一個合法的選擇注意：這個解并不是一個合法的選擇 因為：因為：3、

46、1來自于矩陣同一列，僅給出一個參考下界來自于矩陣同一列，僅給出一個參考下界9.3.2 任務(wù)分配問題任務(wù)分配問題 n設(shè)當(dāng)前已對人員設(shè)當(dāng)前已對人員1 1i i分配了任務(wù)，并且獲得了成本分配了任務(wù)，并且獲得了成本v v，則限界函數(shù)，則限界函數(shù)可以定義為：可以定義為： （式（式9.49.4）n搜索過程搜索過程n在根結(jié)點在根結(jié)點1 沒有分配任務(wù)，限界函數(shù)函數(shù)值為:lb=2+3+1+4=10n在結(jié)點在結(jié)點2 將J1人員a，獲得的成本為9 目標(biāo)函數(shù)值為: lb=9 + (3+1+4)=17 超出目標(biāo)函數(shù)的界10, 14，將結(jié)點2丟棄nikkvlb1行的最小值第9.3.2 任務(wù)分配問題任務(wù)分配問題 C9 2

47、7 86 4 3 75 8 1 87 6 9 4人員人員a人員人員b人員人員c人員人員d圖圖9.11 分支限界法求解任務(wù)分配問題示例分支限界法求解任務(wù)分配問題示例(表示該結(jié)點被丟棄，結(jié)點上方的數(shù)組表示搜索順序表示該結(jié)點被丟棄，結(jié)點上方的數(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

48、任務(wù)任務(wù)4人員人員a人員人員b人員人員c人員人員d任務(wù)1任務(wù)4任務(wù)2任務(wù)1任務(wù)3任務(wù)4任務(wù)1任務(wù)49.3.2 任務(wù)分配問題任務(wù)分配問題 n搜索過程搜索過程n在結(jié)點在結(jié)點3 將J2人員a，獲得的成本為2 目標(biāo)函數(shù)值:lb=2 + (3+1+4)=10 將結(jié)點3 -PT表中n在結(jié)點在結(jié)點4 將J3人員a，獲得的成本為7 目標(biāo)函數(shù)值:lb=7 + (3+1+4)=15 超出目標(biāo)函數(shù)的界10, 14，將結(jié)點4丟棄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é)點在

49、結(jié)點5 將J4人員a，獲得的成本為8 目標(biāo)函數(shù)值:lb=8 + (3+1+4)=16 超出目標(biāo)函數(shù)的界10, 14，將結(jié)點5丟棄n在結(jié)點在結(jié)點6 將J2人員a,J1人員b，獲得的成本為2+6=8 目標(biāo)函數(shù)值:lb=8+(1+4)13 將結(jié)點6加入表PT中在表在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點中選取目標(biāo)函數(shù)值極小的結(jié)點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 4任務(wù)任務(wù)1 任務(wù)任務(wù)2 任務(wù)任務(wù)3 任務(wù)任務(wù)4人員人員a人員人員b人員人員c人員人員dn在結(jié)點在結(jié)點7 將J2人員a，J3人員b，獲得的成本為2+3=5 目標(biāo)函數(shù)

50、值:lb=5+(1+4)10 將結(jié)點7加入表PT中n在結(jié)點在結(jié)點8 將J2人員a，J4人員b，獲得的成本為2+7=9 目標(biāo)函數(shù)值:lb=9+(1+4)14 將結(jié)點8加入表PT中； 在表在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點中選取目標(biāo)函數(shù)值極小的結(jié)點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人員人員dn在結(jié)點在結(jié)點9 將J2人員a，J3人員b ，J1人員c，獲得的成本為5+5=10 目標(biāo)函數(shù)值:lb=10+4=14 將結(jié)點9加入表PT中n在結(jié)點在結(jié)

51、點10 將J2人員a，J3人員b ，J4人員c，獲得的成本為5+8=13 目標(biāo)函數(shù)值:lb=13+4=17 超出目標(biāo)函數(shù)的界10, 14，將結(jié)點10丟棄在表在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點中選取目標(biāo)函數(shù)值極小的結(jié)點6 6優(yōu)先進(jìn)行搜索優(yōu)先進(jìn)行搜索9.3.2 任務(wù)分配問題任務(wù)分配問題 n在結(jié)點在結(jié)點11 將J2人員a,J1人員b， J3人員c，獲得的成本為8+1=9 目標(biāo)函數(shù)值:lb=9+4=13 將結(jié)點11加入表PT中n在結(jié)點在結(jié)點12 將J2人員a,J1人員b，J4人員c，獲得的成本為8+8=16 目標(biāo)函數(shù)值:lb=16+4=20 超出目標(biāo)函數(shù)的界10, 14，將結(jié)點12丟棄；在表在表PT中

52、選取目標(biāo)函數(shù)值極小的結(jié)點中選取目標(biāo)函數(shù)值極小的結(jié)點1111優(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ù)4n在結(jié)點在結(jié)點13 將J2人員a,J1人員b，J3人員c ，J4人員d 獲得的成本為9+4=13 目標(biāo)函數(shù)值為:lb=13 由于結(jié)點13是葉子結(jié)點，同時結(jié)點13的目標(biāo)函數(shù)值是表PT中的極小值， 所以，結(jié)點13對應(yīng)的解即是問題的最優(yōu)解 搜索結(jié)束。n構(gòu)建搜索經(jīng)過的樹結(jié)構(gòu)構(gòu)建搜索經(jīng)過的樹結(jié)構(gòu)n取出表取出表PT中最小值結(jié)點進(jìn)行擴(kuò)充時，并將最小值結(jié)點存中最小值結(jié)點進(jìn)行擴(kuò)充時，并將最小值

53、結(jié)點存儲到儲到ST中，表中，表PT 和表和表 ST 的數(shù)據(jù)結(jié)構(gòu)為：的數(shù)據(jù)結(jié)構(gòu)為： (人員人員i-1分配的任務(wù)分配的任務(wù),lb)9.3.2 任務(wù)分配問題任務(wù)分配問題 (人員人員i-1分配的任務(wù)分配的任務(wù),lb)(e) 擴(kuò)展結(jié)點擴(kuò)展結(jié)點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é)點后的狀態(tài)擴(kuò)展根結(jié)點后

54、的狀態(tài) (b) 擴(kuò)展結(jié)點擴(kuò)展結(jié)點3后的狀態(tài)后的狀態(tài) PTSTPTST PTST (c) 擴(kuò)展結(jié)點擴(kuò)展結(jié)點7后的狀態(tài)后的狀態(tài) (d) 擴(kuò)展結(jié)點擴(kuò)展結(jié)點6后的狀態(tài)后的狀態(tài)(2,14) (3,14) (3,13)PTSTPTST 9.3.2 任務(wù)分配問題任務(wù)分配問題 算法算法9.3任務(wù)分配問題任務(wù)分配問題 1根據(jù)限界函數(shù)計算目標(biāo)函數(shù)的根據(jù)限界函數(shù)計算目標(biāo)函數(shù)的 down；采用貪心法得到；采用貪心法得到up； 2將待處理結(jié)點表將待處理結(jié)點表PT 初始化為空；初始化為空； 3for (i=1; i=1) 5.1 xk=1; 5.2 while (xk=n) 5.2.1 如果人員如果人員k 分配任務(wù)分配任

55、務(wù)xk 不發(fā)生沖突，則不發(fā)生沖突，則 5.2.1.1 根據(jù)式根據(jù)式9.4 計算目標(biāo)函數(shù)值計算目標(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é)點的且葉子結(jié)點的lb值在表值在表PT中最小，中最小， 則輸出該葉子結(jié)點對應(yīng)的最優(yōu)解；則輸出該葉子結(jié)點對應(yīng)的最優(yōu)解； 5.4 否則，如果否則，如果k= =n且表且表PT中的葉子結(jié)點的中的葉子結(jié)點的lb值不是最小，則值不是最小，則 5.4.1 up=表表

56、PT中的葉子結(jié)點最小的中的葉子結(jié)點最小的lb值值; 5.4.2 將表將表PT中超出目標(biāo)函數(shù)界的結(jié)點刪除；中超出目標(biāo)函數(shù)界的結(jié)點刪除； 5.5 i=表表PT中中l(wèi)b最小的結(jié)點的最小的結(jié)點的xk值；值； 5.6 k=表表PT中中l(wèi)b最小的結(jié)點的最小的結(jié)點的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背包問題背包問題n問題描述問題描述nn個作業(yè)的集合個作業(yè)的集合J=J1, J2, , Jn，

57、n每個作業(yè)都有每個作業(yè)都有3項任務(wù)分別在項任務(wù)分別在3臺機(jī)器上完成臺機(jī)器上完成nJi 需要機(jī)器需要機(jī)器j 的處理時間為的處理時間為tij（1in, 1j3）n作業(yè)處理順序作業(yè)處理順序: 機(jī)器機(jī)器1處理處理機(jī)器機(jī)器2處理處理機(jī)器機(jī)器3處理處理n批處理作業(yè)調(diào)度問題批處理作業(yè)調(diào)度問題?n要求確定這要求確定這 n 個作業(yè)的最優(yōu)處理順序使得從第個作業(yè)的最優(yōu)處理順序使得從第1個作業(yè)個作業(yè)在機(jī)器在機(jī)器1上處理開始，到最后一個作業(yè)在機(jī)器上處理開始，到最后一個作業(yè)在機(jī)器3上處理結(jié)上處理結(jié)束所需的時間最少。束所需的時間最少。n最優(yōu)調(diào)度原則最優(yōu)調(diào)度原則使機(jī)器使機(jī)器1沒有空閑時間，且機(jī)器沒有空閑時間，且機(jī)器2和和3的

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

59、理順序為: :J4 J1 J3 J2，調(diào)度方案，調(diào)度方案: :J4:7 J1:5 J3:9 J2:10機(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上處理時間最短的作業(yè)。例如，以作業(yè) Ji 開始的處理順序，估算處理所需的

60、最短時間是最短時間是：tij: 表示表示 Ji 需要機(jī)器需要機(jī)器 j 的處理時間的處理時間(1in, 1j3)9.3.3 批處理作業(yè)調(diào)度問題批處理作業(yè)調(diào)度問題作業(yè)Ji在機(jī)器1上的處理時間作業(yè)作業(yè)1作業(yè)作業(yè)n在機(jī)器2上的處理時間總和在機(jī)器3上處理時間最短的作業(yè)n目標(biāo)函數(shù)下界計算目標(biāo)函數(shù)下界計算lb若已安排了k-1個作業(yè)集合，即：M 1, 2, , k-1，|M|=k-1sum1k-1：機(jī)器機(jī)器1 1完成k-1個作業(yè)的處理時間sum2k-1：機(jī)器2完成k-1個作業(yè)的處理時間現(xiàn)要處理作業(yè)k，此時，該部分解的目標(biāo)函數(shù)值的下界lb計算方法如下：（1）sum1k=sum1k-1+ tk1（2）（3）sum