分支限界法完

2023/2/14第9章分支限界法Page19.1概

述

9.2圖問題中的分支限界法9.3組合問題中的分支限界法9.4試驗(yàn)項(xiàng)目——電路布線問題第9章分支限界法2023/2/14第9章分支限界法Page29.1.1解空間樹的動(dòng)態(tài)搜尋（2）9.1.2分支限界法的設(shè)計(jì)思想9.1.3分支限界法的時(shí)間性能9.1概述

2023/2/14第9章分支限界法Page3分支限界法首先確定一個(gè)合理的限界函數(shù)，并依據(jù)限界函數(shù)確定目標(biāo)函數(shù)的界[down,up]。然后，依據(jù)廣度優(yōu)先策略遍歷問題的解空間樹，在分支結(jié)點(diǎn)上，依次搜尋該結(jié)點(diǎn)的全部孩子結(jié)點(diǎn)，分別估算這些孩子結(jié)點(diǎn)的目標(biāo)函數(shù)的可能取值，假如某孩子結(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ù)上述過程，直到找到最優(yōu)解。9.1.1解空間樹的動(dòng)態(tài)搜尋（2）2023/2/14第9章分支限界法Page4隨著這個(gè)遍歷過程的不斷深化，表PT中所估算的目標(biāo)函數(shù)的界越來越接近問題的最優(yōu)解。當(dāng)搜尋到一個(gè)葉子結(jié)點(diǎn)時(shí)，假如該結(jié)點(diǎn)的目標(biāo)函數(shù)值是表PT中的極值（對(duì)于最小化問題，是微小值；對(duì)于最大化問題，是極大值），則該葉子結(jié)點(diǎn)對(duì)應(yīng)的解就是問題的最優(yōu)解；否則，依據(jù)這個(gè)葉子結(jié)點(diǎn)調(diào)整目標(biāo)函數(shù)的界（對(duì)于最小化問題，調(diào)整上界；對(duì)于最大化問題，調(diào)整下界），依次考察表PT中的結(jié)點(diǎn)，將超出目標(biāo)函數(shù)界的結(jié)點(diǎn)丟棄，然后從表PT中選取使目標(biāo)函數(shù)取得極值的結(jié)點(diǎn)接著進(jìn)行擴(kuò)展。2023/2/14第9章分支限界法Page5例：0/1背包問題。假設(shè)有4個(gè)物品，其重量分別為(4,7,5,3)，價(jià)值分別為(40,42,25,12)，背包涵量W=10。首先，將給定物品按單位重量價(jià)值從大到小排序，結(jié)果如下：物品重量(w)價(jià)值(v)價(jià)值/重量(v/w)1440102742635255431242023/2/14第9章分支限界法Page6應(yīng)用貪心法求得近似解為(1,0,0,0)，獲得的價(jià)值為40，這可以作為0/1背包問題的下界。如何求得0/1背包問題的一個(gè)合理的上界呢？考慮最好狀況，背包中裝入的全部是第1個(gè)物品且可以將背包裝滿，則可以得到一個(gè)特殊簡潔的上界的計(jì)算方法：ub=W×(v1/w1)=10×10=100。于是，得到了目標(biāo)函數(shù)的界[40,100]。2023/2/14第9章分支限界法Page7假設(shè)背包中已裝入物品的重量是w，獲得的價(jià)值是v，計(jì)算該結(jié)點(diǎn)的目標(biāo)函數(shù)上界的一個(gè)簡潔方法是把已經(jīng)裝入背包中的物品取得的價(jià)值v，加上背包剩余容量W-w與剩下物品的最大單位重量價(jià)值的積，于是，得到限界函數(shù)為：

