第9章-分支限界法

第9章 分支限界法

BranchandBoundMethod算法設(shè)計(jì)與分析—本科生課程DesignandAnalysisofAlgorithm邱釗海南大學(xué)信息科學(xué)技術(shù)學(xué)院CollegeofInformationScienceandTechnology,HainanUniversityqiuzhao73@2023/2/12教學(xué)重點(diǎn)分支限界法的設(shè)計(jì)思想，各種經(jīng)典問(wèn)題的限界函數(shù)教學(xué)難點(diǎn)各種經(jīng)典問(wèn)題的限界函數(shù)以及限界算法教學(xué)內(nèi)容及目標(biāo)知識(shí)點(diǎn)教學(xué)要求了解理解掌握熟練掌握分支限界法的設(shè)計(jì)思想√分支限界法的時(shí)空性能√TSP問(wèn)題√多段圖的最短路徑問(wèn)題√0/1背包問(wèn)題√任務(wù)分配問(wèn)題√批處理作業(yè)調(diào)度問(wèn)題√學(xué)習(xí)目標(biāo)Chapter8BackTrackMethod2023/2/1BranchandBoundMethod3第9章分支限界法

9.1概

述

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

述

2023/2/1BranchandBoundMethod59.1概

述

9.1.1分支限界法的設(shè)計(jì)思想9.1.2分支限界法的時(shí)間性能2023/2/1BranchandBoundMethod6回溯法存在的問(wèn)題雖用剪枝減少了搜索空間，但按深度優(yōu)先策略機(jī)械地進(jìn)行，搜索是盲目的。如0/1背包問(wèn)題。首先將目標(biāo)函數(shù)初始化為最大值，目標(biāo)函數(shù)只有在有一個(gè)可行解（第一個(gè)葉子）后才有意義，此后的搜索相對(duì)來(lái)說(shuō)才有方向，所以從搜索的整個(gè)過(guò)程來(lái)看還是盲目的。如TSP問(wèn)題（圖8.6）。分支限界法先確定一個(gè)合理的限界函數(shù)由限界函數(shù)確定目標(biāo)函數(shù)的界[down,up]仍以窮舉法的解空間樹(shù)為基礎(chǔ)，但以廣度優(yōu)先的原理搜索該結(jié)點(diǎn)的所有孩子結(jié)點(diǎn)，分別估算這些孩子結(jié)點(diǎn)的目標(biāo)函數(shù)的可能取值分支限界法的設(shè)計(jì)思想2023/2/1BranchandBoundMethod7如果某孩子結(jié)點(diǎn)的目標(biāo)函數(shù)可能取值超出目標(biāo)函數(shù)的界，則將其丟棄，因?yàn)閺倪@個(gè)結(jié)點(diǎn)生成的解不會(huì)比目前已經(jīng)得到的解更好；否則，將其加入待處理結(jié)點(diǎn)表（表PT）依次從表PT中選取使目標(biāo)函數(shù)的值取極值的結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，重復(fù)上述過(guò)程，直到找到最優(yōu)解。目標(biāo)函數(shù)的界[down,up]的確定對(duì)最大化問(wèn)題Up由限界函數(shù)確定，down由某種啟發(fā)方式得到,如貪心算法對(duì)最小化問(wèn)題down由限界函數(shù)確定，up由某種啟發(fā)方式得到,如貪心算法分支限界法的設(shè)計(jì)思想2023/2/1BranchandBoundMethod8例：0/1背包問(wèn)題。假設(shè)有4個(gè)物品，其重量分別為(4,7,5,3)，價(jià)值分別為(40,42,25,12)，背包容量W=10。首先，將給定物品按單位重量?jī)r(jià)值從大到小排序，結(jié)果如下：物品重量(w)價(jià)值(v)價(jià)值/重量(v/w)144010274263525543124分支限界法的設(shè)計(jì)思想2023/2/1BranchandBoundMethod9確定上下界

down：應(yīng)用貪心法求得近似解為(1,0,1,0)，獲得的價(jià)值為65，這可以作為0/1背包問(wèn)題的下界。up：考慮最好情況，背包中全部裝入第1個(gè)物品且可以將背包裝滿，則可得到一個(gè)簡(jiǎn)單上界的計(jì)算方法：

up=W×(v1/w1)=10×10=100則目標(biāo)函數(shù)的界：[65,100]限界函數(shù)為：分支限界法的設(shè)計(jì)思想2023/2/1BranchandBoundMethod10×w=0,v=0ub=100w=4,v=40ub=76w=0,v=0ub=60w=11無(wú)效解w=4,v=40ub=70w=9,v=65ub=69w=4,v=40ub=64w=12無(wú)效解w=9,v=65ub=6523456789×1××PT表圖9.10/1背包問(wèn)題分支限界法的設(shè)計(jì)思想2023/2/1BranchandBoundMethod11分支限界法的搜索過(guò)程如下：在根結(jié)點(diǎn)1

沒(méi)有物品裝入背包，w=0,v=0

限界函數(shù)值：ub=0+(10-0)=10×10=100在結(jié)點(diǎn)2

物品1裝入背包，w=w1=4，v=40

目標(biāo)函數(shù)值:ub=40+(10-4)×6=76

將結(jié)點(diǎn)2加入待處理結(jié)點(diǎn)表PT中在結(jié)點(diǎn)3

