第15講 分支定界法

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

分支限界法常以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索問(wèn)題的解空間樹(shù)。此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過(guò)程。這個(gè)過(guò)程一直持續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時(shí)為止。在分支限界法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)?；罱Y(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àn)的兩種分支限界法（1）隊(duì)列式(FIFO)分支限界法按照隊(duì)列先進(jìn)先出（FIFO）原則選取下一個(gè)節(jié)點(diǎn)為擴(kuò)展節(jié)點(diǎn)。

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

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

單源最短路徑問(wèn)題3.算法思想

解單源最短路徑問(wèn)題的優(yōu)先隊(duì)列式分支限界法用一極小堆來(lái)存儲(chǔ)活結(jié)點(diǎn)表。其優(yōu)先級(jí)是結(jié)點(diǎn)所對(duì)應(yīng)的當(dāng)前路長(zhǎng)。

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

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

缺乏上界函數(shù)減枝優(yōu)先權(quán)隊(duì)列VS.先進(jìn)先出隊(duì)列0/1背包問(wèn)題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應(yīng)用貪心法求得近似解為(1,0,0,0)，獲得的價(jià)值為40，這可以作為0/1背包問(wèn)題的下界。如何求得0/1背包問(wèn)題的一個(gè)合理的上界呢？考慮最好情況，背包中裝入的全部是第1個(gè)物品且可以將背包裝滿，則可以得到一個(gè)非常簡(jiǎn)單的上界的計(jì)算方法：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ú)效解w=4,v=40ub=70w=9,v=65ub=69w=4,v=40ub=64w=12無(wú)效解w=9,v=65ub=6523456789×1分支限界法求解0/1背包問(wèn)題分支限界法求解0/1背包問(wèn)題，具體的搜索過(guò)程如下：（1）在根結(jié)點(diǎn)1，沒(méi)有將任何物品裝入背包，因此，背包的重量和獲得的價(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，沒(méi)有將物品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)行搜索；（4）在結(jié)點(diǎn)4，將物品2裝入背包，因此，背包的重量為11，不滿足約束條件，將結(jié)點(diǎn)4丟棄；在結(jié)點(diǎn)5，沒(méi)有將物品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，沒(méi)有將物品3裝入背包，因此，背包的重量和獲得的價(jià)值與結(jié)點(diǎn)5相同，目標(biāo)函數(shù)值為40+(10-4)×4＝64，將結(jié)點(diǎn)6加入表PT中；（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，沒(méi)有將物品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)的解即是問(wèn)題的最優(yōu)解，搜索結(jié)束。分支限界法的時(shí)間性能

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

首先，一個(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ù)一個(gè)待處理結(jié)點(diǎn)表PT，并且需要在表PT中快速查找取得極值的結(jié)點(diǎn)，等等。這都需要較大的存儲(chǔ)空間，在最壞情況下，分支限界法需要的空間復(fù)雜性是指數(shù)階。任務(wù)分配問(wèn)題任務(wù)分配問(wèn)題要求把n項(xiàng)任務(wù)分配給n個(gè)人，每個(gè)人完成每項(xiàng)任務(wù)的成本不同，要求分配總成本最小的最優(yōu)分配方案。如下圖所示是一個(gè)任務(wù)分配的成本矩陣。

C＝9278643758187694任務(wù)1任務(wù)2任務(wù)3任務(wù)4人員a人員b人員c人員d任務(wù)分配問(wèn)題的成本矩陣求最優(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。因此，將每一行的最小元素加起來(lái)就得到解的下界，其成本是2+3+1+4=10。需要強(qiáng)調(diào)的是，這個(gè)解并不是一個(gè)合法的選擇（3和1來(lái)自于矩陣的同一列），它僅僅給出了一個(gè)參考下界，這樣，最優(yōu)值一定是[10,14]之間的某個(gè)值。設(shè)當(dāng)前已對(duì)人員1～i分配了任務(wù)，并且獲得了成本v，則限界函數(shù)可以定義為：（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)用分支限界法求解任務(wù)分配問(wèn)題，具體的搜索過(guò)程如下：（1）在根結(jié)點(diǎn)1，沒(méi)有分配任務(wù)，根據(jù)限界函數(shù)估算目標(biāo)函數(shù)值為2+3+1+4=10；

（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丟棄；（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)的解即是問(wèn)題的最優(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ù)分配問(wèn)題示例(×表示該結(jié)點(diǎn)被丟棄，結(jié)點(diǎn)上方的數(shù)組表示搜索順序)23567891213111××××為了在搜索過(guò)程中構(gòu)建搜索經(jīng)過(guò)的樹(shù)結(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任務(wù)分配問(wèn)題最優(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

回溯過(guò)程是：(3,<4,d>13)→(1,<3,c>13)→(2,<1,b>13)→(0,<2,a>10)。算法任務(wù)分配問(wèn)題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++;偽代碼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