2023/2/14第9章分支限界法Page8×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=6523456789×1分支限界法求解0/1背包問題2023/2/14第9章分支限界法Page9分支限界法求解0/1背包問題，其搜尋空間如圖9.1所示，具體的搜尋過程如下：（1）在根結(jié)點(diǎn)1，沒有將任何物品裝入背包，因此，背包的重量和獲得的價(jià)值均為0，依據(jù)限界函數(shù)計(jì)算結(jié)點(diǎn)1的目標(biāo)函數(shù)值為10×10=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，沒有將物品1裝入背包，因此，背包的重量和獲得的價(jià)值仍為0，目標(biāo)函數(shù)值為10×6＝60，將結(jié)點(diǎn)3加入表PT中；（3）在表PT中選取目標(biāo)函數(shù)值取得極大的結(jié)點(diǎn)2優(yōu)先進(jìn)行搜尋；2023/2/14第9章分支限界法Page10（4）在結(jié)點(diǎn)4，將物品2裝入背包，因此，背包的重量為11，不滿足約束條件，將結(jié)點(diǎn)4丟棄；在結(jié)點(diǎn)5，沒有將物品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加入表PT中；在結(jié)點(diǎn)7，沒有將物品3裝入背包，因此，背包的重量和獲得的價(jià)值與結(jié)點(diǎn)5相同，目標(biāo)函數(shù)值為40+(10-4)×4＝64，將結(jié)點(diǎn)6加入表PT中；2023/2/14第9章分支限界法Page11（7）在表PT中選取目標(biāo)函數(shù)值取得極大的結(jié)點(diǎn)6優(yōu)先進(jìn)行搜尋；（8）在結(jié)點(diǎn)8，將物品4裝入背包，因此，背包的重量為12，不滿足約束條件，將結(jié)點(diǎn)8丟棄；在結(jié)點(diǎn)9，沒有將物品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)的解即是問題的最優(yōu)解，搜尋結(jié)束。2023/2/14第9章分支限界法Page12假設(shè)求解最大化問題，解向量為X=(x1,x2,…,xn)，其中，xi的取值范圍為某個(gè)有窮集合Si，|Si|=ri（1≤i≤n）。在運(yùn)用分支限界法搜尋問題的解空間樹時(shí)，首先依據(jù)限界函數(shù)估算目標(biāo)函數(shù)的界[down,up]，然后從根結(jié)點(diǎn)動(dòng)身，擴(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)為根的子樹所可能取得的目標(biāo)函數(shù)值不大于bound(x1)，也就是部分解應(yīng)滿足：bound(x1)≥bound(x1,x2)≥…≥bound(x1,x2,…,xk)≥…≥bound(x1,x2,…,xn)9.1.2分支限界法的設(shè)計(jì)思想2023/2/14第9章分支限界法Page13

若某孩子結(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ù)上述過程，當(dāng)?shù)竭_(dá)一個(gè)葉子結(jié)點(diǎn)時(shí)，就得到了一個(gè)可行解X=(x1,x2,…,xn)及其目標(biāo)函數(shù)值bound(x1,x2,…,xn)。2023/2/14第9章分支限界法Page14假如bound(x1,x2,…,xn)是表PT中目標(biāo)函數(shù)值最大的結(jié)點(diǎn)，則bound(x1,x2,…,xn)就是所求問題的最大值，(x1,x2,…,xn)就是問題的最優(yōu)解；假如bound(x1,x2,…,xn)不是表PT中目標(biāo)函數(shù)值最大的結(jié)點(diǎn)，說明還存在某個(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)，接著搜尋，直到某個(gè)葉子結(jié)點(diǎn)的目標(biāo)函數(shù)值在表PT中最大。2023/2/14第9章分支限界法Page15分支限界法求解最大化問題的一般過程分支限界法的一般過程1．依據(jù)限界函數(shù)確定目標(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)且結(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值在表PT中不是最大)，則令down=value，并且將表PT中全部小于value的結(jié)點(diǎn)刪除；2023/2/14第9章分支限界法Page16應(yīng)用分支限界法的關(guān)鍵問題（1）如何確定合適的限界函數(shù)（2）如何組織待處理結(jié)點(diǎn)表（3）如何確定最優(yōu)解中的各個(gè)重量2023/2/14第9章分支限界法Page17分支限界法對(duì)問題的解空間樹中結(jié)點(diǎn)的處理是跳動(dòng)式的，回溯也不是單純地沿著雙親結(jié)點(diǎn)一層一層向上回溯，因此，當(dāng)搜尋到某個(gè)葉子結(jié)點(diǎn)且該葉子結(jié)點(diǎn)的目標(biāo)函數(shù)值在表PT中最大時(shí)（假設(shè)求解最大化問題），求得了問題的最優(yōu)值，但是，卻無法求得該葉子結(jié)點(diǎn)對(duì)應(yīng)的最優(yōu)解中的各個(gè)重量。這個(gè)問題可以用如下方法解決：①對(duì)每個(gè)擴(kuò)展結(jié)點(diǎn)保存該結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑；②在搜尋過程中構(gòu)建搜尋經(jīng)過的樹結(jié)構(gòu)，在求得最優(yōu)解時(shí)，從葉子結(jié)點(diǎn)不斷回溯到根結(jié)點(diǎn)，以確定最優(yōu)解中的各個(gè)重量。