物品1不裝入背包，w=0,v=0

目標(biāo)函數(shù)值:10ub=0+(10-0)×6＝60<65，丟棄結(jié)點(diǎn)3在表PT中選取目標(biāo)函數(shù)值取得極大的結(jié)點(diǎn)2優(yōu)先進(jìn)行搜索；

分支限界法的設(shè)計(jì)思想2023/2/1BranchandBoundMethod12在結(jié)點(diǎn)4

物品2裝入背包，w=11>W，不滿足約束條件，將結(jié)點(diǎn)4丟棄在結(jié)點(diǎn)5

物品2不裝入背包，w=4,v=40與結(jié)點(diǎn)2相同目標(biāo)函數(shù)值為:ub=40+(10-4)×5=70

將結(jié)點(diǎn)5加入表PT中在結(jié)點(diǎn)6

物品3裝入背包，w=4+5=9，v=40+25=65

目標(biāo)函數(shù)值為:ub=65+(10-9)×4=69

將結(jié)點(diǎn)6加入表PT中在表PT中選取目標(biāo)函數(shù)值取得極大的結(jié)點(diǎn)5優(yōu)先進(jìn)行搜索分支限界法的設(shè)計(jì)思想2023/2/1BranchandBoundMethod13在結(jié)點(diǎn)7

物品3不裝入背包，w=4,v=40,與結(jié)點(diǎn)5相同目標(biāo)函數(shù)值為：ub=40+(10-4)×4＝64<65

丟棄結(jié)點(diǎn)7在結(jié)點(diǎn)8

物品4裝入背包，w=12>W,不滿足約束條件，將結(jié)點(diǎn)8丟棄；在結(jié)點(diǎn)9

物品4不裝入背包，w=9,v=65,與結(jié)點(diǎn)6相同目標(biāo)函數(shù)值為:ub=65+(W-w)*0=65

將結(jié)點(diǎn)9加入表PT中在表PT中選取目標(biāo)函數(shù)值取得極大的結(jié)點(diǎn)6優(yōu)先進(jìn)行搜索分支限界法的設(shè)計(jì)思想2023/2/1BranchandBoundMethod14結(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é)束在圖9.1的0/1背包問(wèn)題中，為了在搜索過(guò)程中構(gòu)建搜索經(jīng)過(guò)的樹(shù)結(jié)構(gòu)，設(shè)一個(gè)表PT，記錄搜索過(guò)程，如圖9.2。再設(shè)計(jì)了一表ST，從PT中取出最大值結(jié)點(diǎn)進(jìn)行擴(kuò)充時(shí)，將最大值結(jié)點(diǎn)存儲(chǔ)到表ST中，表PT和表ST的數(shù)據(jù)結(jié)構(gòu)為：

(物品i-1的選擇結(jié)果，<物品i,

物品i

的選擇結(jié)果>ub)

在搜索過(guò)程中表PT和表ST的狀態(tài)如圖9.2所示分支限界法的設(shè)計(jì)思想2023/2/1BranchandBoundMethod15(c)擴(kuò)展結(jié)點(diǎn)5后(d)擴(kuò)展結(jié)點(diǎn)6后，最優(yōu)解為(1,0,1,0)65

圖9.2方法②確定0/1背包問(wèn)題最優(yōu)解的各分量(a)擴(kuò)展根結(jié)點(diǎn)后(b)擴(kuò)展結(jié)點(diǎn)2后(0,<1,1>76)PTST(1,<2,0>70)PTST(0,<1,1>76)(0,<3,1>69)

PTST(0,<1,1>76)(1,<2,0>70)(1,<4,0>65)PTST(0,<1,1>76)(1,<2,0>70)(0,<3,1>69)9256分支限界法的設(shè)計(jì)思想2023/2/1BranchandBoundMethod16基本思想分支限界法常以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索問(wèn)題的解空間樹(shù)。在分支限界法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)。活結(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)。在這些兒子結(jié)點(diǎn)中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄，其余兒子結(jié)點(diǎn)被加入活結(jié)點(diǎn)表中。此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)（使目標(biāo)函數(shù)取得極值的結(jié)點(diǎn)）成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過(guò)程。這個(gè)過(guò)程一直持續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時(shí)為止。分支限界法的設(shè)計(jì)思想2023/2/1BranchandBoundMethod17分支限界法的一般過(guò)程

1．根據(jù)限界函數(shù)計(jì)算目標(biāo)函數(shù)的[down，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.1i=表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)且value值在表PT中最大），則將結(jié)點(diǎn)x對(duì)應(yīng)的解輸出，算法結(jié)束；4.2.4若(結(jié)點(diǎn)x是葉子結(jié)點(diǎn)但value值在表PT中不是最大),則令down=value，并且將表PT中所有小于value的結(jié)點(diǎn)刪除；分支限界法的設(shè)計(jì)思想2023/2/1BranchandBoundMethod18用分支限界法求解問(wèn)題的關(guān)鍵如何確定合適的限界函數(shù)限界函數(shù)用于估算結(jié)點(diǎn)的目標(biāo)函數(shù)的可能取值。好的限界函數(shù)不僅計(jì)算簡(jiǎn)單，還要保證最優(yōu)解在搜索空間中，更重要的是能盡早對(duì)超出目標(biāo)函數(shù)界的結(jié)點(diǎn)進(jìn)行剪枝，減少搜索空間。有時(shí)需要對(duì)具體的問(wèn)題實(shí)例進(jìn)行大量實(shí)驗(yàn)才能確定一個(gè)合理的限界函數(shù)。如何組織待處理結(jié)點(diǎn)表

