第15講 分支定界法

第6章分支限界法理解分支限界法的剪枝搜索策略。掌握分支限界法的算法框架：（1）隊列式(FIFO)分支限界法（2）優(yōu)先隊列式分支限界法通過應(yīng)用范例學(xué)習(xí)分支限界法的設(shè)計策略。學(xué)習(xí)要點分支限界法的基本思想分支限界法與回溯法（1）求解目標(biāo)：回溯法的求解目標(biāo)是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。（2）搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費優(yōu)先的方式搜索解空間樹。

分支限界法常以廣度優(yōu)先或以最小耗費（最大效益）優(yōu)先的方式搜索問題的解空間樹。此后，從活結(jié)點表中取下一結(jié)點成為當(dāng)前擴展結(jié)點，并重復(fù)上述結(jié)點擴展過程。這個過程一直持續(xù)到找到所需的解或活結(jié)點表為空時為止。在分支限界法中，每一個活結(jié)點只有一次機會成為擴展結(jié)點?；罱Y(jié)點一旦成為擴展結(jié)點，就一次性產(chǎn)生其所有兒子結(jié)點。在這些兒子結(jié)點中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點被舍棄，其余兒子結(jié)點被加入活結(jié)點表中。分支限界法的基本思想分支限界法的基本思想常見的兩種分支限界法（1）隊列式(FIFO)分支限界法按照隊列先進(jìn)先出（FIFO）原則選取下一個節(jié)點為擴展節(jié)點。

（2）優(yōu)先隊列式分支限界法按照優(yōu)先隊列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的節(jié)點成為當(dāng)前擴展節(jié)點。

分支限界法首先確定一個合理的限界函數(shù)，并根據(jù)限界函數(shù)確定目標(biāo)函數(shù)的界[down,up]。然后，按照廣度優(yōu)先策略遍歷問題的解空間樹，在分支結(jié)點上，依次搜索該結(jié)點的所有孩子結(jié)點，分別估算這些孩子結(jié)點的目標(biāo)函數(shù)的可能取值。如果某孩子結(jié)點的目標(biāo)函數(shù)可能取得的值超出目標(biāo)函數(shù)的界，則將其丟棄，因為從這個結(jié)點生成的解不會比目前已經(jīng)得到的解更好；否則，將其加入待處理結(jié)點表中。依次從表PT中選取使目標(biāo)函數(shù)的值取得極值的結(jié)點成為當(dāng)前擴展結(jié)點，重復(fù)上述過程，直到找到最優(yōu)解。隨著這個遍歷過程的不斷深入，表PT中所估算的目標(biāo)函數(shù)的界越來越接近問題的最優(yōu)解。當(dāng)搜索到一個葉子結(jié)點時，如果該結(jié)點的目標(biāo)函數(shù)值是表PT中的極值（對于最小化問題，是極小值；對于最大化問題，是極大值），則該葉子結(jié)點對應(yīng)的解就是問題的最優(yōu)解；否則，根據(jù)這個葉子結(jié)點調(diào)整目標(biāo)函數(shù)的界（對于最小化問題，調(diào)整上界；對于最大化問題，調(diào)整下界），依次考察表PT中的結(jié)點，將超出目標(biāo)函數(shù)界的結(jié)點丟棄，然后從表PT中選取使目標(biāo)函數(shù)取得極值的結(jié)點繼續(xù)進(jìn)行擴展。單源最短路徑問題單源最短路徑問題1.問題描述下面以一個例子來說明單源最短路徑問題：在下圖所給的有向圖G中，每一邊都有一個非負(fù)邊權(quán)。要求圖G的從源頂點s到目標(biāo)頂點t之間的最短路徑。2347292235122231333O單源最短路徑問題2.剪枝策略在算法擴展結(jié)點的過程中，一旦發(fā)現(xiàn)一個結(jié)點的下界不小于當(dāng)前找到的最短路長，則算法剪去以該結(jié)點為根的子樹。在算法中，利用結(jié)點間的控制關(guān)系進(jìn)行剪枝。從源頂點s出發(fā)，2條不同路徑到達(dá)圖G的同一頂點。由于兩條路徑的路長不同，因此可以將路長長的路徑所對應(yīng)的樹中的結(jié)點為根的子樹剪去。

