第9章分支限界法

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

理解分支限界法的剪枝搜索策略掌握分支限界法的算法框架隊列式(FIFO)分支限界法優(yōu)先隊列式分支限界法通過應(yīng)用范例學(xué)習(xí)分支限界算法設(shè)計策略9.1.1分支限界法分支限界法類似于回溯法，也是一種在問題的解空間樹T中搜索問題解的算法。分支限界法常以廣度優(yōu)先或以最小耗費(LC)優(yōu)先的方式搜索問題的解空間樹。在遍歷過程中，對已經(jīng)擴展出的每一個結(jié)點根據(jù)限界函數(shù)估算目標(biāo)函數(shù)的可能取值，從中選取使目標(biāo)函數(shù)取得極值的結(jié)點優(yōu)先進行廣度優(yōu)先搜索，從而不斷調(diào)整搜索方向，盡快找到問題的解。適用于求解最優(yōu)化問題。9.1

概述9.1.2分支限界法的設(shè)計思想首先，確定一個合理的限界函數(shù)，并根據(jù)限界函數(shù)確定問題的目標(biāo)函數(shù)的界[down,up](具體問題可以只有下界down，或上界up)；然后，按照廣度優(yōu)先策略遍歷問題的解空間樹：當(dāng)搜索到達一個擴展結(jié)點時，一次性擴展它的所有孩子，估算每一個孩子結(jié)點的目標(biāo)函數(shù)的可能取值(又稱為耗費函數(shù)值)；將那些滿足約束條件且耗費函數(shù)值不超過目標(biāo)函數(shù)的界的孩子，插入活動結(jié)點表PT中，再從PT表中取耗費函數(shù)值極大(小)的下一結(jié)點同樣擴展；直到找到所需的解或PT表為空為止。怎樣確定“限界函數(shù)”？又如何求得目標(biāo)函數(shù)的界呢？對于PT中的葉子結(jié)點：其耗費函數(shù)值是極值(極大或極小)，則該葉子結(jié)點對應(yīng)的解就是問題的最優(yōu)解；否則，將問題目標(biāo)函數(shù)的界([down,up])調(diào)整為該葉子結(jié)點的耗費函數(shù)值，然后丟棄PT表中超出目標(biāo)函數(shù)界的結(jié)點，再次選取結(jié)點繼續(xù)擴展。例9-1：0/1背包問題。實例：假設(shè)有4個物品，其重量分別為(4,7,5,3)，價值分別為(40,42,25,12)，背包容量W=10。將給定物品按單位重量價值從大到小排序，結(jié)果如下：物品重量(w)價值(v)價值/重量(v/w)144010274263525543124分析：問題的解可表示為n元向量{x1,x2,...xn},xi{0,1}，則可用子集樹表示解空間,在樹中做廣度優(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個物品獲得的價值剩余容量全部裝入物品i+1，最多能夠獲得的價值分支限界法求解0/1背包問題：×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}無效解PT={5,3}PT={6,7,3}無效解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)分支限界法的一般過程：1．根據(jù)限界函數(shù)確定目標(biāo)函數(shù)的界[down,up]；2．將待處理結(jié)點表PT初始化為空；3．對根結(jié)點的每個孩子結(jié)點x執(zhí)行下列操作

3.1估算結(jié)點x的目標(biāo)函數(shù)值value;3.2若(value>=down)，則將結(jié)點x加入表PT中；4．循環(huán)直到某個葉子結(jié)點的目標(biāo)函數(shù)值在表PT中最大

4.1i=表PT中值最大的結(jié)點；

4.2對結(jié)點i的每個孩子結(jié)點x執(zhí)行下列操作

4.2.1估算結(jié)點x的目標(biāo)函數(shù)值value;4.2.2若(value>=down)，則將結(jié)點x加入表PT中；

4.2.3若(結(jié)點x是葉子結(jié)點且結(jié)點x的value值在表PT中最大)，則將結(jié)點x對應(yīng)的解輸出，算法結(jié)束；

