算法設(shè)計與分析：第9章 分枝限界法

第9章分枝限界法

學習要點：理解分枝限界法的剪枝搜索策略。分枝限界法與回溯法的異同。掌握幾種常見的分枝限界法思想： （1）FIFO(先進先出)分枝限界法 （2）LIFO(堆棧,即D-檢索)分枝限界法

（3）LC(優(yōu)先權(quán)隊列)分枝限界法分枝限界法的算法框架。通過應(yīng)用范例學習分枝限界法的設(shè)計策略。 （1）15謎問題 （2）帶時限的作業(yè)排序

（3）0/1背包章節(jié)內(nèi)容:

9.1一般方法

9.2求最優(yōu)解的分枝限界法

9.3帶時限的作業(yè)排序

9.40/1背包9.1 分枝限界法的一般方法采用廣度優(yōu)先產(chǎn)生狀態(tài)空間樹的結(jié)點，并使用剪枝函數(shù)的方法稱為——分枝限界法。分枝限界法的基本做法是： 以廣度優(yōu)先的方式搜索問題的狀態(tài)空間樹。每一個活結(jié)點只有一次機會成為擴展結(jié)點。 按照廣度優(yōu)先的原則，活結(jié)點一旦成為擴展結(jié)點（E結(jié)點）R后，就依次生成它的所有孩子結(jié)點。在這些孩子結(jié)點中，導致不可行解或?qū)е路亲顑?yōu)解的孩子結(jié)點被舍棄，其余孩子結(jié)點被一一加入活結(jié)點表中。

此后，R自身成為死結(jié)點，從活結(jié)點表中取下一結(jié)點成為當前擴展結(jié)點，并重復上述結(jié)點擴展過程。這個過程一直持續(xù)到找到所需的解或活結(jié)點表為空時為止。

分枝限界法與回溯法的異同一、分枝限界法與回溯法的共同點 都是在問題的狀態(tài)空間樹上搜索問題解的算法,都通過活結(jié)點表實現(xiàn)。都用約束函數(shù)剪去不含答案結(jié)點的分枝,用限界函數(shù)剪去不含最優(yōu)解的分枝.二、分枝限界法與回溯法的區(qū)別（1）求解目標不同：回溯法的求解目標是找出解空間樹中滿足約束條件的所有可行解；而分枝限界法的求解目標則是找出滿足約束條件的一個可行解，或某種意義下的最優(yōu)解。（2）搜索方式不同：回溯法以深度優(yōu)先的方式搜索解空間樹，而分枝限界法則以廣度優(yōu)先的方式搜索解空間樹。（3）對當前擴展結(jié)點的擴展方式不同：回溯法中的每個活結(jié)點可能多次成為當前擴展結(jié)點，縱深方向擴展其一個兒子，然后再回溯后擴展其他兒子；而分枝限界法中每一個活結(jié)點只有一次機會成為擴展結(jié)點，一次產(chǎn)生所有孩子結(jié)點，自身成為死結(jié)點，之后無需再返回該結(jié)點處。分枝限界法的種類根據(jù)從活結(jié)點中選擇下一個擴展結(jié)點的不同次序，將分枝限界法分為三類：（1）隊列式(FIFO)分枝限界法：將活結(jié)點表組織成一個隊列，按隊列的先進先出(FIFO)原則選取下一個結(jié)點為當前擴展結(jié)點；（2）堆棧式(LIFO)分枝限界法：將活結(jié)點表組織成一個堆棧，按堆棧的后進先出(LIFO)原則選取下一個結(jié)點為當前擴展結(jié)點；（3）優(yōu)先隊列式(LC)分枝限界法：將活結(jié)點表組織成一個優(yōu)先隊列，并按優(yōu)先隊列中規(guī)定的結(jié)點優(yōu)先級選取優(yōu)先級最高的下一個結(jié)點為當前擴展結(jié)點。程序9-1分枝限界法的算法框架(為簡化起見,用指針代表所指向的結(jié)點)voidBranchBound(Node*t) //t是指向狀態(tài)空間樹的根結(jié)點指針{do{ //lst為活結(jié)點表,表中元素為指針類型; for(對結(jié)點E的每個不受限的孩子) {x=newNode; x->parent=E; //構(gòu)造E的孩子結(jié)點x if(x是一個答案結(jié)點)