為提高查找極值的效率，待處理結(jié)點(diǎn)表PT可采用堆或優(yōu)先隊(duì)列的形式存儲(chǔ)。分支限界法的設(shè)計(jì)思想2023/2/1BranchandBoundMethod19用分支限界法求解問(wèn)題的關(guān)鍵（續(xù)）如何確定最優(yōu)解中的各個(gè)分量

分支限界法對(duì)問(wèn)題的解空間樹(shù)中結(jié)點(diǎn)的處理是跳躍式的，回溯也不是單純地沿著雙親結(jié)點(diǎn)一層一層向上回溯，因此當(dāng)搜索到最優(yōu)解（葉子結(jié)點(diǎn)）時(shí)，卻無(wú)法求得該葉子結(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)，在求得最優(yōu)解時(shí)，從葉子結(jié)點(diǎn)不斷回溯到根結(jié)點(diǎn)，以確定最優(yōu)解中的各個(gè)分量。分支限界法的設(shè)計(jì)思想2023/2/1BranchandBoundMethod20(c)擴(kuò)展結(jié)點(diǎn)5后(d)擴(kuò)展結(jié)點(diǎn)6后，最優(yōu)解為(1,0,1,0)65

圖9.2方法②確定0/1背包問(wèn)題最優(yōu)解的各分量(a)擴(kuò)展根結(jié)點(diǎn)后(b)擴(kuò)展結(jié)點(diǎn)2后(0,<1,1>76)PTST(1,<2,0>70)PTST(0,<1,1>76)(0,<3,1>69)

PTST(0,<1,1>76)(1,<2,0>70)(1,<4,0>65)PTST(0,<1,1>76)(1,<2,0>70)(0,<3,1>69)9256分支限界法的設(shè)計(jì)思想2023/2/1BranchandBoundMethod219.1概

述

9.1.1分支限界法的設(shè)計(jì)思想9.1.2分支限界法的時(shí)間性能2023/2/1BranchandBoundMethod22與回溯法相同點(diǎn)分支限界法和回溯法實(shí)際上都是基于蠻力法，遍歷具有指數(shù)階個(gè)結(jié)點(diǎn)的解空間樹(shù)在最壞情況下，時(shí)間復(fù)雜性肯定為指數(shù)階2n或nn與回溯法不同點(diǎn)分支限界法首先擴(kuò)展解空間樹(shù)中的上層結(jié)點(diǎn)，并用限界函數(shù)大范圍剪枝根據(jù)限界函數(shù)不斷調(diào)整搜索方向，選擇最有可能取得最優(yōu)解的子樹(shù)優(yōu)先進(jìn)行搜索如果選擇了結(jié)點(diǎn)的合理擴(kuò)展順序以及設(shè)計(jì)好的限界函數(shù)，分支界限法可以快速得到問(wèn)題的解9.1.2分支限界法的時(shí)間性能

2023/2/1BranchandBoundMethod23分支限界法的代價(jià)首先，設(shè)計(jì)一個(gè)好的限界函數(shù)通常需要花費(fèi)更多的時(shí)間計(jì)算相應(yīng)的目標(biāo)函數(shù)值，而且對(duì)于具體的問(wèn)題實(shí)例，通常需要進(jìn)行大量實(shí)驗(yàn)，才能確定一個(gè)好的限界函數(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ù)PT表需要較大的存儲(chǔ)空間，在最壞情況下，分支限界法需要的空間復(fù)雜性是指數(shù)階。9.1.2分支限界法的時(shí)間性能

2023/2/1BranchandBoundMethod24第9章分支限界法

9.1概

述

9.2圖問(wèn)題中的分支限界法9.3組合問(wèn)題中的分支限界法9.2圖問(wèn)題中的分支限界法9.2.1TSP問(wèn)題9.2.2多段圖的最短路徑問(wèn)題25BranchandBoundMethod算法設(shè)計(jì)與分析2023/2/1BranchandBoundMethod269.2.1TSP問(wèn)題TSP問(wèn)題是指旅行家要旅行n個(gè)城市，要求各個(gè)城市經(jīng)歷且僅經(jīng)歷一次然后回到出發(fā)城市，并要求所走的路程最短。271563134253984C=∞3

158

3∞679

16∞42

574∞3892

3∞(a)一個(gè)無(wú)向圖(b)無(wú)向圖的代價(jià)矩陣圖9.4無(wú)向圖及其代價(jià)矩陣2023/2/1BranchandBoundMethod27確定上界ub采用貪心法求得近似解為:1→3→5→4→2→1

ub=1+2+3+7+3=16

這可以作為T(mén)SP問(wèn)題的上界確定下界lb把矩陣中每一行最小的元素相加，可以得到一個(gè)簡(jiǎn)單的下界:

lb=1+3+1+3+2=10一個(gè)信息量更大的下界：把矩陣中每一行最小的兩個(gè)元素相加再除以2，再對(duì)這個(gè)結(jié)果向上取整，就得到了一個(gè)合理的下界:

lb=((1+3)+(3+6)+(1+2)+(3+4)+(2+3))/2=14