4.2.4若(結(jié)點x是葉子結(jié)點但結(jié)點x的value值在表PT中不是最大)，則令down=value，并且將表PT中所有小于value的結(jié)點刪除；常見的兩種分支限界法：從表PT中選擇下一擴展結(jié)點的不同方式導(dǎo)致不同的分支限界法：隊列式(FIFO)分支限界法：從左往右依次插入結(jié)點到隊尾，按照隊列先進先出（FIFO）原則選取下一個節(jié)點為擴展節(jié)點。優(yōu)先隊列式分支限界法：按照優(yōu)先隊列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的節(jié)點成為當(dāng)前擴展節(jié)點。最大優(yōu)先隊列：使用最大堆，體現(xiàn)最大效益優(yōu)先。最小優(yōu)先隊列：使用最小堆，體現(xiàn)最小費用優(yōu)先。例如，上例0/1背包問題，采用最大優(yōu)先隊列式分支限界法。應(yīng)用分支限界法的其他關(guān)鍵問題：如何確定最優(yōu)解中的各個分量？對每個擴展結(jié)點保存根結(jié)點到該結(jié)點的路徑；例如，0/1背包問題。將部分解(x1,…,xi)和該部分解的目標(biāo)函數(shù)的上界值都存儲在待處理結(jié)點表PT中，在搜索過程中表PT的狀態(tài)如下：(0)60(1,0,0)64(1,0,1,0)65(a)擴展根結(jié)點后表PT狀態(tài)(b)擴展結(jié)點2后表PT狀態(tài)(c)擴展結(jié)點5后表PT狀態(tài)(d)擴展結(jié)點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é)點2結(jié)點3結(jié)點3結(jié)點5結(jié)點3結(jié)點6結(jié)點7結(jié)點3結(jié)點7結(jié)點9在搜索的過程中構(gòu)建搜索經(jīng)過的樹結(jié)構(gòu)，在求得最優(yōu)解時，從葉子結(jié)點不斷回溯到根結(jié)點，以確定最優(yōu)解中的各個分量。例如，0/1背包問題。設(shè)一個表ST，在表PT中取出最大值結(jié)點進行擴充時，將最大值結(jié)點存儲到表ST中，表PT和表ST的數(shù)據(jù)結(jié)構(gòu)為(物品i-1的選擇結(jié)果，<物品i,物品i的選擇結(jié)果>ub)，在搜索過程中表PT和表ST的狀態(tài)如下：(a)擴展根結(jié)點后(b)擴展結(jié)點2后(c)擴展結(jié)點5后(d)擴展結(jié)點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)說明：ST中記錄的就是得到最優(yōu)解的搜索路徑上的各個結(jié)點！分支限界法與回溯法的區(qū)別：求解目標(biāo)不同：回溯法——找出滿足約束條件的所有解分支限界法——找出滿足條件的一個解，或某種意義下的最優(yōu)解搜索方式不同：回溯法——深度優(yōu)先分支限界法——廣度優(yōu)先或最小耗費優(yōu)先此外，在分支限界法中，每一個活結(jié)點只有一次機會成為擴展結(jié)點。9.2.1TSP問題例9-2：TSP問題。問題描述：略。各個城市間的距離用代價矩陣來表示,如果(i,j)E，則cij=∞。分析：設(shè)城市按自然數(shù)1,2,...,n編號解向量：(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è)已確定的頂點集合U=(r1,r2,...,rk)(式9.2)目標(biāo)函數(shù)的界：[14,

16]271563134253984C=∞31583∞67916∞42574∞38923∞(a)一個無向圖(b)無向圖的代價矩陣從集合U中出來的邊一條進邊，一條出邊優(yōu)先隊列式分支限界法求解TSP問題:目標(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∞對每個擴展結(jié)點保存根結(jié)點到該結(jié)點的路徑：(g)擴展結(jié)點16后的狀態(tài)，最優(yōu)解為1→3→5→4→2→1(1,2)14(1,3)14(1,4)16(a)擴展根結(jié)點后的狀態(tài)(b)擴展結(jié)點2后的狀態(tài)(c)擴展結(jié)點3后的狀態(tài)(d)擴展結(jié)點11后的狀態(tài)(e)擴展結(jié)點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)擴展結(jié)點10后的狀態(tài)TSP問題算法的偽代碼描述：1．根據(jù)限界函數(shù)計算目標(biāo)函數(shù)的下界down；采用貪心法得到上界up；2．將待處理結(jié)點表PT初始化為空；3．for(i=1;i<=n;i++)x[i]=0;4．k=1;x[1]=1;//從頂點1出發(fā)求解TSP問題5．while(k>=1)5.1i=k+1;5.2x[i]=1;5.3while(x[i]<=n)5.3.1如果路徑上頂點不重復(fù)，則

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

