第9章分支限界法

第9章分支限界法學(xué)習(xí)要點(diǎn):

理解分支限界法的剪枝搜索策略掌握分支限界法的算法框架隊(duì)列式(FIFO)分支限界法優(yōu)先隊(duì)列式分支限界法通過(guò)應(yīng)用范例學(xué)習(xí)分支限界算法設(shè)計(jì)策略9.1.1分支限界法分支限界法類似于回溯法，也是一種在問(wèn)題的解空間樹(shù)T中搜索問(wèn)題解的算法。分支限界法常以廣度優(yōu)先或以最小耗費(fèi)(LC)優(yōu)先的方式搜索問(wèn)題的解空間樹(shù)。在遍歷過(guò)程中，對(duì)已經(jīng)擴(kuò)展出的每一個(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)題的解。適用于求解最優(yōu)化問(wèn)題。9.1

概述9.1.2分支限界法的設(shè)計(jì)思想首先，確定一個(gè)合理的限界函數(shù)，并根據(jù)限界函數(shù)確定問(wèn)題的目標(biāo)函數(shù)的界[down,up](具體問(wèn)題可以只有下界down，或上界up)；然后，按照廣度優(yōu)先策略遍歷問(wèn)題的解空間樹(shù)：當(dāng)搜索到達(dá)一個(gè)擴(kuò)展結(jié)點(diǎn)時(shí)，一次性擴(kuò)展它的所有孩子，估算每一個(gè)孩子結(jié)點(diǎn)的目標(biāo)函數(shù)的可能取值(又稱為耗費(fèi)函數(shù)值)；將那些滿足約束條件且耗費(fèi)函數(shù)值不超過(guò)目標(biāo)函數(shù)的界的孩子，插入活動(dòng)結(jié)點(diǎn)表PT中，再?gòu)腜T表中取耗費(fèi)函數(shù)值極大(小)的下一結(jié)點(diǎn)同樣擴(kuò)展；直到找到所需的解或PT表為空為止。怎樣確定“限界函數(shù)”？又如何求得目標(biāo)函數(shù)的界呢？對(duì)于PT中的葉子結(jié)點(diǎn)：其耗費(fèi)函數(shù)值是極值(極大或極小)，則該葉子結(jié)點(diǎn)對(duì)應(yīng)的解就是問(wèn)題的最優(yōu)解；否則，將問(wèn)題目標(biāo)函數(shù)的界([down,up])調(diào)整為該葉子結(jié)點(diǎn)的耗費(fèi)函數(shù)值，然后丟棄PT表中超出目標(biāo)函數(shù)界的結(jié)點(diǎn)，再次選取結(jié)點(diǎn)繼續(xù)擴(kuò)展。例9-1：0/1背包問(wèn)題。實(shí)例：假設(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分析：?jiǎn)栴}的解可表示為n元向量{x1,x2,...xn},xi{0,1}，則可用子集樹(shù)表示解空間,在樹(shù)中做廣度優(yōu)先搜索。約束條件:目標(biāo)函數(shù):下界Vdb=40(1,0,0,0)—貪心思想；上界Vub=0+(W-0)×(v1/w1)

=0+(10-0)×10=100；上限界函數(shù)：

