1、分支限界法,1. 概 述,2. 圖問題中的分支限界法,3. 組合問題中的分支限界法,我們已經(jīng)知道，在現(xiàn)實(shí)世界中，當(dāng)問題的規(guī)模變得很大時，窮盡搜索是不可能的，所以有必要找到某種啟發(fā)式方法去掉那部分我們明知道不可能在其中找到最優(yōu)解的搜索空間。 分支限界法就是這樣的一種啟發(fā)式方法，它建立在對搜索空間的基礎(chǔ)上。將整個搜索空間想象成樹狀結(jié)構(gòu)，根據(jù)計算出的特定解的代價剪去不感興趣的分支。,分支限界法首先確定一個合理的限界函數(shù)，并根據(jù)限界函數(shù)確定評估函數(shù)的界down, up 。然后，按照廣度優(yōu)先策略遍歷問題的解空間樹，在分支結(jié)點(diǎn)上，依次搜索該結(jié)點(diǎn)的所有孩子結(jié)點(diǎn)，分別估算這些孩子結(jié)點(diǎn)的評估函數(shù)的可能取值，如果

2、某孩子結(jié)點(diǎn)的評估函數(shù)可能取得的值超出評估函數(shù)的界，則將其丟棄，因?yàn)閺倪@個結(jié)點(diǎn)生成的解不會比目前已經(jīng)得到的解更好；否則，將其加入待處理結(jié)點(diǎn)表中。依次從表中選取使評估函數(shù)的值取得極值的結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，重復(fù)上述過程，直到找到最優(yōu)解。,解空間樹的動態(tài)搜索（2）,例：0/1背包問題。假設(shè)有4個物品，其重量分別為(4, 7, 5, 3)，價值分別為(40, 42, 25, 12)，背包容量W=10。首先，將給定物品按單位重量價值從大到小排序，結(jié)果如下：,應(yīng)用貪心法求得近似解為(1, 0, 0, 0)，獲得的價值為40，這可以作為0/1背包問題的下界。 如何求得0/1背包問題的一個合理的上界呢？考慮最

3、好情況，背包中裝入的全部是第1個物品且可以將背包裝滿，則可以得到一個非常簡單的上界的計算方法：ub=W(v1/w1)=1010=100。于是，得到了評估函數(shù)的界40, 100。 限界函數(shù)為：,分支限界法求解0/1背包問題,分支限界法求解0/1背包問題，其搜索空間如圖9.1所示，具體的搜索過程如下： （1）在根結(jié)點(diǎn)1，沒有將任何物品裝入背包，因此，背包的重量和獲得的價值均為0，根據(jù)限界函數(shù)計算結(jié)點(diǎn)1的評估函數(shù)值為1010=100； （2）在結(jié)點(diǎn)2，將物品1裝入背包，因此，背包的重量為4，獲得的價值為40，評估函數(shù)值為40 + (10-4)6=76，將結(jié)點(diǎn)2加入待處理結(jié)點(diǎn)表PT中；在結(jié)點(diǎn)3，沒有將

4、物品1裝入背包，因此，背包的重量和獲得的價值仍為0，評估函數(shù)值為10660，將結(jié)點(diǎn)3加入表PT中； （3）在表PT中選取評估函數(shù)值取得極大的結(jié)點(diǎn)2優(yōu)先進(jìn)行搜索；,（4）在結(jié)點(diǎn)4，將物品2裝入背包，因此，背包的重量為11，不滿足約束條件，將結(jié)點(diǎn)4丟棄；在結(jié)點(diǎn)5，沒有將物品2裝入背包，因此，背包的重量和獲得的價值與結(jié)點(diǎn)2相同，評估函數(shù)值為40 + (10-4)5=70，將結(jié)點(diǎn)5加入表PT中； （5）在表PT中選取評估函數(shù)值取得極大的結(jié)點(diǎn)5優(yōu)先進(jìn)行搜索； （6）在結(jié)點(diǎn)6，將物品3裝入背包，因此，背包的重量為9，獲得的價值為65，評估函數(shù)值為65 + (10-9)4=69，將結(jié)點(diǎn)6加入表PT中；在結(jié)點(diǎn)