{輸出從x到t的一條路經(jīng);return;} //輸出一個可行解后,算法終止

lst.Append(x); //否則（x不是答案結(jié)點）x進活結(jié)點表

}

if(lst.IsEmpty())

//活結(jié)點表lst為空時

{cout<<“沒有答案結(jié)點”;return;} //搜索失敗終止

lst.Serve(E); //從活結(jié)點表lst中輸出一個活結(jié)點為E-結(jié)點

}while(1);}求得一個可行解后終止利用FIFO分枝限界法求解4-皇后問題時,實際生成的部分狀態(tài)空間樹如圖9-1所示(請與P182圖8-6比較):03113212389112BBB0321819242B2932303102ansBB031343540B45383613BB021505156B61545212B595702BB12比較圖8-6和圖9-1可以看到:(n-皇后問題求第一個可行解時)FIFO分枝限界法并不占優(yōu)勢.LC分枝限界法

從活結(jié)點表中選擇下一個擴展結(jié)點(E結(jié)點)時,通過衡量一個活結(jié)點的搜索代價，來確定哪個活結(jié)點能夠盡快到達一個答案結(jié)點。答案結(jié)點X的搜索代價cost(X)：從根結(jié)點開始,直到搜索到答案結(jié)點X為止所耗費的搜索時間.代價函數(shù)：從根結(jié)點到X的搜索代價。 若X是答案結(jié)點,則是從根結(jié)點到X的搜索代價;若X不是答案結(jié)點且子樹X上不含任何答案結(jié)點,則=∞;若X不是答案結(jié)點但子樹X上包含答案結(jié)點,則等于子樹X上具有最小搜索代價的答案結(jié)點的代價. (見圖9-2(a))定義4個相關(guān)函數(shù)：相對代價函數(shù)：衡量一個結(jié)點X的相對代價。衡量標準一：生成答案結(jié)點前，子樹X上需要生成的結(jié)點數(shù)目衡量標準二：子樹X上離X最近的答案結(jié)點到X的路徑長度(見圖9-2(b))相對代價估計函數(shù)：估計結(jié)點X的相對代價。 是的估計值，是X到達一個答案結(jié)點所需代價的估計

一般的，若Y是X的孩子，則。

結(jié)點的代價和相對代價都難以計算，因此通常采用它們的估計值作為評價函數(shù)：代價估計函數(shù)： 由兩個部分組成：從根到X的代價f(X)和從X到答案結(jié)點的估計代價，即。 一般的，f(X)為X在樹中的層次。以代價估計函數(shù)最小的活結(jié)點作為下一個擴展結(jié)點（E結(jié)點）的搜索策略稱為最小成本檢索，簡稱LC-檢索。如果，則，LC-檢索表現(xiàn)出深度優(yōu)先搜索特性，成為D-檢索（LIFO檢索）。如果，且f(X)等于X在樹中的層次，則LC-檢索表現(xiàn)出寬度優(yōu)先搜索特性，成為FIFO檢索。15謎問題