則，目標(biāo)函數(shù)的界:[lb,ub]=[14,16]注意：該解并不是一個(gè)合法的選擇（即沒(méi)構(gòu)成哈密頓回路），僅給出了一個(gè)參考下界。9.2TSP問(wèn)題2715631342539842023/2/1BranchandBoundMethod28

部分解的目標(biāo)函數(shù)值的計(jì)算方法假設(shè)當(dāng)前已確定的路徑為U=(r1,r2,…,rk),則：

例如圖10.4所示無(wú)向圖，如果部分解包含頂點(diǎn)U=(1,4)，則該部分解的下界是:lb=(2*5+(1+3)+((3+6)+(1+2)+(2+3)))/2=16分支限界法求解TSP問(wèn)題示例271563134253984C=∞31

58

3∞679

16∞42

5

74∞3892

3∞i=1,k2023/2/1BranchandBoundMethod29TSP問(wèn)題的搜索過(guò)程考察根結(jié)點(diǎn)1

目標(biāo)函數(shù):lb=((1+3)+(3+6)+(1+2)+(3+4)+(2+3))/2=14

將根結(jié)點(diǎn)1加入PT表中考察孩子結(jié)點(diǎn)2:C1C2,路徑長(zhǎng)度為3

目標(biāo)函數(shù):lb=(2*3+(1+6)+(1+2)+(3+4)+(2+3))/2=14

將結(jié)點(diǎn)2加入待處理結(jié)點(diǎn)表PT中；在結(jié)點(diǎn)3：C1C3，路徑長(zhǎng)度為1

目標(biāo)函數(shù):lb=(2*1+(3+2)+(3+6)+(3+4)+(2+3))/2=14

將結(jié)點(diǎn)3加入表PT中在結(jié)點(diǎn)4：C1C4，路徑長(zhǎng)度為5

目標(biāo)函數(shù):lb=(2*5+(1+3)+(3+6)+(1+2)+(2+3))/2=16

將結(jié)點(diǎn)4加入表PT中∞3158

3∞679

16∞42

574∞3892

3∞2023/2/1BranchandBoundMethod30在結(jié)點(diǎn)5：C1C5，路徑長(zhǎng)度為8

目標(biāo)函數(shù)：lb=(2*8+(1+2)+(3+6)+(1+2)+(3+4))/2=19

超出目標(biāo)函數(shù)的界，將結(jié)點(diǎn)5丟棄；處理結(jié)點(diǎn)2的孩子結(jié)點(diǎn)。結(jié)點(diǎn)6,C1C2C3,路徑長(zhǎng)度為3+6

目標(biāo)函數(shù):lb=(2*9+(1+1)+(3+4)+(2+3))/2=16

將結(jié)點(diǎn)6加入表PT中在結(jié)點(diǎn)7，C1

C2C4，路徑長(zhǎng)度為3+7

目標(biāo)函數(shù)lb=(2*10+(1+3)+(1+2)+(2+3))/2=16

將結(jié)點(diǎn)7加入表PT中分支限界法求解TSP問(wèn)題示例在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)2優(yōu)先進(jìn)行搜索∞3

158

3∞6

79

1

6∞42

5

74∞38923

∞2023/2/1BranchandBoundMethod31在結(jié)點(diǎn)8，C1

C2C5，路徑長(zhǎng)度為3+9目標(biāo)函數(shù):lb=(2*12+(1+2)+(1+2)+(3+4))/2=19超出目標(biāo)函數(shù)的界，將結(jié)點(diǎn)8丟棄處理結(jié)點(diǎn)3的孩子。結(jié)點(diǎn)9，C1

C3C2，路徑長(zhǎng)度為1+6

目標(biāo)函數(shù)值:lb=(2*7+(3+3)+(3+4)+(2+3))/2=16

將結(jié)點(diǎn)9加入表PT中在結(jié)點(diǎn)10，C1

C3C4，路徑長(zhǎng)度為1+4

目標(biāo)函數(shù):lb=(2*5+(3+3)+(3+6)+(2+3))/2=15

將結(jié)點(diǎn)10加入表PT中分支限界法求解TSP問(wèn)題示例在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)3優(yōu)先進(jìn)行搜索∞3

1583∞679

1

6∞4

2

5

74∞389

23

∞2023/2/1BranchandBoundMethod32在結(jié)點(diǎn)11，C1C3C5，路徑長(zhǎng)度為1+2

目標(biāo)函數(shù)值:lb=(2*3+(3+3)+(3+6)+(3+4))/2=14

將結(jié)點(diǎn)11加入表PT中在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)11優(yōu)先進(jìn)行搜索處理結(jié)點(diǎn)11的孩子。結(jié)點(diǎn)12，C1C3C5C2，路徑長(zhǎng)度為1+2+9，目標(biāo)函數(shù)值:lb=(2*12+(3+3)+(3+4))/2=19

超出目標(biāo)函數(shù)的界，將結(jié)點(diǎn)12丟棄在結(jié)點(diǎn)13，C1C3

C5C4，路徑長(zhǎng)度為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)13優(yōu)先進(jìn)行搜索∞3

1583∞679

1

6∞42

5

74∞389

2

3∞2023/2/1BranchandBoundMethod33在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)10優(yōu)先進(jìn)行搜索處理結(jié)點(diǎn)13的孩子。結(jié)點(diǎn)14，C1C3