5、7，沒有將物品3裝入背包，因此，背包的重量和獲得的價值與結(jié)點(diǎn)5相同，評估函數(shù)值為40 + (10-4)464，將結(jié)點(diǎn)6加入表PT中；,（7）在表PT中選取評估函數(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é)點(diǎn)6相同，評估函數(shù)值為65； （9）由于結(jié)點(diǎn)9是葉子結(jié)點(diǎn)，同時結(jié)點(diǎn)9的評估函數(shù)值是表PT中的極大值，所以，結(jié)點(diǎn)9對應(yīng)的解即是問題的最優(yōu)解，搜索結(jié)束。,分支限界法的設(shè)計思想,假設(shè)求解最大化問題，解向量為X=(x1, x2, , xn)，其中，xi的取值范

6、圍為某個有窮集合Si，|Si|=ri（1in）。在使用分支限界法搜索問題的解空間樹時，首先根據(jù)限界函數(shù)估算目標(biāo)函數(shù)的界down, up，然后從根結(jié)點(diǎn)出發(fā)，擴(kuò)展根結(jié)點(diǎn)的r1個孩子結(jié)點(diǎn)，從而構(gòu)成分量x1的r1種可能的取值方式。對這r1個孩子結(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),若某孩子結(jié)點(diǎn)的目標(biāo)函數(shù)值超出目標(biāo)函數(shù)的界，則將該孩子結(jié)點(diǎn)丟棄；否則，將該孩子結(jié)點(diǎn)保存在

7、待處理結(jié)點(diǎn)表PT中。從表PT中選取使目標(biāo)函數(shù)取得極大值的結(jié)點(diǎn)作為下一次擴(kuò)展的根結(jié)點(diǎn)，重復(fù)上述過程，當(dāng)?shù)竭_(dá)一個葉子結(jié)點(diǎn)時，就得到了一個可行解X=(x1, x2, , xn)及其目標(biāo)函數(shù)值bound(x1, x2, , xn)。 如果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)，說明還存在某個部分解對應(yīng)的結(jié)點(diǎn)，其上界大于bound(x1, x2, , xn)。于是，用bound(x1, x2

8、, , 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)，繼續(xù)搜索，直到某個葉子結(jié)點(diǎn)的目標(biāo)函數(shù)值在表PT中最大。,分支限界法求解最大化問題的一般過程,分支限界法的一般過程 1根據(jù)限界函數(shù)確定目標(biāo)函數(shù)的界down, up； 2將待處理結(jié)點(diǎn)表PT初始化為空； 3對根結(jié)點(diǎn)的每個孩子結(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)直到某個葉子結(jié)點(diǎn)的目標(biāo)函數(shù)值在表PT中最大 4.1 i=