問題描述：在一個4×4的方形棋盤上放置了15塊編了號的牌，還剩下一個空格。號牌的一次合法移動是指將位于空格四周（上、下、左、右）的一塊號牌移入空格位置的四種移動方式。 要求：對于任意給定的一種初始排列，通過一系列的合法移動，將給定的初始排列轉(zhuǎn)換成如圖9-3(c)所示的目標排列：123456789101112131415注意：（一個4×4的棋盤有16!種不同的排列）并非所有可能的狀態(tài)作為初始狀態(tài)都能到達目標狀態(tài)。對給定的初始狀態(tài)，當且僅當為偶數(shù)時，可以由此初始狀態(tài)到達目標狀態(tài)。Less(k)為滿足下列情況的號牌數(shù)目：號牌牌號小于k，但被放置在號牌k的位置之后。(見圖9-3(a))i和j分別是空格在棋盤上的行和列下標。定理9-1給出了一種簡單的判定方法：采用廣度優(yōu)先搜索由初始狀態(tài)圖9-3(b)移動號牌得到目標狀態(tài)圖9-3(c)的過程。(見圖9-4狀態(tài)空間樹)由于移動號牌和移動空格是等價的，因此從父狀態(tài)到子狀態(tài)的一次轉(zhuǎn)換可以視為空格的一次向上、下、左或右的合法移動。圖中剪去了那些與雙親狀態(tài)重復的孩子結(jié)點及其子樹。（即不能和上一步移動方向剛好相反）到達邊界時，也無法繼續(xù)移向界外方向。第一種搜索方式：FIFO分枝限界法采用深度優(yōu)先搜索（回溯法）生成狀態(tài)空間樹的方式。（見圖9-5部分狀態(tài)空間樹）——深度優(yōu)先搜索沿著狀態(tài)生成樹中最左邊的路徑搜索，離目標狀態(tài)越來越遠。第二種搜索方式：LIFO分枝限界法（D-檢索）第三種搜索方式：LC分枝限界法定義代價估計函數(shù)：作為搜索代價進行LC檢索。（見圖9-6狀態(tài)空間樹）其中：是從根到結(jié)點X的路徑長度，是不在其位的非空白牌數(shù)目?！梢钥吹竭@種代價估計函數(shù)對這一實例十分有效。課堂作業(yè)

判斷由如圖(a)所示的初始狀態(tài)出發(fā)，經(jīng)過一系列合法的號牌移動能否到達圖(b)所示的目標狀態(tài)？為什么？ 如果可以到達目標狀態(tài)，請畫出其LC分枝限界法實際生成的那部分狀態(tài)空間樹。(a)123456789101112131415(b)134527896101213141115課外提高題請編程實現(xiàn)用LC分枝限界法求解15迷問題。9.2求最優(yōu)解的分枝限界法定義一個與最優(yōu)化問題的目標函數(shù)有關(guān)的代價函數(shù)（不同于上一節(jié)的搜索代價）和上下界函數(shù)：用分枝限界法求最優(yōu)解時，需要使用上下界函數(shù)作為限界函數(shù)（也即一種剪枝函數(shù)），以剪去不含最優(yōu)解的分枝。定義9-1:

狀態(tài)空間樹上一個結(jié)點X的代價函數(shù)定義為：若X是答案結(jié)點，則c(X)為X所代表的可行解的目標函數(shù)值；若X為非可行解結(jié)點，則c(X)=∞；若X代表部分向量，則c(X)是以X為根的子樹上具有最小代價的結(jié)點代價。定義9-2:

函數(shù)和分別是代價函數(shù)的上界和下界函數(shù)。對所有結(jié)點X，總有難以計算基于上下界函數(shù)的分枝限界法對任意結(jié)點X，若，則X子樹可以剪枝。因為c(X)是X子樹上最小代價答案結(jié)點的代價，是其下界。而U是迄今已知的最小代價答案結(jié)點的代價值（即：整個樹最小代價的上界值）。現(xiàn)若有，必可斷定：X子樹上不含最小代價答案結(jié)點。（假定目標函數(shù)取最小值時為最優(yōu)解。）設(shè)定一個上界變量U，記錄迄今為止已知的最小代價答案結(jié)點的代價值(即最小代價的上界值，最小代價答案結(jié)點的代價值不會超過U)?；谏舷陆绾瘮?shù)的分枝限界法對任意結(jié)點X，若，則X子樹可以剪枝。（假定目標函數(shù)取最小值時為最優(yōu)解。）設(shè)定一個上界變量U，記錄迄今為止已知的最小代價答案結(jié)點的代價值(即最小代價的上界值，最小代價答案結(jié)點的代價值不會超過U)。U的值是不斷修改的，根據(jù)搜索中獲取的越來越多關(guān)于最小代價的上界信息，逐漸逼近最小代價答案結(jié)點的代價值（即整棵樹的最小目標函數(shù)值——最優(yōu)解值）。在算法已經(jīng)搜索到一個答案結(jié)點之后，所有滿足的子樹X都可以剪除。基于上下界函數(shù)的分枝限界法