C5C4C2，路徑長(zhǎng)度為1+2+3+7，目標(biāo)函數(shù)值:lb=(2*13+(3+3))/2=16

由于結(jié)點(diǎn)14為葉子結(jié)點(diǎn)，得到一個(gè)可行解 其路徑長(zhǎng)度為16∞3

158

3∞67

9

1

6∞42

5

74∞389

2

3∞分支限界法求解TSP問(wèn)題示例2023/2/1BranchandBoundMethod34分支限界法求解TSP問(wèn)題示例在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)16優(yōu)先進(jìn)行搜索處理結(jié)點(diǎn)10的孩子。結(jié)點(diǎn)15，C1C3

C4C2，長(zhǎng)度12。

目標(biāo)函數(shù):lb=(2*12+(3+3)+(2+3))/2=18

超出目標(biāo)函數(shù)的界，將結(jié)點(diǎn)15丟棄結(jié)點(diǎn)16，C1C3

C4C5，長(zhǎng)度8

目標(biāo)函數(shù):lb=(2*8+(3+2)+(3+6))/2=15

將結(jié)點(diǎn)16加入表PT中處理結(jié)點(diǎn)16的孩子。結(jié)點(diǎn)17,C1C3C4C5C2,長(zhǎng)度17，目標(biāo)函數(shù):lb=(2*17+(3+3))/2=20,超目標(biāo)函數(shù)的界，結(jié)點(diǎn)17丟棄表PT中目標(biāo)函數(shù)值均為16，且已找到葉子結(jié)點(diǎn)14的長(zhǎng)度是16，故這是最優(yōu)解，搜索過(guò)程結(jié)束。

∞3

158

3∞679

1

6∞4

2

5

74∞38

9

2

3∞2023/2/1BranchandBoundMethod3541→2lb=142356781×startlb=141→3lb=141→4lb=161→5lb=192→3lb=162→4lb=162→5lb=193→2lb=163→4lb=153→5lb=14×910115→2lb=195→4lb=141213×4→2lb=16144→2lb=184→5lb=151516×5→2lb=2017×分支限界法求解TSP問(wèn)題示例C2C1C3C5C4C3C5C4C2C4C5C4C2C2∞3

158

3∞679

1

6∞42

5

74∞3892

3∞2023/2/1BranchandBoundMethod36(g)擴(kuò)展結(jié)點(diǎn)16后的狀態(tài)，最優(yōu)解為1→3→5→4→2→1圖9.6TSP問(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)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,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)2023/2/1BranchandBoundMethod37算法9.1——TSP問(wèn)題輸入：圖G＝（V，E）輸出：最短哈密爾頓回路

1．根據(jù)限界函數(shù)計(jì)算目標(biāo)函數(shù)的下界down；采用貪心法得到上界up；

2．計(jì)算根結(jié)點(diǎn)的目標(biāo)函數(shù)值并加入待處理結(jié)點(diǎn)表PT；

3．循環(huán)直到某個(gè)葉子結(jié)點(diǎn)的目標(biāo)函數(shù)值在表PT中取得極小值

3.1i=表PT中具有最小值的結(jié)點(diǎn)；3.2對(duì)結(jié)點(diǎn)i的每個(gè)孩子結(jié)點(diǎn)x執(zhí)行下列操作： 3.2.1估算結(jié)點(diǎn)x的目標(biāo)函數(shù)值lb; 3.2.2若（lb<=up），則將結(jié)點(diǎn)x加入表PT中，否則丟棄4.將葉子結(jié)點(diǎn)對(duì)應(yīng)的最優(yōu)值輸出，回溯求得最優(yōu)解的各個(gè)分量。偽代碼9.2TSP問(wèn)題9.2圖問(wèn)題中的分支限界法9.2.1TSP問(wèn)題9.2.2多段圖的最短路徑問(wèn)題38BranchandBoundMethod算法設(shè)計(jì)與分析9.2.2多段圖的最短路徑問(wèn)題

設(shè)圖G=(V,E)是一個(gè)帶權(quán)有向連通圖，如果把頂點(diǎn)集合V劃分成k個(gè)互不相交的子集Vi（2≤k≤n,1≤i≤k），使得E中的任何一條邊(u,v)，必有u∈Vi，v∈Vi+m（1≤i＜k,

1＜i+m≤k），則稱圖G為多段圖，稱s∈V1為源點(diǎn)，t∈Vk為終點(diǎn)。1203456789492387884756866537多段圖的最短路徑問(wèn)題是求從源點(diǎn)到終點(diǎn)的最小代價(jià)路徑。39BranchandBoundMethod算法設(shè)計(jì)與分析