5.3.1.2if(db<=up)將路徑上的頂點和db值存儲在表PT中；

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

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

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

x2,...,t)，s和t分別為起點和終點約束條件：顯式：xi=A,B,...(i=2,...,n)隱式：cij≠∞目標(biāo)函數(shù)：cost(i)=min{cij+cost(j)}(i≤j≤n且頂點j是i的鄰接點)下界：把每一段最小的代價相加，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段的最短邊第＋與頂點ri+1相連的邊中,代價最小的邊(剩余頂點能夠達到的最小代價)優(yōu)先隊列式分支限界法求解：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])){

//頂點i到頂點j可達，且滿足控制約束

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

//加入活結(jié)點優(yōu)先隊列

MinHeapNode<Type>N;N.i=j;N.length=dist[j];H.Insert(N);}try{H.DeleteMin(E);}//取下一擴展結(jié)點

catch(OutOfBounds){break;}//優(yōu)先隊列空

}}

頂點i和j間有邊，且此路徑長小于原先從原點到j(luò)的路徑長9.2.3裝載問題問題描述：略。分析：解空間：X=(x1,x2,…,xn)，xi∈Si={0,1}，i=1,2,…,n約束函數(shù)：目標(biāo)函數(shù)：下界：…上界：…上限界函數(shù)：左孩子：Ew+w[i+1]<=c1右孩子：Ew+>bestw改進搜索算法設(shè)計：隊列式分支限界：while(true){

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

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

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

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

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

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

Q.Delete(Ew);//取下一擴展結(jié)點

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

采用最大優(yōu)先隊列存儲活結(jié)點表?；罱Y(jié)點x在優(yōu)先隊列中的優(yōu)先級定義為：從根結(jié)點到結(jié)點x的路徑所相應(yīng)的載重量Ew+

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

boolLChild;//左孩子結(jié)點標(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é)點在子集樹中相應(yīng)結(jié)點的指針Typeuweight;//活結(jié)點優(yōu)先級(上界)intlevel;//活結(jié)點在子集樹中所處的層序號};template<classType>voidAddLiveNode(MaxHeap<HeapNode<Type>>&H,bbnode*E,Typewt,boolch,intlev){//將活結(jié)點加入到表示活結(jié)點優(yōu)先隊列的最大堆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)先隊列式分支限界法,返回最優(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)前擴展結(jié)點所處的層bbnode*E=0;//當(dāng)前擴展結(jié)點TypeEw=0;//擴展結(jié)點所相應(yīng)的載重量//搜索子集空間樹while(i!=n+1){//非葉子結(jié)點//檢查當(dāng)前擴展結(jié)點的孩子結(jié)點if(Ew+w[i]<=c){//左孩子結(jié)點為可行結(jié)點AddLiveNode(H,E,Ew+w[i]+r[i],true,i+1);}//右孩子結(jié)點AddLiveNode(H,E,Ew+r[i],false,i+1);//取下一擴展結(jié)點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)度問題例9-4：批處理作業(yè)調(diào)度問題。問題描述：給定n個作業(yè)的集合J={J1,J2,…,Jn}，每個作業(yè)都有3項任務(wù)分別在3臺機器上完成，作業(yè)Ji需要機器j的處理時間為tij(1≤i≤n,1≤j≤3)，每個作業(yè)必須先由機器1處理，再由機器2處理，最后由機器3處理。批處理作業(yè)調(diào)度問題要求確定這n個作業(yè)的最優(yōu)處理順序，使得從第1個作業(yè)在機器1上處理開始，到最后一個作業(yè)在機器3上處理結(jié)束所需的時間最少。實例：設(shè)J={J1,J2,J3,J4}是4個待處理的作業(yè)，需要的處理時間如下所示。若處理順序為(J2,J3,J1,J4)，則從作業(yè)2在機器1處理開始到作業(yè)4在機器3處理完成的調(diào)度方案如下：T＝57910529957810J1J2J3J4機器1機器2機器3J2:10J3:9J1:5J4:7機器1機器2機器3(表示空閑，最后完成處理時間為54)空閑:10

J2:5空閑:4

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

J2:2空閑:11

J3:5空閑:2

J1:9J4:10等待時間+處理時間分析：解向量：X=(x1,x2,...,xn)——排列樹約束條件：顯式：xi=J1,J2,...,Jn目標(biāo)函數(shù):sum3=下限界函數(shù)：機器3有空閑機器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=

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

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

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