求最優(yōu)解的限界方法：（按以下原則修正U的值）如果X是答案結(jié)點，cost(X)是X所代表的可行解的目標函數(shù)值，則U=min{cost(X),U};如果X代表部分分量，u(X)是該子樹上最小代價答案結(jié)點代價的上界值，則U=min{u(X)+ε,U}；—— 于是，算法可使用作為剪枝條件盡可能剪除多余分枝。Livelist<Node*>lst(mSize); Node*ans=null,*x,*E=t; //lst為FIFO隊列do{for(對結(jié)點E的每個孩子）

{ x=newNode; x->parent=E; if() //若，則x不會被限界函數(shù)剪枝

{lst.Append(x); //x進FIFO隊列l(wèi)st

if(x是一個答案結(jié)點&&cost(x)<U)

//x為答案結(jié)點時修正U

{U=cost(x); ans=x;} elseif(u(x)+ε<U)U=u(x)+ε;

//x為非答案結(jié)點時修正U }}do{if(lst.IsEmpty())returnans; //隊列為空時，返回ans，算法結(jié)束。

lst.Serve(E); //從FIFO隊列l(wèi)st中取出一個活結(jié)點E}while(); //找到滿足的活結(jié)點E作為當前擴展結(jié)點}while(1);基于上下界函數(shù)的FIFO分枝限界法：Livelist<Node*>lst(mSize); Node*ans=null,*x,*E=t; //lst為優(yōu)先權(quán)隊列do{for(對結(jié)點E的每個孩子）

{ x=newNode; x->parent=E; if() //若，則x不會被限界函數(shù)剪枝

{lst.Append(x); //x進優(yōu)先權(quán)隊列l(wèi)st

if(x是一個答案結(jié)點&&cost(x)<U)

//x為答案結(jié)點時修正U

{U=cost(x); ans=x;} elseif(u(x)+ε<U)U=u(x)+ε;

//x為非答案結(jié)點時修正U }}if(！lst.IsEmpty()){ lst.Serve(E); //從優(yōu)先權(quán)隊列l(wèi)st中取出一個活結(jié)點E if()returnans; //若，則算法結(jié)束。

}elsereturnans; //若隊列為空，則算法結(jié)束。}while(1);基于上下界函數(shù)的LC分枝限界法：9.3帶時限的作業(yè)排序 n個作業(yè)，每個作業(yè)i處理所需時間為ti，如果能夠在時限di內(nèi)完成將可收益pi。 將每個作業(yè)所需的處理時間、要求時限和收益用三元組(ti,di,pi)0≤i<n表示。求使得總收益最大的作業(yè)子集J。采用可變大小元組(x0,x1,......,xk)表示解，xi為作業(yè)編號。例9-1

設(shè)有帶時限的作業(yè)排序?qū)嵗簄=4, (p0,d0,t0)=(5,1,1), (p1,d1,t1)=(10,3,2), (p2,d2,t2)=(6,2,1), (p3,d3,t3)=(3,1,1),求使得總收益最大的作業(yè)子集J。顯式約束：xi∈{0,1,.....,n-1}且xi<xi+1隱式約束：對入選子集J的作業(yè)(x0,x1,......,xk)存在一種作業(yè)排列使J中作業(yè)均能如期完成。目標函數(shù)：已入選子集J的所有作業(yè)所獲總收益。則使目標函數(shù)（總收益）最大的作業(yè)子集是最優(yōu)解。目標函數(shù)：未入選子集J的作業(yè)所導致的損失則使目標函數(shù)最小的作業(yè)子集是最優(yōu)解。采用可變大小元組(x0,x1,......,xk)表示解，xi為作業(yè)編號。例9-1

設(shè)有帶時限的作業(yè)排序?qū)嵗簄=4, (p0,d0,t0)=(5,1,1), (p1,d1,t1)=(10,3,2), (p2,d2,t2)=(6,2,1), (p3,d3,t3)=(3,1,1),求使得總收益最大的作業(yè)子集J。顯式約束：xi∈{0,1,.....,n-1}且xi<xi+1隱式約束：對入選子集J的作業(yè)(x0,x1,......,xk)存在一種作業(yè)排列使J中作業(yè)均能如期完成。X是狀態(tài)空間樹上一個結(jié)點，J=(x0,x1,...,xk)是迄今為止作業(yè)子集（0,1,…,xk)中已入選的作業(yè)子集。設(shè)計結(jié)點X的上下界函數(shù)：下界函數(shù)：上界函數(shù)：下界函數(shù)實際上是由迄今為止作業(yè)子集J=（0,1,...,xk)中，未能入選J的作業(yè)所造成的損失。它必定是最終損失的下界，即有：。X是狀態(tài)空間樹上一個結(jié)點，J=(x0,x1,......,xk)是已入選的作業(yè)子集。設(shè)計結(jié)點X的上下界函數(shù)：下界函數(shù)：上界函數(shù)：上界函數(shù)值由兩部分組成：一是迄今為止作業(yè)子集J=（x0,x1,...,xk)中未入選的作業(yè)所造成的損失，也即；二是假定作業(yè)xk后所有的作業(yè)都未入選，所造成的損失。它是X結(jié)點處可以預計的最大損失;必有。P109定理6-3可以對一個作業(yè)子集有效的判斷：是否存在一種排列，使得子集中的作業(yè)按該次序處理都不超期。定理6-3：X=(x0,x1,……,xk)是k個作業(yè)的集合，α=(α0,α1,……,αk)是X的一種特定排列，它使得dα0≤dα1≤……≤dαk，其中dαj是作業(yè)αj的時限。X是一個可行解當且僅當X中的作業(yè)能夠按α次序調(diào)度而不會有作業(yè)超期。因此，將作業(yè)按時限非減次序排列。例9-1可變大小元組表示的狀態(tài)空間樹（圖9-8）(t0,d0,p0)=(1,1,5)(t1,d1,p1)=(1,1,3)(t2,d2,p2)=(1,2,6)(t3,d3,p3)=(2,3,10)=5u=21=5u=15=u=11=0u=24U=24=3u=13U=13=0u=19U=19=8u=18U=18=u=14U=14123457910141511x0=0x0=1x0=2x0=3x1=1x1=2x1=3x1=2x1=3x1=3x2=3x2=368=u=9U=9=u=8U=8ans采用FIFO分枝限界法實現(xiàn)：（即采用先進先出隊列為活結(jié)點表）方形結(jié)點代表因不滿足約束條件而被剪枝的子樹——不可行可變長度元組解，狀態(tài)空間樹中每個結(jié)點均可視為解狀態(tài)。用FIFO分枝限界法實現(xiàn)帶時限的作業(yè)排序：狀態(tài)空間樹的結(jié)點結(jié)構(gòu)Node：structNode{Node(Node*par,intk){ parent=par; j=k;}Node*parent;

//指向該結(jié)點的雙親結(jié)點intj; //該結(jié)點代表的解分量x[i]=j}活結(jié)點表的結(jié)點結(jié)構(gòu)qNode：template<classT>structqNode{qNode(){}qNode(Tp,Tlos,intsd,intk,Node*pt){prof=p;loss=los;d=sd;ptr=pt;j=k;}Tprof,loss;//loss為當前結(jié)點下界函數(shù)(X),即已有損失

//prof為當前結(jié)點已獲收益，上界函數(shù)u(X)=24-profintj,d; //d是迄今為止的時間

//當前活結(jié)點所代表的解分量x[i]=jNode*ptr; //指向狀態(tài)空間樹中相應(yīng)的結(jié)點};Node*E,*child;E=root=newNode(Null,-1);Queue<qNode<T>>q(mSize);//FIFO隊列（活結(jié)點表）qNode<T>ep(0,0,0,-1,root),ec;//ep為擴展結(jié)點，ec為ep的孩子TU=total+epsilon; //U賦初值為全部作業(yè)收益之和total。while(1){Tloss=ep.loss,prof=f; //loss為已造成的損失(ep)，prof為已獲收益

E=ep.ptr;for(intj=ep.j+1;j<n;j++) //從左向右逐個生成擴展結(jié)點ep所有可能的孩子

{if(ep.d+t[j]<=d[j]&&loss<U) //前者為約束條件(可行)，后者為限界條件(剪枝){child=newNode(E,j); //滿足if條件則生成ep的當前孩子

f=prof+p[j];ec.d=ep.d+t[j];ec.ptr=child;ec.loss=loss;ec.j=j;//由ec指向

q.Append(ec);

//將ec加入活結(jié)點表(即FIFO隊列q) Tcost=f; //計算ec的上界函數(shù)值u(ec)=cost if(cost<U) {U=cost;ans=child;} //更新上界變量U的值，并用ans記錄迄今為止最優(yōu)解

}

loss=loss+p[j]; //為生成ep的下一個孩子做準備，求下一個孩子的loss值(ec)}do{ if(q.IsEmpty())returnU;//活結(jié)點表(隊列)為空時，返回最優(yōu)解值(最小損失)，結(jié)束

ep=q.Front(); q.Serve();}while(ep.loss>=U); //從活結(jié)點表(隊列)中選擇下一個滿足ep.loss<U的擴展結(jié)點}當前擴展結(jié)點為ep判斷條件是否滿足若滿足條件，則生成ep的孩子結(jié)點ec,并加入活結(jié)點表計算ec的上界函數(shù)值u(ec)更新U，同時記錄迄今為止最優(yōu)解。準備生成下一個孩子，并計算其loss值選擇下一個滿足ep.loss<U的擴展結(jié)點ep執(zhí)行上述程序時(圖9-8)狀態(tài)空間樹中哪些結(jié)點將實際生成？(t0,d0,p0)=(1,1,5)(t1,d1,p1)=(1,1,3)(t2,d2,p2)=(1,2,6)(t3,d3,p3)=(2,3,10)=5u=21=5u=15=u=11=0u=24U=24=3u=13U=13=0u=19U=19=8u=18U=18=u=14U=1412345791011x0=0x0=1x0=2x0=3x1=2x1=3x1=2x1=3x1=3x2=315x2=3x1=168=9u=9U=9=u=8U=8ans14x2=3思考9若采用LC分枝限界法求解該實例，又將如何選取擴展結(jié)點？狀態(tài)空間樹中的哪些結(jié)點將被剪枝？(t0,d0,p0)=(1,1,5)(t1,d1,p1)=(1,1,3)(t2,d2,p2)=(1,2,6)(t3,d3,p3)=(2,3,10)=5u=21