對(duì)圖9.7所示多段圖應(yīng)用貪心法求得近似解為0→2→5→8→9，其路徑代價(jià)為2+7+6+3=18，這可以作為多段圖最短路徑問(wèn)題的上界。把每一段最小的代價(jià)相加，可以得到一個(gè)非常簡(jiǎn)單的下界，其路徑長(zhǎng)度為2+4+5+3=14。于是，得到了目標(biāo)函數(shù)的界[14,18]。由于多段圖將頂點(diǎn)劃分為k個(gè)互不相交的子集，所以，多段圖劃分為k段，一旦某條路徑的一些段被確定后，就可以并入這些信息并計(jì)算部分解的目標(biāo)函數(shù)值的下界。一般情況下，對(duì)于一個(gè)正在生成的路徑，假設(shè)已經(jīng)確定了i段（1≤i≤k），其路徑為(r1,r2,…,ri,ri+1)，此時(shí)，該部分解的目標(biāo)函數(shù)值的計(jì)算方法即限界函數(shù)如下：??+=+>?<=++=+kijpiEvrijjjjvrcrrclbpi21,11]}][[{min]][[1段的最短邊第＋40BranchandBoundMethod算法設(shè)計(jì)與分析已確定的路徑長(zhǎng)度ri+1出發(fā)的最短邊ri+2后面每段的最短邊和

應(yīng)用分支限界法求解圖9.7所示多段圖的最短路徑問(wèn)題，其搜索空間如圖9.8所示，具體的搜索過(guò)程如下（加黑表示該路徑上已經(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段選擇邊<0,1>，目標(biāo)函數(shù)值為lb=4+8+5+3=20，超出目標(biāo)函數(shù)的界，將結(jié)點(diǎn)2丟棄；在結(jié)點(diǎn)3，第1段選擇邊<0,2>，目標(biāo)函數(shù)值為lb=2+7+5+3=17，將結(jié)點(diǎn)3加入表PT；在結(jié)點(diǎn)4，第1段選擇邊<0,3>，目標(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)行搜索；41BranchandBoundMethod算法設(shè)計(jì)與分析1203456789492387884756866537（4）在結(jié)點(diǎn)5，第2段選擇邊<3,5>，目標(biāo)函數(shù)值為lb=3+4+6+3=16，將結(jié)點(diǎn)5加入表PT中；在結(jié)點(diǎn)6，第2段選擇邊<3,6>，目標(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，已確定路徑是0→3→5→7，可直接確定第4段的邊<7,9>，目標(biāo)函數(shù)值為lb=3+4+8+7=22，超界丟棄；在結(jié)點(diǎn)8，已確定路徑是0→3→5→8，可直接確定第4段的邊<8,9>，目標(biāo)函數(shù)值為lb=3+4+6+3=16，為一個(gè)可行解；由于結(jié)點(diǎn)8是葉子結(jié)點(diǎn)，并且其目標(biāo)函數(shù)值是PT中最小的，所以它是最優(yōu)解，搜索結(jié)束。42BranchandBoundMethod算法設(shè)計(jì)與分析1203456789492387884756866537640→1lb=20231startlb=180→2lb=160→3lb=15×圖9.8分支限界法求解多段圖的最短路徑問(wèn)題示例(×表示該結(jié)點(diǎn)被丟棄，結(jié)點(diǎn)上方的數(shù)組表示搜索順序)53→5lb=163→6lb=1887lb=22lb=16×5→85→743BranchandBoundMethod算法設(shè)計(jì)與分析2023/2/1BranchandBoundMethod44第9章分支限界法

9.1概

述

9.2圖問(wèn)題中的分支限界法9.3組合問(wèn)題中的分支限界法2023/2/1BranchandBoundMethod459.3組合問(wèn)題中的分支限界法

9.3.2任務(wù)分配問(wèn)題

9.3.3批處理作業(yè)調(diào)度問(wèn)題9.3.10/1背包問(wèn)題2023/2/1BranchandBoundMethod46問(wèn)題描述

任務(wù)分配問(wèn)題要求把n項(xiàng)任務(wù)分配給n個(gè)人，每個(gè)人完成每項(xiàng)任務(wù)的成本不同，要求分配總成本最小的最優(yōu)分配方案。如圖9.10所示是一個(gè)任務(wù)分配的成本矩陣。

9.3.2任務(wù)分配問(wèn)題

C＝9278643758187694任務(wù)1任務(wù)2任務(wù)3任務(wù)4人員a人員b人員c人員d圖9.10任務(wù)分配問(wèn)題的成本矩陣2023/2/1BranchandBoundMethod47如何求最優(yōu)分配成本的上界Up和下界Down獲得上界UP如考慮以矩陣的對(duì)角線作為一個(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=1414是一個(gè)更好的上界9.3.2任務(wù)分配問(wèn)題

C＝9278643758187694任務(wù)1任務(wù)2任務(wù)3任務(wù)4人員a人員b人員c人員d圖9.10任務(wù)分配問(wèn)題的成本矩陣2023/2/1BranchandBoundMethod48獲得下界Down考慮人員a所有任務(wù)的最小代價(jià)是2人員b執(zhí)行所有任務(wù)的最小代價(jià)是3人員c執(zhí)行所有任務(wù)的最小代價(jià)是1人員d執(zhí)行所有任務(wù)的最小代價(jià)是4

每行取最小元素，其成本下界：2+3+1+4=10

則上下界為：[10,14]

注意：這個(gè)解并不是一個(gè)合法的選擇因?yàn)椋?、1來(lái)自于矩陣同一列，僅給出一個(gè)參考下界9.3.2任務(wù)分配問(wèn)題

2023/2/1BranchandBoundMethod49設(shè)當(dāng)前已對(duì)人員1～i分配了任務(wù)，并且獲得了成本v，則限界函數(shù)可以定義為：

（式9.4）搜索過(guò)程在根結(jié)點(diǎn)1

沒(méi)有分配任務(wù)，限界函數(shù)函數(shù)值為:lb=2+3+1+4=10在結(jié)點(diǎn)2

將J1人員a，獲得的成本為9

目標(biāo)函數(shù)值為:lb=9+(3+1+4)=17

超出目標(biāo)函數(shù)的界[10,14]，將結(jié)點(diǎn)2丟棄9.3.2任務(wù)分配問(wèn)題

C＝9278643758187694人員a人員b人員c人員d2023/2/1BranchandBoundMethod50圖9.11分支限界法求解任務(wù)分配問(wèn)題示例(×表示該結(jié)點(diǎn)被丟棄，結(jié)點(diǎn)上方的數(shù)組表示搜索順序)4→alb=16104×startlb=101→alb=172→alb=103→alb=151→blb=133→blb=104→blb=141→clb=144→clb=174→clb=173→clb=134→dlb=1323567891213111××××

C＝9278643758187694任務(wù)1任務(wù)2任務(wù)3任務(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)題

2023/2/1BranchandBoundMethod51搜索過(guò)程在結(jié)點(diǎn)3

將J2人員a，獲得的成本為2

目標(biāo)函數(shù)值:lb=2+(3+1+4)=10

將結(jié)點(diǎn)3-PT表中在結(jié)點(diǎn)4

將J3人員a，獲得的成本為7

目標(biāo)函數(shù)值:lb=7+(3+1+4)=15

超出目標(biāo)函數(shù)的界[10,14]，將結(jié)點(diǎn)4丟棄9.3.2任務(wù)分配問(wèn)題

C＝9278643758187694任務(wù)1任務(wù)2任務(wù)3任務(wù)4人員a人員b人員c人員d2023/2/1BranchandBoundMethod52在結(jié)點(diǎn)5

將J4人員a，獲得的成本為8

目標(biāo)函數(shù)值:lb=8+(3+1+4)=16

超出目標(biāo)函數(shù)的界[10,14]，將結(jié)點(diǎn)5丟棄在結(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)3優(yōu)先進(jìn)行搜索9.3.2任務(wù)分配問(wèn)題

9278643758187694任務(wù)1任務(wù)2任務(wù)3任務(wù)4人員a人員b人員c人員d2023/2/1BranchandBoundMethod53在結(jié)點(diǎn)7

將J2人員a，J3人員b，獲得的成本為2+3=5

目標(biāo)函數(shù)值:lb=5+(1+4)＝10

將結(jié)點(diǎn)7加入表PT中在結(jié)點(diǎn)8

將J2人員a，J4人員b，獲得的成本為2+7=9

目標(biāo)函數(shù)值:lb=9+(1+4)＝14

將結(jié)點(diǎn)8加入表PT中；在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)7優(yōu)先進(jìn)行搜索9.3.2任務(wù)分配問(wèn)題

9278643

758187694任務(wù)1任務(wù)2任務(wù)3任務(wù)4人員a人員b人員c人員d2023/2/1BranchandBoundMethod54在結(jié)點(diǎn)9

將J2人員a，J3人員b

，J1人員c，獲得的成本為5+5=10

目標(biāo)函數(shù)值:lb=10+4=14

將結(jié)點(diǎn)9加入表PT中在結(jié)點(diǎn)10

將J2人員a，J3人員b

，J4人員c，獲得的成本為5+8=13

目標(biāo)函數(shù)值:lb=13+4=17

超出目標(biāo)函數(shù)的界[10,14]，將結(jié)點(diǎn)10丟棄在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)6優(yōu)先進(jìn)行搜索9.3.2任務(wù)分配問(wèn)題

2023/2/1BranchandBoundMethod55在結(jié)點(diǎn)11

將J2人員a,J1人員b，

J3人員c，獲得的成本為8+1=9

目標(biāo)函數(shù)值:lb=9+4=13

將結(jié)點(diǎn)11加入表PT中在結(jié)點(diǎn)12

將J2人員a,J1人員b，J4人員c，獲得的成本為8+8=16

目標(biāo)函數(shù)值:lb=16+4=20

超出目標(biāo)函數(shù)的界[10,14]，將結(jié)點(diǎn)12丟棄；在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點(diǎn)11優(yōu)先進(jìn)行搜索9.3.2任務(wù)分配問(wèn)題

9278643

758187694任務(wù)1任務(wù)2任務(wù)3任務(wù)42023/2/1BranchandBoundMethod56在結(jié)點(diǎn)13

將J2人員a,J1人員b，J3人員c

，J4人員d

獲得的成本為9+4=13

目標(biāo)函數(shù)值為:lb=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é)束。構(gòu)建搜索經(jīng)過(guò)的樹(shù)結(jié)構(gòu)取出表PT中最小值結(jié)點(diǎn)進(jìn)行擴(kuò)充時(shí)，并將最小值結(jié)點(diǎn)存儲(chǔ)到ST中，表PT和表ST的數(shù)據(jù)結(jié)構(gòu)為：

(人員i-1分配的任務(wù),<任務(wù)k,人員i>lb)9.3.2任務(wù)分配問(wèn)題

2023/2/1BranchandBoundMethod57

(人員i-1分配的任務(wù),<任務(wù)k,人員i>lb)(e)擴(kuò)展結(jié)點(diǎn)11后的狀態(tài)，最優(yōu)解為2→a，1→b，3→c，4→d(0,<2,a>10)(2,<1,b>13)(2,<3,b>10)(2,<4,b>14)(0,<2,a>10)(2,<1,b>13)(2,<4,b>14)(3,<1,c>14)(0,<2,a>10)(2,<3,b>10)(2,<4,b>14)(3,<1,c>14)(1,<3,c>13)(0,<2,a>10)(2,<3,b>10)(2,<1,b>13)(0,<2,a>10)(2,<3,b>10)(2,<1,b>13)(1,<3,c>13)(3,<4,d>13)(a)擴(kuò)展根結(jié)點(diǎn)后的狀態(tài)(b)擴(kuò)展結(jié)點(diǎn)3后的狀態(tài)PTSTPTST

PTST

(c)擴(kuò)展結(jié)點(diǎn)7后的狀態(tài)(d)擴(kuò)展結(jié)點(diǎn)6后的狀態(tài)(2,<4,b>14)(3,<1,c>14)(3,<4,d>13)PTSTPTST

9.3.2任務(wù)分配問(wèn)題

2023/2/1BranchandBoundMethod589.3組合問(wèn)題中的分支限界法

9.3.2任務(wù)分配問(wèn)題

9.3.3批處理作業(yè)調(diào)度問(wèn)題9.3.10/1背包問(wèn)題2023/2/1BranchandBoundMethod59問(wèn)題描述n個(gè)作業(yè)的集合J={J1,J2,…,Jn}，每個(gè)作業(yè)都有3項(xiàng)任務(wù)分別在3臺(tái)機(jī)器上完成Ji

需要機(jī)器j的處理時(shí)間為tij（1≤i≤n,1≤j≤3）作業(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è)在機(jī)器3上處理結(jié)束所需的時(shí)間最少。最優(yōu)調(diào)度原則使機(jī)器1沒(méi)有空閑時(shí)間，且機(jī)器2和3的空閑時(shí)間最小9.3.3批處理作業(yè)調(diào)度問(wèn)題2023/2/1BranchandBoundMethod60T＝57910529957810J1J2J3J4機(jī)器1機(jī)器2機(jī)器3

設(shè)J={J1,J2,J3,J4}是4個(gè)待處理的作業(yè)，每個(gè)作業(yè)的處理順序相同:機(jī)器1上處理機(jī)器2上處理機(jī)器3上處理需要的處理時(shí)間如下矩陣所示:9.3.3批處理作業(yè)調(diào)度問(wèn)題2023/2/1BranchandBoundMethod61上界？隨機(jī)產(chǎn)生幾個(gè)方案，從中選取最短完成時(shí)間為問(wèn)題的上界。如若處理順序?yàn)?J4

J1

J3

J2，調(diào)度方案:J4:7J1:5J3:9J2:10機(jī)器1機(jī)器2機(jī)器3

圖9.13批處理調(diào)度問(wèn)題的調(diào)度方案空閑:7J4:8J1:7J3:9J2:5空閑:15J4:10J1:9J3:5J2:29.3.3批處理作業(yè)調(diào)度問(wèn)題上界：412023/2/1BranchandBoundMethod62批處理作業(yè)調(diào)度問(wèn)題的限界函數(shù)down理想情況機(jī)器1和機(jī)器2開(kāi)始作業(yè)后無(wú)空閑，最后處理的恰好是在機(jī)器3上處理時(shí)間最短的作業(yè)。例如，以作業(yè)Ji開(kāi)始的處理順序，估算處理所需的最短時(shí)間是：tij:表示Ji需要機(jī)器j的處理時(shí)間(1≤i≤n,1≤j≤3)9.3.3批處理作業(yè)調(diào)度問(wèn)題作業(yè)Ji在機(jī)器1上的處理時(shí)間作業(yè)1~作業(yè)n在機(jī)器2上的處理時(shí)間總和在機(jī)器3上處理時(shí)間最短的作業(yè)2023/2/1BranchandBoundMethod63目標(biāo)函數(shù)下界計(jì)算lb若已安排了k-1個(gè)作業(yè)集合，即：M{1,2,…,

k-1}，|M|=k-1sum1[k-1]：機(jī)器1完成k-1個(gè)作業(yè)的處理時(shí)間sum2[k-1]：機(jī)器2完成k-1個(gè)作業(yè)的處理時(shí)間現(xiàn)要處理作業(yè)k，此時(shí)，該部分解的目標(biāo)函數(shù)值的下界lb計(jì)算方法如下：（1）sum1[k]=sum1[k-1]+tk1（2）（3）sum2[k]=max{sum1[k],sum2[k-1]}+

tk2

9.3.3批處理作業(yè)調(diào)度問(wèn)題2023/2/1BranchandBoundMethod64分支限界法搜索過(guò)程在根結(jié)點(diǎn)將sum1[0]和sum2[0]分別初始化為0

估算目標(biāo)函數(shù)上界為41，加入表PT在結(jié)點(diǎn)2

以作業(yè)J1開(kāi)始處理，則sum1[1]=5

目標(biāo)函數(shù)值:lb=5+(7+5+9+8)+2=36,

sum2[1]=5+7=12

將結(jié)點(diǎn)2加入待處理結(jié)點(diǎn)表PT中在結(jié)點(diǎn)3

以作業(yè)J2開(kāi)始處理，則sum1[1]=10

目標(biāo)函數(shù)值:lb=10+(7+5+9+8)+5=44,

超過(guò)上界41，結(jié)點(diǎn)3舍棄。T＝579105