(式9.1)目標(biāo)函數(shù)的界：[40,100]11111100000001124891011121314157653前i個(gè)物品獲得的價(jià)值剩余容量全部裝入物品i+1，最多能夠獲得的價(jià)值分支限界法求解0/1背包問(wèn)題：×w=0,v=0ub=100w=4,v=40ub=76w=0,v=0ub=60w=11w=4,v=40ub=70w=9,v=65ub=69w=4,v=40ub=64w=12w=9,v=65ub=6523456789×1PT={2,3}無(wú)效解PT={5,3}PT={6,7,3}無(wú)效解x1=1x1=0x2=1x2=0x3=1x3=0x4=1x4=0PT={9,7,3}V=65X=(1,0,1,0)目標(biāo)函數(shù)范圍：[40,100]wi=(4,7,5,3)vi=(40,42,25,12)vi/wi=(10,6,5,4)分支限界法的一般過(guò)程：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)刪除；常見(jiàn)的兩種分支限界法：從表PT中選擇下一擴(kuò)展結(jié)點(diǎn)的不同方式導(dǎo)致不同的分支限界法：隊(duì)列式(FIFO)分支限界法：從左往右依次插入結(jié)點(diǎn)到隊(duì)尾，按照隊(duì)列先進(jìn)先出（FIFO）原則選取下一個(gè)節(jié)點(diǎn)為擴(kuò)展節(jié)點(diǎn)。優(yōu)先隊(duì)列式分支限界法：按照優(yōu)先隊(duì)列中規(guī)定的優(yōu)先級(jí)選取優(yōu)先級(jí)最高的節(jié)點(diǎn)成為當(dāng)前擴(kuò)展節(jié)點(diǎn)。最大優(yōu)先隊(duì)列：使用最大堆，體現(xiàn)最大效益優(yōu)先。最小優(yōu)先隊(duì)列：使用最小堆，體現(xiàn)最小費(fèi)用優(yōu)先。例如，上例0/1背包問(wèn)題，采用最大優(yōu)先隊(duì)列式分支限界法。應(yīng)用分支限界法的其他關(guān)鍵問(wèn)題：如何確定最優(yōu)解中的各個(gè)分量？對(duì)每個(gè)擴(kuò)展結(jié)點(diǎn)保存根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑；例如，0/1背包問(wèn)題。將部分解(x1,…,xi)和該部分解的目標(biāo)函數(shù)的上界值都存儲(chǔ)在待處理結(jié)點(diǎn)表PT中，在搜索過(guò)程中表PT的狀態(tài)如下：(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(0)60(1,0,1)69(1,0,0)64(1)76(0)60(0)60(1,0)70結(jié)點(diǎn)2結(jié)點(diǎn)3結(jié)點(diǎn)3結(jié)點(diǎn)5結(jié)點(diǎn)3結(jié)點(diǎn)6結(jié)點(diǎn)7結(jié)點(diǎn)3結(jié)點(diǎn)7結(jié)點(diǎn)9在搜索的過(guò)程中構(gòu)建搜索經(jīng)過(guò)的樹(shù)結(jié)構(gòu)，在求得最優(yōu)解時(shí)，從葉子結(jié)點(diǎn)不斷回溯到根結(jié)點(diǎn)，以確定最優(yōu)解中的各個(gè)分量。例如，0/1背包問(wèn)題。設(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)，在搜索過(guò)程中表PT和表ST的狀態(tài)如下：(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(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)說(shuō)明：ST中記錄的就是得到最優(yōu)解的搜索路徑上的各個(gè)結(jié)點(diǎn)！分支限界法與回溯法的區(qū)別：求解目標(biāo)不同：回溯法——找出滿足約束條件的所有解分支限界法——找出滿足條件的一個(gè)解，或某種意義下的最優(yōu)解搜索方式不同：回溯法——深度優(yōu)先分支限界法——廣度優(yōu)先或最小耗費(fèi)優(yōu)先此外，在分支限界法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)。9.2.1TSP問(wèn)題例9-2：TSP問(wèn)題。問(wèn)題描述：略。各個(gè)城市間的距離用代價(jià)矩陣來(lái)表示,如果(i,j)E，則cij=∞。分析：設(shè)城市按自然數(shù)1,2,...,n編號(hào)解向量：(x1,x2,...,xn)約束條件：顯式約束：xi=1,2,...,n(i=1,2,...,n)隱式約束：(xi≠xj)∧(cij≠∞)9.2

廣度優(yōu)先分支限界法應(yīng)用舉例目標(biāo)函數(shù)：(k∈V’)下界：ddb=((1+3)+(3+6)+(1+2)+(3+4)+(2+3))/2=14上界：dub=16(1→3→5→4→2→1)下限界函數(shù)：設(shè)已確定的頂點(diǎn)集合U=(r1,r2,...,rk)(式9.2)目標(biāo)函數(shù)的界：[14,

16]271563134253984C=∞31583∞67916∞42574∞38923∞(a)一個(gè)無(wú)向圖(b)無(wú)向圖的代價(jià)矩陣從集合U中出來(lái)的邊一條進(jìn)邊，一條出邊優(yōu)先隊(duì)列式分支限界法求解TSP問(wèn)題:目標(biāo)函數(shù)范圍：[14,16]41→2db=142356781×startdb=141→3db=141→4db=161→5db=192→3db=162→4db=162→5db=193→2db=163→4db=153→5db=14×910115→2db=195→4db=141213×4→2db=16144→2db=184→5db=151516×5→2db=2017×db=19PT={2,3,4}db=19PT={6,7,9,10,11,4}db=18db=19PT={6,7,9,16,14,4}db=20PT={6,7,9,14,4}PT={6,7,9,10,13,4}PT={6,7,3,4}PT={6,7,9,10,14,4}d=161→3→5→4→2→1C=∞31583∞67916∞42574∞38923∞對(duì)每個(gè)擴(kuò)展結(jié)點(diǎn)保存根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑：(g)擴(kuò)展結(jié)點(diǎn)16后的狀態(tài)，最優(yōu)解為1→3→5→4→2→1(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)TSP問(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;x[1]=1;//從頂點(diǎn)1出發(fā)求解TSP問(wèn)題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ù)式7.2計(jì)算目標(biāo)函數(shù)值db；

5.3.1.2if(db<=up)將路徑上的頂點(diǎn)和db值存儲(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)db，令up=db，將表PT中目標(biāo)函數(shù)值db超出up的結(jié)點(diǎn)刪除；

5.6k=表PT中db最小的路徑上頂點(diǎn)個(gè)數(shù)；課后作業(yè)應(yīng)用分支限界法求解下圖的TSP問(wèn)題。9.2.2單源最短路徑問(wèn)題問(wèn)題描述：略。例9-3：分析：采用優(yōu)先隊(duì)列式分支限界法，并用一極小堆來(lái)存儲(chǔ)活結(jié)點(diǎn)表。其優(yōu)先級(jí)是結(jié)點(diǎn)所對(duì)應(yīng)的當(dāng)前路長(zhǎng)。ABsCDEFGHt492386884756866537解向量：X=(s,

x2,...,t)，s和t分別為起點(diǎn)和終點(diǎn)約束條件：顯式：xi=A,B,...(i=2,...,n)隱式：cij≠∞目標(biāo)函數(shù)：cost(i)=min{cij+cost(j)}(i≤j≤n且頂點(diǎn)j是i的鄰接點(diǎn))下界：把每一段最小的代價(jià)相加，2+4+5+3=14上界：2+7+6+3=18(s→B→E→H→t)下限界函數(shù)：假設(shè)已經(jīng)確定了i段(1≤i≤k)，其路徑為(r1,r2,…,ri,ri+1)??+=+>?<=++=+kijpiEvrijjjjvrcrrcdbpi21,11]}][[{min]][[1段的最短邊第＋與頂點(diǎn)ri+1相連的邊中,代價(jià)最小的邊(剩余頂點(diǎn)能夠達(dá)到的最小代價(jià))優(yōu)先隊(duì)列式分支限界法求解：64s→Adb=20231startdb=14s→Bdb=16s→Cdb=15×7B→Ddb=188B→Edb=189B→Fdb=185C→Edb=16C→Fdb=181110E→Gdb=22E→Hdb=16×目標(biāo)函數(shù)范圍：[14,18]ABsCDEFGHt492386884756866537PT={3,4}PT={3,5,6}PT={7,8,9,5,6}PT={7,8,9,11,6}c=16s→C→E→H→t(4+8+(5+3))搜索算法描述：while(true){for(intj=1;j<=n;j++)if((c[E.i][j]<inf)&&(E.length+c[E.i][j]<dist[j])){

//頂點(diǎn)i到頂點(diǎn)j可達(dá)，且滿足控制約束

dist[j]=E.length+c[E.i][j];prev[j]=E.i;

//加入活結(jié)點(diǎn)優(yōu)先隊(duì)列

MinHeapNode<Type>N;N.i=j;N.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)9.2.3裝載問(wèn)題問(wèn)題描述：略。分析：解空間：X=(x1,x2,…,xn)，xi∈Si={0,1}，i=1,2,…,n約束函數(shù)：目標(biāo)函數(shù)：下界：…上界：…上限界函數(shù)：左孩子：Ew+w[i+1]<=c1右孩子：Ew+>bestw改進(jìn)搜索算法設(shè)計(jì)：隊(duì)列式分支限界：while(true){

//檢查左兒子結(jié)點(diǎn)

Typewt=Ew+w[i];//左兒子結(jié)點(diǎn)的重量if(wt<=c){//可行結(jié)點(diǎn)if(wt>bestw)bestw=wt;//加入活結(jié)點(diǎn)隊(duì)列if(i<n)Q.Add(wt);

}//檢查右兒子結(jié)點(diǎn)

if(Ew+r>bestw&&i<n)Q.Add(Ew);//可能含最優(yōu)解

Q.Delete(Ew);//取下一擴(kuò)展結(jié)點(diǎn)if(Ew==-1){//同層結(jié)點(diǎn)尾部

if(Q.IsEmpty())returnbestw;Q.Add(-1);//同層結(jié)點(diǎn)尾部標(biāo)志

Q.Delete(Ew);//取下一擴(kuò)展結(jié)點(diǎn)

i++;r-=w[i];}//進(jìn)入下一層}}提前更新bestw右兒子剪枝優(yōu)先隊(duì)列式分支限界：

采用最大優(yōu)先隊(duì)列存儲(chǔ)活結(jié)點(diǎn)表。活結(jié)點(diǎn)x在優(yōu)先隊(duì)列中的優(yōu)先級(jí)定義為：從根結(jié)點(diǎn)到結(jié)點(diǎn)x的路徑所相應(yīng)的載重量Ew+

剩余集裝箱的重量r。子集樹(shù)中葉結(jié)點(diǎn)所相應(yīng)的載重量與其優(yōu)先級(jí)相同，一旦有一個(gè)葉結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，則可以斷言該葉結(jié)點(diǎn)所相應(yīng)的解即為最優(yōu)解。此時(shí)可終止算法。實(shí)現(xiàn)方法：(PT表結(jié)點(diǎn)的結(jié)構(gòu))在活結(jié)點(diǎn)中保存從解空間樹(shù)的根結(jié)點(diǎn)到該活結(jié)點(diǎn)的路徑；搜索進(jìn)程中保存當(dāng)前已構(gòu)造出的部分解空間樹(shù)；算法描述（采用第二種方式實(shí)現(xiàn)PT表）：template<classType>classHeapNode;classbbnode{

friendvoidAddLiveNode(MaxHeap<HeapNode<int>>&,

bbbnode*,int,bool,int);

friendintMaxLoading(int*,int,int,int*);

friendclassAdjacencyGraph;

private:

bbnode*parent;//指向父結(jié)點(diǎn)的指針

boolLChild;//左孩子結(jié)點(diǎn)標(biāo)志};template<classType>classHeapNode{

friendvoidAddLiveNode(MaxHeap<HeapNode<Type>>&,

bbnode*,Type,bool,int);friendTypeMaxLoading(Type*,Type,int,int*);public:operatorType()const{returnuweight;}private:bbnode*ptr;//指向活結(jié)點(diǎn)在子集樹(shù)中相應(yīng)結(jié)點(diǎn)的指針Typeuweight;//活結(jié)點(diǎn)優(yōu)先級(jí)(上界)intlevel;//活結(jié)點(diǎn)在子集樹(shù)中所處的層序號(hào)};template<classType>voidAddLiveNode(MaxHeap<HeapNode<Type>>&H,bbnode*E,Typewt,boolch,intlev){//將活結(jié)點(diǎn)加入到表示活結(jié)點(diǎn)優(yōu)先隊(duì)列的最大堆H中bbnode*b=newbbnode;b->parent=E;b->Lchild=ch;HeapNode<Type>N;N.uweight=wt;N.level=lev;N.ptr=b;H.Inset(N);}template<classType>TypeMaxLoading(Typew[],Typec,intn,intbestx[]){//優(yōu)先隊(duì)列式分支限界法,返回最優(yōu)裝載重量，bestx返回最優(yōu)解//定義最大堆的容量為1000MaxHeap<HeapNode<Type>>H(1000);//定義剩余重量數(shù)組rType*r=newType[n+1];r[n]=0;for(intj=n-1;j>0;j--)r[j]=r[j+1]+w[j+1];//初始化inti=1;//當(dāng)前擴(kuò)展結(jié)點(diǎn)所處的層bbnode*E=0;//當(dāng)前擴(kuò)展結(jié)點(diǎn)TypeEw=0;//擴(kuò)展結(jié)點(diǎn)所相應(yīng)的載重量//搜索子集空間樹(shù)while(i!=n+1){//非葉子結(jié)點(diǎn)//檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的孩子結(jié)點(diǎn)if(Ew+w[i]<=c){//左孩子結(jié)點(diǎn)為可行結(jié)點(diǎn)AddLiveNode(H,E,Ew+w[i]+r[i],true,i+1);}//右孩子結(jié)點(diǎn)AddLiveNode(H,E,Ew+r[i],false,i+1);//取下一擴(kuò)展結(jié)點(diǎn)HeapNode<Type>N;H.DeleteMax(N);//非空i=N.level;E=N.prt;Ew=N.uweight–r[i-1];}//構(gòu)造當(dāng)前最優(yōu)解for(intj=n;j>0;j--){bestx[j]=E->Lchild;E=E->parent;}returnEw;}9.2.4批處理作業(yè)調(diào)度問(wèn)題例9-4：批處理作業(yè)調(diào)度問(wèn)題。問(wèn)題描述：給定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)度問(wèn)題要求確定這n個(gè)作業(yè)的最優(yōu)處理順序，使得從第1個(gè)作業(yè)在機(jī)器1上處理開(kāi)始，到最后一個(gè)作業(yè)在機(jī)器3上處理結(jié)束所需的時(shí)間最少。實(shí)例：設(shè)J={J1,J2,J3,J4}是4個(gè)待處理的作業(yè)，需要的處理時(shí)間如下所示。若處理順序?yàn)?J2,J3,J1,J4)，則從作業(yè)2在機(jī)器1處理開(kāi)始到作業(yè)4在機(jī)器3處理完成的調(diào)度方案如下：T＝57910529957810J1J2J3J4機(jī)器1機(jī)器2機(jī)器3J2:10J3:9J1:5J4:7機(jī)器1機(jī)器2機(jī)器3(表示空閑，最后完成處理時(shí)間為54)空閑:10

J2:5空閑:4

J3:9J1:7J4:8空閑:15

J2:2空閑:11

J3:5空閑:2

J1:9J4:10等待時(shí)間+處理時(shí)間分析：解向量：X=(x1,x2,...,xn)——排列樹(shù)約束條件：顯式：xi=J1,J2,...,Jn目標(biāo)函數(shù):sum3=下限界函數(shù)：機(jī)器3有空閑機(jī)器3有積壓，極小化其中，sum2[n]=max{sum1[n],sum2[n-1]}+tn2

；

sum1[n]=sum1[n-1]+tn1設(shè)M是已安排好的作業(yè)集合，M{1,2,...,n},|M|=k?，F(xiàn)在要處理作業(yè)k+1，有：sum1[k+1]=sum1[k]+tk+1,1sum2[k+1]=max{sum1[k+1],sum2[k]}+tk+1,2max{sum2[n],sum3[n-1]}+tn3目標(biāo)函數(shù)的下界:sum3db=

說(shuō)明：最理想的情況下，機(jī)器1和機(jī)器2均無(wú)空閑，最后處理的作業(yè)恰好是在機(jī)器3上處理時(shí)間最短的作業(yè)。如上實(shí)例，sum3db==36遍歷并估算解空間樹(shù)上各結(jié)點(diǎn)的目標(biāo)函數(shù)的下界值：根結(jié)點(diǎn)：sum1=0,sum2=0,M={}

k=0T＝57910529957810J1J2J3J4機(jī)器1機(jī)器2機(jī)器3優(yōu)先隊(duì)列式分支限界法求解過(guò)程：J4,sum1=0+7db=38sum2=152M={}k=1J1,sum1=0+5db=36sum2=5+7=121M={}k=0startsum1=0,sum2=03M={}k=1J2,sum1=0+10db=44sum2=124M={}k=1J3,sum1=0+9db=40sum2=185M={}k=16M={1}k=2J1J2,sum1=15db=42sum2=207M={1}k=2J1J3,sum1=14db=38sum2=228M={1}k=2J1J4,sum1=12db=36sum2=209M={1,4}k=3J1J4J2,sum1=22db=41sum2=2710M={1,4}k=3J1J4J3,sum1=21db=37sum2=3011M={1,4,3}k=4J1J4J3J2,sum1=31db=36sum2[4]=36PT={2,3,4,5}PT={6,7,8,3,4,5}PT={6,7,9,10,3,4,5}PT={6,7,9,11,3,4,5}X=(J1,J4,J3,J2)sum3=sum2[4]+t23=38sum1[k]=sum1[k-1]+tk,1sum2[k]=max{sum1[k],sum2[k-1]}+tk,2T＝57910529957810J1J2J3J4機(jī)器1機(jī)器2機(jī)器3下界sum3db=36從上例可知：優(yōu)先隊(duì)列式分支限界法中，擴(kuò)展結(jié)點(diǎn)表PT取得極值的葉子結(jié)點(diǎn)就對(duì)應(yīng)的是問(wèn)題的最優(yōu)解；擴(kuò)展結(jié)點(diǎn)的過(guò)程，一開(kāi)始實(shí)際類似“深度優(yōu)先”。思考：將例9-2和例9-4改成FIFO式分支限界法，搜索過(guò)程有何不同？在算法的實(shí)現(xiàn)上，F(xiàn)IFO式分支限界法和優(yōu)先隊(duì)列式分支限界法的PT表數(shù)據(jù)結(jié)構(gòu)一樣嗎？課后作業(yè)采用分支限界法求解下列作業(yè)調(diào)度問(wèn)題，4個(gè)作業(yè)J1,J2,J3,J4在機(jī)器M1,M2上處理的時(shí)間矩陣如圖所示。求最佳的處理順序，使得4個(gè)作業(yè)從開(kāi)始到結(jié)束處理的時(shí)間最短。(要求：畫(huà)出解空間的展開(kāi))M1M2J1J2J3J49.3最小消耗(LC)搜索法9.3.1LC檢索在FIFO分枝限界法中，對(duì)下一個(gè)E-結(jié)點(diǎn)的選擇規(guī)則相當(dāng)死板，在某種意義上是盲目的。對(duì)活結(jié)點(diǎn)使用一個(gè)“有智力”的排序函數(shù)c(.)來(lái)選取下一個(gè)E-結(jié)點(diǎn)往往可以加快到達(dá)一答案結(jié)點(diǎn)的速度。對(duì)任意結(jié)點(diǎn)x，可用兩種標(biāo)準(zhǔn)來(lái)量度：在生成一個(gè)答案結(jié)點(diǎn)之前，子樹(shù)x需要生成的結(jié)點(diǎn)個(gè)數(shù)；在子樹(shù)x中離x最近的那個(gè)答案結(jié)點(diǎn)到x的路徑長(zhǎng)度。使用第一種度量：圖中樹(shù)的根結(jié)點(diǎn)付出的代價(jià)是4。結(jié)點(diǎn)(18和34)，(29和35)以及(30和38)的代價(jià)分別是3,2和1。所有在2,3和4級(jí)上剩余結(jié)點(diǎn)的代價(jià)應(yīng)分別大于3,2和1。以這些代價(jià)作為選擇下一個(gè)E-結(jié)點(diǎn)的依據(jù)，則E-結(jié)點(diǎn)依次為1,18,29和30。另外，不得已生成的結(jié)點(diǎn)為2,34,50,19,24,32。使用第二種度量，則E-結(jié)點(diǎn)只是由根到最近的那個(gè)答案結(jié)點(diǎn)路徑上的那些結(jié)點(diǎn)。圖9.14-皇后問(wèn)題總是生成最小數(shù)目的結(jié)點(diǎn)9.3.2LC方法要點(diǎn)對(duì)狀態(tài)空間樹(shù)上的一個(gè)答案結(jié)點(diǎn)x,定義實(shí)際代價(jià)函數(shù)cost(x)。cost(x)的內(nèi)涵：從狀態(tài)空間樹(shù)根結(jié)點(diǎn)出發(fā)，到達(dá)一個(gè)答案結(jié)點(diǎn)x，實(shí)際需要付出的“代價(jià)”。cost(x)的定義：原則上應(yīng)根據(jù)具體問(wèn)題加以定義。對(duì)狀態(tài)空間樹(shù)上任一結(jié)點(diǎn)x，定義代價(jià)函數(shù)c(x)。c(x)的內(nèi)涵：從狀態(tài)空間樹(shù)根結(jié)點(diǎn)出發(fā)，經(jīng)過(guò)x結(jié)點(diǎn)，在以結(jié)點(diǎn)x為根的子樹(shù)上，搜索到一個(gè)答案結(jié)點(diǎn)，所需要付出的代價(jià)。定義c(x)的一般原則：若x是答案結(jié)點(diǎn)，則：c(x)=cost(x)；若x不是答案結(jié)點(diǎn)，但以x為根的子樹(shù)上至少有一個(gè)答案結(jié)點(diǎn)，則：c(x)=min{c(answer)|answer:x上所有答案結(jié)點(diǎn)}若x不是答案結(jié)點(diǎn)，且以x為根的子樹(shù)上也沒(méi)有答案結(jié)點(diǎn)，則：c(x)=+∞對(duì)狀態(tài)空間樹(shù)上結(jié)點(diǎn)x,定義估算函數(shù)，且使?jié)M足：≤c(x)。注：與c(x)相比，應(yīng)是當(dāng)前“可計(jì)算”的。設(shè)計(jì)一個(gè)活結(jié)點(diǎn)表L，用于存放搜索過(guò)程的“活結(jié)點(diǎn)”。該表的數(shù)據(jù)結(jié)構(gòu)可選擇有序表或堆。即要求：活結(jié)點(diǎn)表上的所有結(jié)點(diǎn)，按照它們估算函數(shù)取值，構(gòu)成一個(gè)有序表或堆。=h(x)+g(x)LC法搜索過(guò)程：初始：把狀態(tài)空間樹(shù)的根結(jié)點(diǎn)，做為活結(jié)點(diǎn)表L的第一個(gè)結(jié)點(diǎn)；重復(fù)以下兩步，直到找到一個(gè)解，或L為空：從L上選出具有最小的結(jié)點(diǎn)，作為當(dāng)前E-結(jié)點(diǎn)。依次搜索當(dāng)前E-結(jié)點(diǎn)的所有子結(jié)點(diǎn)。若子結(jié)點(diǎn)是答案結(jié)點(diǎn)，則結(jié)束；否則，把子結(jié)點(diǎn)加入有序表L。9.3.3LC方法應(yīng)用舉例15迷問(wèn)題。問(wèn)題描述：把編號(hào)為1~15的棋子，隨意放在4×4格的棋盤上(空出一個(gè)格)。要求：經(jīng)過(guò)有限步的移動(dòng)，把棋盤上棋子的“初態(tài)”，變成棋子號(hào)與棋盤號(hào)一致的目標(biāo)狀態(tài)。(注：“移動(dòng)”僅限于空格周圍棋子)實(shí)例：初態(tài)目標(biāo)狀態(tài)124563791012813141115123456789101112131415分析：實(shí)際代價(jià)函數(shù)cost(x):

若x是目標(biāo)狀態(tài)，則：cost(x)等于從棋盤初態(tài)，經(jīng)逐步移動(dòng)棋子而到達(dá)目標(biāo)狀態(tài)x，實(shí)際需要移動(dòng)棋子總步數(shù)。代價(jià)函數(shù)c(x):若x是目標(biāo)狀態(tài)，則：c(x)=cost(x)若x不是目標(biāo)狀態(tài)，但x所在子樹(shù)上存在目標(biāo)狀態(tài)結(jié)點(diǎn)，則：c(x)=min{c(x′)|x′：x子樹(shù)上所有目標(biāo)狀態(tài)結(jié)點(diǎn)}若x不是目標(biāo)狀態(tài)，且x所在子樹(shù)上也不存在任何目標(biāo)狀態(tài)結(jié)點(diǎn)，則c(x)=+∞定義估算函數(shù)：=h(x)+g(x)其中，h(x):從狀態(tài)空間樹(shù)的根結(jié)點(diǎn)到x結(jié)點(diǎn)路徑長(zhǎng)度；g(x)：x狀態(tài)下，沒(méi)有達(dá)到“目標(biāo)狀態(tài)”的棋子數(shù)量。124563791012813141115124563791012813141115123456791012813141115124563791012813141115g1=6h1=01g2=7g3=5g4=7234左下右1123456791012813141115g3=5311234567910128131411151234567910128