對(duì)于（3）：如何確定最優(yōu)解中的各個(gè)重量：2023/2/14第9章分支限界法Page18(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背包問題最優(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背包問題，為了對(duì)每個(gè)擴(kuò)展結(jié)點(diǎn)保存該結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑，將部分解(x1,…,xi)和該部分解的目標(biāo)函數(shù)值都存儲(chǔ)在待處理結(jié)點(diǎn)表PT中，在搜尋過程中表PT的狀態(tài)如圖9.2所示。2023/2/14第9章分支限界法Page19(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背包問題最優(yōu)解的各分量(0,<1,1>76)(0,<1,0>60)PTST(0,<1,0>60)(1,<2,0>70)PTST(0,<1,1>76)(0,<1,0>60)(0,<3,1>69)(0,<3,0>64)PTST(0,<1,1>76)(1,<2,0>70)(0,<1,0>60)(0,<3,0>64)(1,<4,0>65)PTST(0,<1,1>76)(1,<2,0>70)(0,<3,1>69)方法二：圖9.1所示0/1背包問題，為了在搜尋過程中構(gòu)建搜尋經(jīng)過的樹結(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é)果，<物品i,物品i的選擇結(jié)果>ub)，在搜尋過程中表PT和表ST的狀態(tài)如圖9.3所示。2023/2/14第9章分支限界法Page20分支限界法和回溯法事實(shí)上都屬于蠻力窮舉法，當(dāng)然不能希望它有很好的最壞時(shí)間困難性，遍歷具有指數(shù)階個(gè)結(jié)點(diǎn)的解空間樹，在最壞狀況下，時(shí)間困難性確定為指數(shù)階。與回溯法不同的是，分支限界法首先擴(kuò)展解空間樹中的上層結(jié)點(diǎn)，并接受限界函數(shù)，有利于實(shí)行大范圍剪枝，同時(shí)，依據(jù)限界函數(shù)不斷調(diào)整搜尋方向，選擇最有可能取得最優(yōu)解的子樹優(yōu)先進(jìn)行搜尋。所以，假如選擇了結(jié)點(diǎn)的合理擴(kuò)展依次以及設(shè)計(jì)了一個(gè)好的限界函數(shù)，分支界限法可以快速得到問題的解。9.1.3分支限界法的時(shí)間性能2023/2/14第9章分支限界法Page21分支限界法的較高效率是以付出確定代價(jià)為基礎(chǔ)的，其工作方式也造成了算法設(shè)計(jì)的困難性。首先，一個(gè)更好的限界函數(shù)通常須要花費(fèi)更多的時(shí)間計(jì)算相應(yīng)的目標(biāo)函數(shù)值，而且對(duì)于具體的問題實(shí)例，通常須要進(jìn)行大量試驗(yàn)，才能確定一個(gè)好的限界函數(shù)；其次，由于分支限界法對(duì)解空間樹中結(jié)點(diǎn)的處理是跳動(dòng)式的，因此，在搜尋到某個(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)的路徑，或者在搜尋過程中構(gòu)建搜尋經(jīng)過的樹結(jié)構(gòu)，這使得算法的設(shè)計(jì)較為困難；再次，算法要維護(hù)一個(gè)待處理結(jié)點(diǎn)表PT，并且須要在表PT中快速查找取得極值的結(jié)點(diǎn)，等等。這都須要較大的存儲(chǔ)空間，在最壞狀況下，分支限界法須要的空間困難性是指數(shù)階。2023/2/14第9章分支限界法Page229.2.1TSP問題9.2.2多段圖的最短路徑問題9.2圖問題中的分支限界法2023/2/14第9章分支限界法Page23TSP問題是指旅行家要旅行n個(gè)城市，要求各個(gè)城市閱歷且僅閱歷一次然后回到動(dòng)身城市，并要求所走的路程最短。271563134253984C=∞31583∞67916∞42574∞38923∞(a)一個(gè)無向圖(b)無向圖的代價(jià)矩陣圖9.4無向圖及其代價(jià)矩陣9.2.1TSP問題2023/2/14第9章分支限界法Page24接受貪心法求得近似解為1→3→5→4→2→1，其路徑長度為1+2+3+7+3=16，這可以作為TSP問題的上界。把矩陣中每一行最小的元素相加，可以得到一個(gè)簡潔的下界，其路徑長度為1+3+1+3+2=10，但是還有一個(gè)信息量更大的下界：考慮一個(gè)TSP問題的完整解，在每條路徑上，每個(gè)城市都有兩條鄰接邊，一條是進(jìn)入這個(gè)城市的，另一條是離開這個(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è)合法的選擇（可能沒有構(gòu)成哈密頓回路），它僅僅給出了一個(gè)參考下界。

2023/2/14第9章分支限界法Page25部分解的目標(biāo)函數(shù)值的計(jì)算方法

例如圖9.4所示無向圖，假如部分解包含邊(1,4)，則該部分解的下界是lb=((1+5)+(3+6)+(1+2)+(3+5)+(2+3))/2=16。

2023/2/14第9章分支限界法Page2641→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問題示例2023/2/14第9章分支限界法Page27應(yīng)用分支限界法求解圖9.4所示無向圖的TSP問題，其搜尋空間如圖9.5所示，具體的搜尋過程如下（加黑表示該路徑上已經(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，路徑長度為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，路徑長度為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，路徑長度為5，目標(biāo)函數(shù)的值為((1+5)+(3+6)+(1+2)+(3+5)+(2+3))/2=16，將結(jié)點(diǎn)4加入表PT中；在結(jié)點(diǎn)5，從城市1到城市5，路徑長度為8，目標(biāo)函數(shù)的值為((1+8)+(3+6)+(1+2)+(3+5)+(2+8))/2=19，超出目標(biāo)函數(shù)的界，將結(jié)點(diǎn)5丟棄；2023/2/14第9章分支限界法Page28（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，將結(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=14，將結(jié)點(diǎn)11加入表PT中；2023/2/14第9章分支限界法Page29（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))/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è)可行解，其路徑長度為16；2023/2/14第9章分支限界法Page30（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）在表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)的解1→3→5→4→2→1即是TSP問題的最優(yōu)解，搜尋過程結(jié)束。2023/2/14第9章分支限界法Page31(g)擴(kuò)展結(jié)點(diǎn)16后的狀態(tài)，最優(yōu)解為1→3→5→4→2→1圖9.6TSP問題最優(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/14第9章分支限界法Page32算法9.1——TSP問題

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

2．將待處理結(jié)點(diǎn)表PT初始化為空；

3．for(i=1;i<=n;i++)x[i]=0;4．k=1;x[1]=1;//從頂點(diǎn)1出發(fā)求解TSP問題

5．while(k>=1)5.1i=k+1;5.2x[i]=1;5.3while(x[i]<=n)5.3.1如果路徑上頂點(diǎn)不重復(fù)，則

5.3.1.1根據(jù)式9.2計(jì)算目標(biāo)函數(shù)值lb；

5.3.1.2if(lb<=up)將路徑上的頂點(diǎn)和lb值存儲(chǔ)在表PT中；

5.3.2x[i]=x[i]+1;5.4若i=n且葉子結(jié)點(diǎn)的目標(biāo)函數(shù)值在表PT中最小則將該葉子結(jié)點(diǎn)對(duì)應(yīng)的最優(yōu)解輸出；

5.5否則，若i=n，則在表PT中取葉子結(jié)點(diǎn)的目標(biāo)函數(shù)值最小的結(jié)點(diǎn)lb，令up=lb，將表PT中目標(biāo)函數(shù)值lb超出up的結(jié)點(diǎn)刪除；

5.6k=表PT中l(wèi)b最小的路徑上頂點(diǎn)個(gè)數(shù)；偽代碼2023/2/14第9章分支限界法Page33設(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多段圖的最短路徑問題是求從源點(diǎn)到終點(diǎn)的最小代價(jià)路徑。9.2.2多段圖的最短路徑問題2023/2/14第9章分支限界法Page34對(duì)圖9.7所示多段圖應(yīng)用貪心法求得近似解為0→2→5→8→9，其路徑代價(jià)為2+7+6+3=18，這可以作為多段圖最短路徑問題的上界。把每一段最小的代價(jià)相加，可以得到一個(gè)特殊簡潔的下界，其路徑長度為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段的最短邊第＋2023/2/14第9章分支限界法Page35應(yīng)用分支限界法求解圖9.7所示多段圖的最短路徑問題，其搜尋空間如圖9.8所示，具體的搜尋過程如下（加黑表示該路徑上已經(jīng)確定的邊）：（1）在根結(jié)點(diǎn)1，依據(jù)限界函數(shù)計(jì)算目標(biāo)函數(shù)的值為14；（2）在結(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加入待處理結(jié)點(diǎn)表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)行搜尋；2023/2/14第9章分支限界法Page36（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)7，第3段選擇邊<5,7>，可干脆確定第4段的邊<7,9>，目標(biāo)函數(shù)值為lb=3+4+8+7=22，為一個(gè)可行解但超出目標(biāo)函數(shù)的界，將其丟棄；在結(jié)點(diǎn)8，第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中最小的，所以，結(jié)點(diǎn)8代表的解即是問題的最優(yōu)解，搜尋過程結(jié)束。2023/2/14第9章分支限界法Page37640→1lb=20231startlb=140→2lb=170→3lb=15×圖9.8分支限界法求解多段圖的最短路徑問題示例(×表示該結(jié)點(diǎn)被丟棄，結(jié)點(diǎn)上方的數(shù)組表示搜索順序)53→5lb=163→6lb=18875→7lb=225→8lb=16×2023/2/14第9章分支限界法Page38為了在搜尋過程中構(gòu)建搜尋經(jīng)過的樹結(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段，<第i段頂點(diǎn),第i+1段頂點(diǎn)>lb)，在搜尋過程中表PT和表ST的狀態(tài)如下：(b)擴(kuò)展結(jié)點(diǎn)4后的狀態(tài)(c)擴(kuò)展結(jié)點(diǎn)5后的狀態(tài)，最優(yōu)解為0→3→5→8→圖9.9多段圖的最短路徑問題最優(yōu)解的確定(1,<0,2>17)(1,<0,3>15)(1,<0,2>17)(2,<3,5>16)(2,<3,6>18)(1,<0,3>15)(1,<0,2>17)(2,<3,6>18)(3,<5,8>16)(1,<0,3>15)(2,<3,5>16)(a)擴(kuò)展根結(jié)點(diǎn)后的狀態(tài)PTSTSTPTST回溯過程是：(3,<5,8>16)→(2,<3,5>16)→(1,<0,3>15)。PT2023/2/14第9章分支限界法Page39算法9.2——多段圖的最短路徑問題

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

2．將待處理結(jié)點(diǎn)表PT初始化為空；

3．for(i=1;i<=k;i++)x[i]=0;4．i=1;u=0;//求解第i段

5．while(i>=1)5.1對(duì)頂點(diǎn)u的所有鄰接點(diǎn)v5.1.1根據(jù)式9.3計(jì)算目標(biāo)函數(shù)值lb;5.1.2若lb<=up，則將i,<u,v>,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.1up=表PT中的葉子結(jié)點(diǎn)最小的lb值;5.3.2將表PT中目標(biāo)函數(shù)值超出up的結(jié)點(diǎn)刪除；

5.4u=表PT中l(wèi)b最小的結(jié)點(diǎn)的v值；

5.5i=表PT中l(wèi)b最小的結(jié)點(diǎn)的i值；i++;偽代碼2023/2/14第9章分支限界法Page409.3.1任務(wù)支配問題9.3.2批處理作業(yè)調(diào)度問題9.3組合問題中的分支限界法2023/2/14第9章分支限界法Page41任務(wù)支配問題要求把n項(xiàng)任務(wù)支配給n個(gè)人，每個(gè)人完成每項(xiàng)任務(wù)的成本不同，要求支配總成本最小的最優(yōu)支配方案。如圖9.10所示是一個(gè)任務(wù)支配的成本矩陣。C＝9278643758187694任務(wù)1任務(wù)2任務(wù)3任務(wù)4人員a人員b人員c人員d圖9.10任務(wù)分配問題的成本矩陣9.3.1任務(wù)支配問題2023/2/14第9章分支限界法Page42求最優(yōu)支配成本的上界和下界考慮隨意一個(gè)可行解，例如矩陣中的對(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=14。明顯，14是一個(gè)更好的上界。為了獲得下界，考慮人員a執(zhí)行全部任務(wù)的最小代價(jià)是2，人員b執(zhí)行全部任務(wù)的最小代價(jià)是3，人員c執(zhí)行全部任務(wù)的最小代價(jià)是1，人員d執(zhí)行全部任務(wù)的最小代價(jià)是4。因此，將每一行的最小元素加起來就得到解的下界，其成本是2+3+1+4=10。須要強(qiáng)調(diào)的是，這個(gè)解并不是一個(gè)合法的選擇（3和1來自于矩陣的同一列），它僅僅給出了一個(gè)參考下界，這樣，最優(yōu)值確定是[10,14]之間的某個(gè)值。2023/2/14第9章分支限界法Page43設(shè)當(dāng)前已對(duì)人員1～i支配了任務(wù)，并且獲得了成本v，則限界函數(shù)可以定義為：（式9.4）2023/2/14第9章分支限界法Page44（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，獲得的成本為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ù)支配問題，對(duì)解空間樹的搜尋如圖9.11所示，具體的搜尋過程如下：（1）在根結(jié)點(diǎn)1，沒有支配任務(wù)，依據(jù)限界函數(shù)估算目標(biāo)函數(shù)值為2+3+1+4=10；2023/2/14第9章分支限界法Page45（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ù)值為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丟棄；2023/2/14第9章分支限界法Page46（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)的解即是問題的最優(yōu)解，搜尋結(jié)束。2023/2/14第9章分支限界法Page47圖9.11分支限界法求解任務(wù)支配問題示例(×表示該結(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=203→clb=134→dlb=1323567891213111××××2023/2/14第9章分支限界法Page48為了在搜尋過程中構(gòu)建搜尋經(jīng)過的樹結(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ù),<任務(wù)k,人員i>lb)(e)擴(kuò)展結(jié)點(diǎn)11后的狀態(tài)，最優(yōu)解為2→a1→b3→c4→d圖9.12任務(wù)分配問題最優(yōu)解的確定(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)(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,<4,b>14)(3,<1,c>14)(3,<4,d>13)PTSTPTST

ST

回溯過程是：(3,<4,d>13)→(1,<3,c>13)→(2,<1,b>13)→(0,<2,a>10)。2023/2/14第9章分支限界法Page49算法9.3——任務(wù)分配問題

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

2．將待處理結(jié)點(diǎn)表PT初始化為空；

3．for(i=1;i<=n;i++)x[i]=0;4．k=1;i=0;//為第k個(gè)人分配任務(wù)，i為第k-1個(gè)人分配的任務(wù)

5．while(k>=1)5.1x[k]=1;5.2while(x[k]<=n)5.2.1如果人員k分配任務(wù)x[k]不發(fā)生沖突，則

5.2.1.1根據(jù)式9.4計(jì)算目標(biāo)函數(shù)值lb;5.2.1.2若lb<=up，則將i,<x[k],k>lb存儲(chǔ)在表PT中；

5.2.2x[k]=x[k]+1;5.3如果k==n且葉子結(jié)點(diǎn)的lb值在表PT中最小，則輸出該葉子結(jié)點(diǎn)對(duì)應(yīng)的最優(yōu)解；

5.4否則，如果k==n且表PT中的葉子結(jié)點(diǎn)的lb值不是最小，則

5.4.1up=表PT中的葉子結(jié)點(diǎn)最小的lb值;5.4.2將表PT中超出目標(biāo)函數(shù)界的結(jié)點(diǎn)刪除；

5.5i=表PT中l(wèi)b最小的結(jié)點(diǎn)的x[k]值；

5.6k=表PT中l(wèi)b最小的結(jié)點(diǎn)的k值；k++;偽代碼2023/2/14第9章分支限界法Page50給定n個(gè)作業(yè)的集合J={J1,J2,…,Jn}，每個(gè)作業(yè)都有3項(xiàng)任務(wù)分別在3臺(tái)機(jī)器上完成，作業(yè)Ji須要機(jī)器j的處理時(shí)間為tij（1≤i≤n,1≤j≤3），每個(gè)作業(yè)必需先由機(jī)器1處理，再由機(jī)器2處理，最終由機(jī)器3處理。批處理作業(yè)調(diào)度問題要求確定這n個(gè)作業(yè)的最優(yōu)處理依次，使得從第1個(gè)作業(yè)在機(jī)器1上處理起先，到最終一個(gè)作業(yè)在機(jī)器3上處理結(jié)束所需的時(shí)間最少。明顯，批處理作業(yè)的一個(gè)最優(yōu)調(diào)度應(yīng)使機(jī)器1沒有空閑時(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)度問題2023/2/14第9章分支限界法Page51T＝57910529957810J1J2J3J4機(jī)器1機(jī)器2機(jī)器3若處理依次為(J2,J3,J1,J4)，則從作業(yè)2在機(jī)器1處理起先到作業(yè)4在機(jī)器3處理完成的調(diào)度方案如圖9.14所示。J2:10J3:9J1:5J4:7機(jī)器1機(jī)器2機(jī)器3

圖9.14批處理調(diào)度問題的調(diào)度方案空閑:10J2:5J3:9J1:7J4:8空閑:15J2:2J3:5J1:9J4:10設(shè)J={J1,J2,J3,J4}是4個(gè)待處理的作業(yè)，每個(gè)作業(yè)的處理依次相同，即先在機(jī)器1上處理，然后在機(jī)器2上處理，最終在機(jī)器3上處理，須要的處理