9、表PT中值最大的結(jié)點(diǎn)； 4.2 對結(jié)點(diǎn)i的每個孩子結(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對應(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)刪除；,分支限界法求解0/1背包問題,應(yīng)用分支限界法的關(guān)鍵問題 （1）如何確定合適的限界函數(shù) （2）如何組織待處理結(jié)點(diǎn)表 （3）如何確定最優(yōu)解中的各個分量,分支限界

10、法對問題的解空間樹中結(jié)點(diǎn)的處理是跳躍式的，回溯也不是單純地沿著雙親結(jié)點(diǎn)一層一層向上回溯，因此，當(dāng)搜索到某個葉子結(jié)點(diǎn)且該葉子結(jié)點(diǎn)的目標(biāo)函數(shù)值在表PT中最大時（假設(shè)求解最大化問題），求得了問題的最優(yōu)值，但是，卻無法求得該葉子結(jié)點(diǎn)對應(yīng)的最優(yōu)解中的各個分量。這個問題可以用如下方法解決： 對每個擴(kuò)展結(jié)點(diǎn)保存該結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑； 在搜索過程中構(gòu)建搜索經(jīng)過的樹結(jié)構(gòu)，在求得最優(yōu)解時，從葉子結(jié)點(diǎn)不斷回溯到根結(jié)點(diǎn)，以確定最優(yōu)解中的各個分量。,例如圖9.1所示0/1背包問題，為了對每個擴(kuò)展結(jié)點(diǎn)保存該結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑，將部分解(x1, , xi)和該部分解的目標(biāo)函數(shù)值都存儲在待處理結(jié)點(diǎn)表PT中，在搜索過程中表PT

11、的狀態(tài)如圖9.2所示。,對每個擴(kuò)展結(jié)點(diǎn)保存該結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑；,圖9.1所示0/1背包問題，為了在搜索過程中構(gòu)建搜索經(jīng)過的樹結(jié)構(gòu)，設(shè)一個表ST，在表PT中取出最小值結(jié)點(diǎn)進(jìn)行擴(kuò)充時，將最小值結(jié)點(diǎn)存儲到表ST中，表PT和表ST的數(shù)據(jù)結(jié)構(gòu)為(物品i-1的選擇結(jié)果，ub)，在搜索過程中表PT和表ST的狀態(tài)如圖9.3所示。,（物品i-1的選擇結(jié)果，ub）,分支限界法的時間性能,分支限界法和回溯法實(shí)際上都屬于蠻力窮舉法，當(dāng)然不能指望它有很好的最壞時間復(fù)雜性，遍歷具有指數(shù)階個結(jié)點(diǎn)的解空間樹，在最壞情況下，時間復(fù)雜性肯定為指數(shù)階。 與回溯法不同的是，分支限界法首先擴(kuò)展解空間樹中的上層結(jié)點(diǎn)，并采用限界函數(shù)，有

12、利于實(shí)行大范圍剪枝，同時，根據(jù)限界函數(shù)不斷調(diào)整搜索方向，選擇最有可能取得最優(yōu)解的子樹優(yōu)先進(jìn)行搜索。所以，如果選擇了結(jié)點(diǎn)的合理擴(kuò)展順序以及設(shè)計了一個好的限界函數(shù)，分支界限法可以快速得到問題的解。,分支限界法的較高效率是以付出一定代價為基礎(chǔ)的，其工作方式也造成了算法設(shè)計的復(fù)雜性。首先，一個更好的限界函數(shù)通常需要花費(fèi)更多的時間計算相應(yīng)的目標(biāo)函數(shù)值，而且對于具體的問題實(shí)例，通常需要進(jìn)行大量實(shí)驗(yàn)，才能確定一個好的限界函數(shù)；其次，由于分支限界法對解空間樹中結(jié)點(diǎn)的處理是跳躍式的，因此，在搜索到某個葉子結(jié)點(diǎn)得到最優(yōu)值時，為了從該葉子結(jié)點(diǎn)求出對應(yīng)的最優(yōu)解中的各個分量，需要對每個擴(kuò)展結(jié)點(diǎn)保存該結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑，

13、或者在搜索過程中構(gòu)建搜索經(jīng)過的樹結(jié)構(gòu)，這使得算法的設(shè)計較為復(fù)雜；再次，算法要維護(hù)一個待處理結(jié)點(diǎn)表PT，并且需要在表PT中快速查找取得極值的結(jié)點(diǎn)，等等。這都需要較大的存儲空間，在最壞情況下，分支限界法需要的空間復(fù)雜性是指數(shù)階。,2. 圖問題中的分支限界法,多段圖的最短路徑問題,多段圖的最短路徑問題,設(shè)圖G=(V, E)是一個帶權(quán)有向連通圖，如果把頂點(diǎn)集合V劃分成k個互不相交的子集Vi（2kn, 1ik），使得E中的任何一條邊(u, v)，必有uVi，vVi+m（1ik, 1i+mk），則稱圖G為多段圖，稱sV1為源點(diǎn)，tVk為終點(diǎn)。,多段圖的最短路徑問題是求從源點(diǎn)到終點(diǎn)的最小代價路徑。,對圖9.

14、7所示多段圖應(yīng)用貪心法求得近似解為02479，其路徑代價為2+6+5+7=20，這可以作為多段圖最短路徑問題的上界。把每一段最小的代價相加，可以得到一個非常簡單的下界，其路徑長度為2+4+5+3=14。于是，得到了評估函數(shù)的界14, 20。 由于多段圖將頂點(diǎn)劃分為k個互不相交的子集，所以，多段圖劃分為k段，一旦某條路徑的一些段被確定后，就可以并入這些信息并計算部分解的評估函數(shù)值的下界。一般情況下，對于一個正在生成的路徑，假設(shè)已經(jīng)確定了i段（1ik），其路徑為(r1, r2, , ri, ri+1)，此時，該部分解的評估函數(shù)值的計算方法即限界函數(shù)如下：,應(yīng)用分支限界法求解圖9.7所示多段圖的最短

15、路徑問題，其搜索空間如圖9.8所示，具體的搜索過程如下（加黑表示該路徑上已經(jīng)確定的邊）： （1）在根結(jié)點(diǎn)1，根據(jù)限界函數(shù)計算評估函數(shù)的值為18； （2）在結(jié)點(diǎn)2，第1段選擇邊，評估函數(shù)值為lb=4+8+5+3=20，超出評估函數(shù)的界，將結(jié)點(diǎn)2丟棄；在結(jié)點(diǎn)3，第1段選擇邊，評估函數(shù)值為lb=2+6+5+3=16，將結(jié)點(diǎn)3加入待處理結(jié)點(diǎn)表PT中；在結(jié)點(diǎn)4，第1段選擇邊，評估函數(shù)值為lb=3+4+5+3=15，將結(jié)點(diǎn)4加入表PT中； （3）在表PT中選取評估函數(shù)值極小的結(jié)點(diǎn)4優(yōu)先進(jìn)行搜索；,（4）在結(jié)點(diǎn)5，第2段選擇邊，評估函數(shù)值為lb=3+4+6+3=16，將結(jié)點(diǎn)5加入表PT中；在結(jié)點(diǎn)6，第2段選

16、擇邊，評估函數(shù)值為lb=3+7+5+3=18，將結(jié)點(diǎn)6加入表PT中； （5）在表PT中選取評估函數(shù)值極小的結(jié)點(diǎn)3優(yōu)先進(jìn)行搜索； （6）在結(jié)點(diǎn)7，第2段選擇邊，評估函數(shù)值為lb=2+6+5+3=16，將結(jié)點(diǎn)7加入表PT中；在結(jié)點(diǎn)8，第2段選擇邊，評估函數(shù)值為lb=2+7+6+3=18，將結(jié)點(diǎn)8加入表PT中；在結(jié)點(diǎn)9，第2段選擇邊，評估函數(shù)值為lb=2+8+5+3=18，將結(jié)點(diǎn)9加入表PT中；,（7）在表PT中選取評估函數(shù)值極小的結(jié)點(diǎn)5優(yōu)先進(jìn)行搜索； （8）在結(jié)點(diǎn)10，第3段選擇邊，可直接確定第4段的邊，評估函數(shù)值為lb=3+4+8+7=22，為一個可行解但超出評估函數(shù)的界，將其丟棄；在結(jié)點(diǎn)11，

17、第3段選擇邊，可直接確定第4段的邊，評估函數(shù)值為lb=3+4+6+3=16，為一個較好的可行解。由于結(jié)點(diǎn)11是葉子結(jié)點(diǎn)，并且其評估函數(shù)值是表PT中最小的，所以，結(jié)點(diǎn)11代表的解即是問題的最優(yōu)解，搜索過程結(jié)束。,分支限界法求解多段圖的最短路徑問題示例 (表示該結(jié)點(diǎn)被丟棄，結(jié)點(diǎn)上方的數(shù)組表示搜索順序),9.2.1 TSP問題,TSP問題是指旅行家要旅行n個城市，要求各個城市經(jīng)歷且僅經(jīng)歷一次然后回到出發(fā)城市，并要求所走的路程最短。,采用貪心法求得近似解為135421，其路徑長度為1+2+3+7+3=16，這可以作為TSP問題的上界。 把矩陣中每一行最小的元素相加，可以得到一個簡單的下界，其路徑長度為

18、1+3+1+3+2=10，但是還有一個信息量更大的下界：考慮一個TSP問題的完整解，在每條路徑上，每個城市都有兩條鄰接邊，一條是進(jìn)入這個城市的，另一條是離開這個城市的，那么，如果把矩陣中每一行最小的兩個元素相加再除以2，如果圖中所有的代價都是整數(shù)，再對這個結(jié)果向上取整，就得到了一個合理的下界。 lb=(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14 于是，得到了目標(biāo)函數(shù)的界14, 16。 需要強(qiáng)調(diào)的是，這個解并不是一個合法的選擇（可能沒有構(gòu)成哈密頓回路），它僅僅給出了一個參考下界。,部分解的目標(biāo)函數(shù)值的計算方法 例如圖9.4所示無向圖，如果部分解包含邊(1, 4)，則該部分

19、解的下界是lb=(1+5)+(3+6)+(1+2)+(3+5)+(2+3)/2=16。,分支限界法求解TSP問題示例,應(yīng)用分支限界法求解圖9.4所示無向圖的TSP問題，其搜索空間如圖9.5所示，具體的搜索過程如下（加黑表示該路徑上已經(jīng)確定的邊）： （1）在根結(jié)點(diǎn)1，根據(jù)限界函數(shù)計算目標(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+

20、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丟棄；,（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，

21、從城市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中；在

22、結(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中；,（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ù)值為(

23、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)，得到一個可行解，其路徑長度為16；,（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）在

24、表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，且有一個是葉子結(jié)點(diǎn)14，所以，結(jié)點(diǎn)14對應(yīng)的解135421即是TSP問題的最優(yōu)解，搜索過程結(jié)束。,組合問題中的分支限界法,任務(wù)分配問題,任務(wù)分配問題,任務(wù)分配問題要求把n項(xiàng)任務(wù)分配給n個人，每個人完成每項(xiàng)任務(wù)的成本不同，要求分配總成本最小的最優(yōu)分配方案。如圖9.10所示是一個任務(wù)分配的成本矩陣。,求最優(yōu)分配成本的上界和下界 考慮任意一個可行解，例如矩陣

25、中的對角線是一個合法的選擇，表示將任務(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。需要強(qiáng)調(diào)的是，這個解并不是一個合法的選擇（3和1來自于矩

26、陣的同一列），它僅僅給出了一個參考下界，這樣，最優(yōu)值一定是10, 14之間的某個值。,設(shè)當(dāng)前已對人員1i分配了任務(wù)，并且獲得了成本v，則限界函數(shù)可以定義為：,（2）在結(jié)點(diǎn)2，將任務(wù)1分配給人員a，獲得的成本為9，評估函數(shù)值為9 + (3+1+4)=17，超出評估函數(shù)的界10, 14，將結(jié)點(diǎn)2丟棄；在結(jié)點(diǎn)3，將任務(wù)2分配給人員a，獲得的成本為2，評估函數(shù)值為2 + (3+1+4)=10，將結(jié)點(diǎn)3加入待處理結(jié)點(diǎn)表PT中；在結(jié)點(diǎn)4，將任務(wù)3分配給人員a，獲得的成本為7，評估函數(shù)值為7 + (3+1+4)=15，超出評估函數(shù)的界10, 14，將結(jié)點(diǎn)4丟棄；在結(jié)點(diǎn)5，將任務(wù)4分配給人員a，獲得的成本為8，評估函數(shù)值為8 + (3+1+4)=16，超出評估函數(shù)的界10, 14，將結(jié)點(diǎn)5丟棄；,應(yīng)用分支限界法求解圖9.10所示任務(wù)分配問題，對解空間樹的搜索如圖9.11所示，具體的搜索過程如下： （1）在根結(jié)點(diǎn)1，沒有分配任務(wù)，根據(jù)限界函數(shù)估算評估函數(shù)值為2+3+1+4=10；,（3）在表PT中選取評估函數(shù)值極小的結(jié)點(diǎn)3優(yōu)先進(jìn)行搜索； （4）在結(jié)點(diǎn)6，將任務(wù)1分配給人員b，獲得的成本為2+6=8，評估函數(shù)值為8+(1+4)13，將結(jié)點(diǎn)6加入表PT中；在結(jié)點(diǎn)7，將任務(wù)3分配給人員b，獲得的成本為2+3=5，評估函數(shù)值為5+(