單源最短路徑問題3.算法思想

解單源最短路徑問題的優(yōu)先隊列式分支限界法用一極小堆來存儲活結(jié)點表。其優(yōu)先級是結(jié)點所對應(yīng)的當(dāng)前路長。

算法從圖G的源頂點s和空優(yōu)先隊列開始。結(jié)點s被擴展后，它的兒子結(jié)點被依次插入堆（待處理結(jié)點表，以下簡稱表PT）中。此后，算法從堆中取出具有最小當(dāng)前路長的結(jié)點作為當(dāng)前擴展結(jié)點，并依次檢查與當(dāng)前擴展結(jié)點相鄰的所有頂點。如果從當(dāng)前擴展結(jié)點i到頂點j有邊可達(dá)，且從源出發(fā)，途經(jīng)頂點i再到頂點j的所相應(yīng)的路徑的長度小于當(dāng)前最優(yōu)路徑長度，則將該頂點作為活結(jié)點插入到活結(jié)點優(yōu)先隊列中。這個結(jié)點的擴展過程一直繼續(xù)到活結(jié)點優(yōu)先隊列為空時為止。單源最短路徑問題1.問題描述下圖是用優(yōu)先隊列式分支限界法解有向圖G的單源最短路徑問題產(chǎn)生的解空間樹。其中，每一個結(jié)點旁邊的數(shù)字表示該結(jié)點所對應(yīng)的當(dāng)前路長。第1層第2層第4層第5層第3層2347292235122231333O目前的最短路徑是8，一旦發(fā)現(xiàn)某個節(jié)點的下界不小于這個最短路進(jìn)，則剪枝。2347292235122231333O利用節(jié)點的控制關(guān)系剪枝將會產(chǎn)生重復(fù)的子樹，剪枝