=5u=15=u=11=0u=24U=24=3u=13U=13=0u=19U=19=8u=18U=18=u=14U=14123457101113x0=0x0=1x0=2x0=3x1=2x1=3x1=2x1=3x1=3x2=3x2=3x1=18

=9u=9U=9=u=8U=8ansx2=3用頂點編號表示結(jié)點的生成順序思考126511869129.40/1背包解的結(jié)構(gòu)、約束條件、目標函數(shù)和狀態(tài)空間樹的分析與回溯法相同。分枝限界法求解0/1背包問題的關(guān)鍵問題是設(shè)計上下界函數(shù)LBB(X)、UBB(X)：

設(shè)p(i)/w(i)≥p(i+1)/w(i+1)，0≤i＜n-1X是狀態(tài)空間樹上的結(jié)點，從根到X的部分向量為(x0,x1,...,xk-1)。以X為根的子樹可以看成背包載重為cu，由剩余物品組成物品集的0/1背包的狀態(tài)空間樹。設(shè)Z代表子樹X上一般背包問題的最優(yōu)解(zk,zk+1,...,zn-1)ans代表子樹X上0/1背包的最優(yōu)解(xk,xk+1,...,xn-1)Y代表子樹X上0/1背包的一個可行解(yk,yk+1,...,yn-1)則必有：于是得到0/1背包問題的上下界函數(shù)：下界函數(shù)：(X子樹上的最大收益答案結(jié)點的收益下界估計值）上界函數(shù)：(X子樹上的最大收益答案結(jié)點的收益上界估計值）(x0,x1,...,xk-1)TXYZyk...yn-1zk...zn-1xk...xn-1ans一般背包最優(yōu)解0/1背包可行解答案結(jié)點的代價函數(shù)：定義一個下界變量L記錄迄今為止最大收益答案結(jié)點的收益下界值。這樣，當生成某個結(jié)點X時，若UBB(X)<L，則可剪去該X子樹。L的修正方法：若X不是答案結(jié)點，則L=max{LBB(X)-ε，L}若X是答案結(jié)點，則L=max{cost(X)，L}已經(jīng)生成至少一個答案結(jié)點后，可以放心的剪去所有UBB(X)≤L的X子樹。0/1背包算法實現(xiàn)Node為狀態(tài)空間樹的結(jié)點類； （采用雙親表示法，其中指針parent指向雙親結(jié)點，布爾變量left表示當前結(jié)點是其雙親的左孩子還是右孩子。）pqNode為優(yōu)先權(quán)隊列的元素類； （按UBB值由大到小的順序，存儲那些自身已經(jīng)生成、而孩子結(jié)點還未考察的結(jié)點。）Knapsack為背包類；stuctNode //狀態(tài)空間樹結(jié)點{Node(Node*par,boollft){parent=par;left=lft;}Node*parent; //指向雙親結(jié)點的指針

boolleft; //若當前結(jié)點是雙親的左孩子，則left為true；

//否則為false。}Node為狀態(tài)空間樹的結(jié)點類template<classT>stuctpqNode //活結(jié)點結(jié)構(gòu){pqNode(){}pqNode(floatcap,Tprof,Tub,intlev,Node*p){ cu=cap; profit=prof; level=lev; UBB=ub; ptr=p;}floatcu; //背包的剩余載重cuTprofit,UBB; //已獲收益profit和上界函數(shù)值UBBintlevel; //當前結(jié)點的level（根結(jié)點為0）

Node*ptr; //指向狀態(tài)空間樹上相應(yīng)的結(jié)點}pqNode為優(yōu)先權(quán)隊列的元素類template<classT>classKnapsack //背包類{public:Knapsack(T*prof,float*wei,floatmm,intlen);TLCBB(); //求最優(yōu)解值

voidGenerateAns(int*x); //產(chǎn)生最優(yōu)解private:voidLUBound(Tcp,floatcw,intk,T&LBB,T&UBB); //計算結(jié)點的上下界UBB和LBBT*p; //p保存n個物品價值

float*w,m; //w保存n個物品重量，m為背包載重

intn; //物品數(shù)目

Node*ans,*root; //狀態(tài)空間樹的最優(yōu)解結(jié)點和根}Knapsack為背包類voidKnapsack<T> //計算k層結(jié)點處的UBB和LBB ::LUBound(Tcp,floatcw,intk,T&LBB,T&UBB){LBB=cp; floatc=cw;//已獲收益和剩余載重

for(inti=k;i<n;i++)//依次考察物品k~n-1是否都能放入背包

{if(c<w[i]){//①剩余背包載重已放不下整個物品i時，才執(zhí)行此分支

UBB=LBB+c*p[i]/w[i];//計算UBB：一般背包最優(yōu)解值

for(intj=i+1;j<n;j++)//計算LBB：任意一個可行解

if(c>=w[j]{c=c-w[j];LBB=LBB+p[j];}

return;

//結(jié)束函數(shù)

}程序9-6上下界函數(shù)已獲收益剩余載重//②c≥w[i]剩余背包載重仍能放下整個物品i時，一直執(zhí)行

c=c-w[i];LBB=LBB+p[i];}//for循環(huán)結(jié)束

UBB=LBB;//物品k~n-1均可放入背包時，不會執(zhí)行分支①

//因此UBB=LBB}(UBB,LBB)=(38,32)12345678x0=1000L=32-εe(15,0,38,0,ptr)x1=1x2=1x3=1剩余載重已獲收益結(jié)點層次M=15,(w0,w1,w2,w3)=(2,4,6,9),(p0,p1,p2,p3)=(10,10,12,18)固定長度元組解，只有最下層結(jié)點可以視為解狀態(tài)。(UBB,LBB)=(38,32)12345678x0=1000L=32-εe(15,0,38,0,ptr)x1=1x2=1x3=1剩余載重c=15>w[k]=2時,可以生成左孩子。向左走時UBB和LBB值不變。(38,32)L=32-εe(13,10,38,1,ptr)(38,32)12345678x0=1000L=32-εe(15,0,38,0,ptr)x1=1x2=1x3=1向右走時k+1層的UBB和LBB值可能改變，需重新求。計算LUBBound(0,15,1,LBB,UBB)得(38,32)L=32-εe(15,0,32,1,ptr)(32,22)L=32-ε由于UBB=32>L=32-ε，因此生成右孩子。由于L=32-ε>LBB=22，因此L值不做更新。e(13,10,38,1,ptr)(38,32)12345678x0=1000L=32-εx1=1x2=1x3=1(38,32)L=32-εe(15,0,32,1,ptr)(32,22)L=32-εe(13,10,38,1,ptr)選擇優(yōu)先權(quán)隊列中UBB值大的結(jié)點，向下生成孩子。剩余載重c=13>w[1]=4,可以生成左孩子。向左走時UBB和LBB值不變。(38,32)L=32-εe(9,20,38,2,ptr)(38,32)12345678x0=1000L=32-εx1=1x2=1x3=1(38,32)L=32-εe(15,0,32,1,ptr)(32,22)L=32-ε(38,32)L=32-ε計算LUBBound(10,13,2,LBB,UBB)得e(13,10,36,2,ptr)(36,22)L=32-ε由于UBB=36>L=32-ε，因此生成右孩子。由于L=32-ε>LBB=22，因此L值不做更新。e(9,20,38,2,ptr)e(13,10,38,1,ptr)(38,32)12345678x0=1000L=32-εx1=1x2=1x3=1(38,32)L=32-εe(15,0,32,1,ptr)(32,22)L=32-ε(38,32)L=32-εe(13,10,36,2,ptr)(36,22)L=32-εe(9,20,38,2,ptr)選擇優(yōu)先權(quán)隊列中UBB值大的結(jié)點，向下生成孩子。(38,32)L=32-εe(3,32,38,3,ptr)(38,32)12345678x0=1000L=32-εx1=1x2=1x3=1(38,32)L=32-εe(15,0,32,1,ptr)(32,22)L=32-ε(38,32)L=32-εe(13,10,36,2,ptr)(36,22)L=32-εe(9,20,38,2,ptr)(38,32)L=32-εe(3,32,38,3,ptr)L=38-ε(38,38)e(9,20,38,3,ptr)計算LUBBound(20,9,3,LBB,UBB)得由于UBB=38>L=32-ε，因此生成右孩子。由于L=32-ε<LBB=38，因此更新L=38-ε。(38,32)1234