while(true){for(intj=1;j<=n;j++)if((c[E.node][j]<inf)&&(E.length+c[E.node][j]<dist[j])){//頂點E.node到頂點j可達(dá)，且滿足控制約束dist[j]=E.length+c[E.node][j];prev[j]=E.node;//加入活結(jié)點優(yōu)先隊列MinHeapNode<Type>N;N.node=j;//頂點編號為jN.length=dist[j];H.Insert(N);}try{H.DeleteMin(E);}//取下一擴展結(jié)點catch(OutOfBounds){break;}//優(yōu)先隊列空}頂點i和j間有邊，且此路徑長小于原先從原點到j(luò)的路徑長。這個判斷，實現(xiàn)了剪枝dist:最短距離數(shù)組prev:前驅(qū)頂點數(shù)組E：當(dāng)前的擴展節(jié)點c:鄰接矩陣H：活節(jié)點優(yōu)先隊列記載最短路徑

缺乏上界函數(shù)減枝優(yōu)先權(quán)隊列VS.先進(jìn)先出隊列0/1背包問題0/1背包問題。假設(shè)有4個物品，其重量分別為(4,7,5,3)，價值分別為(40,42,25,12)，背包容量W=10。首先，將給定物品按單位重量價值從大到小排序，結(jié)果如下：物品重量(w)價值(v)價值/重量(v/w)144010274263525543124應(yīng)用貪心法求得近似解為(1,0,0,0)，獲得的價值為40，這可以作為0/1背包問題的下界。如何求得0/1背包問題的一個合理的上界呢？考慮最好情況，背包中裝入的全部是第1個物品且可以將背包裝滿，則可以得到一個非常簡單的上界的計算方法：ub=W×(v1/w1)=10×10=100。于是，得到了目標(biāo)函數(shù)的界[40,100]。

限界函數(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=6523456789×1分支限界法求解0/1背包問題分支限界法求解0/1背包問題，具體的搜索過程如下：（1）在根結(jié)點1，沒有將任何物品裝入背包，因此，背包的重量和獲得的價值均為0，根據(jù)限界函數(shù)計算結(jié)點1的目標(biāo)函數(shù)值為10×10=100；（2）在結(jié)點2，將物品1裝入背包，因此，背包的重量為4，獲得的價值為40，目標(biāo)函數(shù)值為40+(10-4)×6=76，將結(jié)點2加入待處理結(jié)點表PT中；在結(jié)點3，沒有將物品1裝入背包，因此，背包的重量和獲得的價值仍為0，目標(biāo)函數(shù)值為10×6＝60，將結(jié)點3加入表PT中；（3）在表PT中選取目標(biāo)函數(shù)值取得極大的結(jié)點2優(yōu)先進(jìn)行搜索；（4）在結(jié)點4，將物品2裝入背包，因此，背包的重量為11，不滿足約束條件，將結(jié)點4丟棄；在結(jié)點5，沒有將物品2裝入背包，因此，背包的重量和獲得的價值與結(jié)點2相同，目標(biāo)函數(shù)值為40+(10-4)×5=70，將結(jié)點5加入表PT中；（5）在表PT中選取目標(biāo)函數(shù)值取得極大的結(jié)點5優(yōu)先進(jìn)行搜索；（6）在結(jié)點6，將物品3裝入背包，因此，背包的重量為9，獲得的價值為65，目標(biāo)函數(shù)值為65+(10-9)×4=69，將結(jié)點6加入表PT中；在結(jié)點7，沒有將物品3裝入背包，因此，背包的重量和獲得的價值與結(jié)點5相同，目標(biāo)函數(shù)值為40+(10-4)×4＝64，將結(jié)點6加入表PT中；（7）在表PT中選取目標(biāo)函數(shù)值取得極大的結(jié)點6優(yōu)先進(jìn)行搜索；（8）在結(jié)點8，將物品4裝入背包，因此，背包的重量為12，不滿足約束條件，將結(jié)點8丟棄；在結(jié)點9，沒有將物品4裝入背包，因此，背包的重量和獲得的價值與結(jié)點6相同，目標(biāo)函數(shù)值為65；（9）由于結(jié)點9是葉子結(jié)點，同時結(jié)點9的目標(biāo)函數(shù)值是表PT中的極大值，所以，結(jié)點9對應(yīng)的解即是問題的最優(yōu)解，搜索結(jié)束。分支限界法的時間性能

分支限界法和回溯法實際上都屬于窮舉法，當(dāng)然不能指望它有很好的最壞時間復(fù)雜性，遍歷具有指數(shù)階個結(jié)點的解空間樹，在最壞情況下，時間復(fù)雜性肯定為指數(shù)階。與回溯法不同的是，分支限界法首先擴展解空間樹中的上層結(jié)點，并采用限界函數(shù)，有利于實行大范圍剪枝，同時，根據(jù)限界函數(shù)不斷調(diào)整搜索方向，選擇最有可能取得最優(yōu)解的子樹優(yōu)先進(jìn)行搜索。所以，如果選擇了結(jié)點的合理擴展順序以及設(shè)計了一個好的限界函數(shù)，分支界限法可以快速得到問題的解。分支限界法的較高效率是以付出一定代價為基礎(chǔ)的，其工作方式也造成了算法設(shè)計的復(fù)雜性。

首先，一個更好的限界函數(shù)通常需要花費更多的時間計算相應(yīng)的目標(biāo)函數(shù)值，而且對于具體的問題實例，通常需要進(jìn)行大量實驗，才能確定一個好的限界函數(shù)；

其次，由于分支限界法對解空間樹中結(jié)點的處理是跳躍式的，因此，在搜索到某個葉子結(jié)點得到最優(yōu)值時，為了從該葉子結(jié)點求出對應(yīng)的最優(yōu)解中的各個分量，需要對每個擴展結(jié)點保存該結(jié)點到根結(jié)點的路徑，或者在搜索過程中構(gòu)建搜索經(jīng)過的樹結(jié)構(gòu)，這使得算法的設(shè)計較為復(fù)雜；再次，算法要維護(hù)一個待處理結(jié)點表PT，并且需要在表PT中快速查找取得極值的結(jié)點，等等。這都需要較大的存儲空間，在最壞情況下，分支限界法需要的空間復(fù)雜性是指數(shù)階。任務(wù)分配問題任務(wù)分配問題要求把n項任務(wù)分配給n個人，每個人完成每項任務(wù)的成本不同，要求分配總成本最小的最優(yōu)分配方案。如下圖所示是一個任務(wù)分配的成本矩陣。

C＝9278643758187694任務(wù)1任務(wù)2任務(wù)3任務(wù)4人員a人員b人員c人員d任務(wù)分配問題的成本矩陣求最優(yōu)分配成本的上界和下界考慮任意一個可行解，例如矩陣中的對角線是一個合法的選擇，表示將任務(wù)1分配給人員a、任務(wù)2分配給人員b、任務(wù)3分配給人員c、任務(wù)4分配給人員d，其成本是9+4+1+4=18；或者應(yīng)用貪心法求得一個近似解：將任務(wù)2分配給人員a、任務(wù)3分配給人員b、任務(wù)1分配給人員c、任務(wù)4分配給人員d，其成本是2+3+5+4=14。顯然，14是一個更好的上界。為了獲得下界，考慮人員a執(zhí)行所有任務(wù)的最小代價是2，人員b執(zhí)行所有任務(wù)的最小代價是3，人員c執(zhí)行所有任務(wù)的最小代價是1，人員d執(zhí)行所有任務(wù)的最小代價是4。因此，將每一行的最小元素加起來就得到解的下界，其成本是2+3+1+4=10。需要強調(diào)的是，這個解并不是一個合法的選擇（3和1來自于矩陣的同一列），它僅僅給出了一個參考下界，這樣，最優(yōu)值一定是[10,14]之間的某個值。設(shè)當(dāng)前已對人員1～i分配了任務(wù)，并且獲得了成本v，則限界函數(shù)可以定義為：（2）在結(jié)點2，將任務(wù)1分配給人員a，獲得的成本為9，目標(biāo)函數(shù)值為9+(3+1+4)=17，超出目標(biāo)函數(shù)的界[10,14]，將結(jié)點2丟棄；在結(jié)點3，將任務(wù)2分配給人員a，獲得的成本為2，目標(biāo)函數(shù)值為2+(3+1+4)=10，將結(jié)點3加入待處理結(jié)點表PT中；在結(jié)點4，將任務(wù)3分配給人員a，獲得的成本為7，目標(biāo)函數(shù)值為7+(3+1+4)=15，超出目標(biāo)函數(shù)的界[10,14]，將結(jié)點4丟棄；在結(jié)點5，將任務(wù)4分配給人員a，獲得的成本為8，目標(biāo)函數(shù)值為8+(3+1+4)=16，超出目標(biāo)函數(shù)的界[10,14]，將結(jié)點5丟棄；應(yīng)用分支限界法求解任務(wù)分配問題，具體的搜索過程如下：（1）在根結(jié)點1，沒有分配任務(wù)，根據(jù)限界函數(shù)估算目標(biāo)函數(shù)值為2+3+1+4=10；

（3）在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點3優(yōu)先進(jìn)行搜索；（4）在結(jié)點6，將任務(wù)1分配給人員b，獲得的成本為2+6=8，目標(biāo)函數(shù)值為8+(1+4)＝13，將結(jié)點6加入表PT中；在結(jié)點7，將任務(wù)3分配給人員b，獲得的成本為2+3=5，目標(biāo)函數(shù)值為5+(1+4)＝10，將結(jié)點7加入表PT中；在結(jié)點8。將任務(wù)4分配給人員b，獲得的成本為2+7=9，目標(biāo)函數(shù)值為9+(1+4)＝14，將結(jié)點8加入表PT中；

（5）在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點7優(yōu)先進(jìn)行搜索；（6）在結(jié)點9，將任務(wù)1分配給人員c，獲得的成本為5+5=10，目標(biāo)函數(shù)值為10+4=14，將結(jié)點9加入表PT中；在結(jié)點10，將任務(wù)4分配給人員c，獲得的成本為5+8=13，目標(biāo)函數(shù)值為13+4=17，超出目標(biāo)函數(shù)的界[10,14]，將結(jié)點10丟棄；（7）在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點6優(yōu)先進(jìn)行搜索；（8）在結(jié)點11，將任務(wù)3分配給人員c，獲得的成本為8+1=9，目標(biāo)函數(shù)值為9+4=13，將結(jié)點11加入表PT中；在結(jié)點12，將任務(wù)4分配給人員c，獲得的成本為8+8=16，目標(biāo)函數(shù)值為16+4=20，超出目標(biāo)函數(shù)的界[10,14]，將結(jié)點12丟棄；（9）在表PT中選取目標(biāo)函數(shù)值極小的結(jié)點11優(yōu)先進(jìn)行搜索；（10）在結(jié)點13，將任務(wù)4分配給人員d，獲得的成本為9+4=13，目標(biāo)函數(shù)值為13，由于結(jié)點13是葉子結(jié)點，同時結(jié)點13的目標(biāo)函數(shù)值是表PT中的極小值，所以，結(jié)點13對應(yīng)的解即是問題的最優(yōu)解，搜索結(jié)束。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=13分支限界法求解任務(wù)分配問題示例(×表示該結(jié)點被丟棄，結(jié)點上方的數(shù)組表示搜索順序)23567891213111××××為了在搜索過程中構(gòu)建搜索經(jīng)過的樹結(jié)構(gòu)，設(shè)一個表ST，在表PT中取出最小值結(jié)點進(jìn)行擴充時，將最小值結(jié)點存儲到表ST中，表PT和表ST的數(shù)據(jù)結(jié)構(gòu)為(人員i-1分配的任務(wù),<任務(wù)k,人員i>lb)(e)擴展結(jié)點11后的狀態(tài)，最優(yōu)解為2→a1→b3→c4→d任務(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)擴展根結(jié)點后的狀態(tài)(b)擴展結(jié)點3后的狀態(tài)PTSTPTST

PT

(c)擴展結(jié)點7后的狀態(tài)(d)擴展結(jié)點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)。算法任務(wù)分配問題1．根據(jù)限界函數(shù)計算目標(biāo)函數(shù)的下界down；采用貪心法得到上界up；2．將待處理結(jié)點表PT初始化為空；3．for(i=1;i<=n;i++)x[i]=0;4．k=1;i=0;//為第k個人分配任務(wù)，i為第k-1個人分配的任務(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計算目標(biāo)函數(shù)值lb;5.2.1.2若lb<=up，則將i,<x[k],k>lb存儲在表PT中；5.2.2x[k]=x[k]+1;5.3如果k==n且葉子結(jié)點的lb值在表PT中最小，則輸出該葉子結(jié)點對應(yīng)的最優(yōu)解；5.4否則，如果k==n且表PT中的葉子結(jié)點的lb值不是最小，則5.4.1up=表PT中的葉子結(jié)點最小的lb值;5.4.2將表PT中超出目標(biāo)函數(shù)界的結(jié)點刪除；5.5i=表PT中l(wèi)b最小的結(jié)點的x[k]值；5.6k=表PT中l(wèi)b最小的結(jié)點的k值；k++;偽代碼4-QueenproblemAlivenodetableBranchandBoundneedsatablewhichholdsthealivenodes.x1＝12x1＝23x1＝34x1＝454-Queenproblem11118x3＝219x3＝41819220x3＝221x3＝321x2＝267x2＝3x2＝4830x4＝330·829x2＝110x2＝311x2＝422x3＝123x3＝331x4＝312x2＝113x2＝214x2＝424x3＝225x3