第9章分支限界法

第9章分支限界法学习要点:

理解分支限界法的剪枝搜索策略掌握分支限界法的算法框架队列式(FIFO)分支限界法优先队列式分支限界法通过应用范例学习分支限界算法设计策略9.1.1分支限界法分支限界法类似于回溯法，也是一种在问题的解空间树T中搜索问题解的算法。分支限界法常以广度优先或以最小耗费(LC)优先的方式搜索问题的解空间树。在遍历过程中，对已经扩展出的每一个结点根据限界函数估算目标函数的可能取值，从中选取使目标函数取得极值的结点优先进行广度优先搜索，从而不断调整搜索方向，尽快找到问题的解。适用于求解最优化问题。9.1

概述9.1.2分支限界法的设计思想首先，确定一个合理的限界函数，并根据限界函数确定问题的目标函数的界[down,up](具体问题可以只有下界down，或上界up)；然后，按照广度优先策略遍历问题的解空间树：当搜索到达一个扩展结点时，一次性扩展它的所有孩子，估算每一个孩子结点的目标函数的可能取值(又称为耗费函数值)；将那些满足约束条件且耗费函数值不超过目标函数的界的孩子，插入活动结点表PT中，再从PT表中取耗费函数值极大(小)的下一结点同样扩展；直到找到所需的解或PT表为空为止。怎样确定“限界函数”？又如何求得目标函数的界呢？对于PT中的叶子结点：其耗费函数值是极值(极大或极小)，则该叶子结点对应的解就是问题的最优解；否则，将问题目标函数的界([down,up])调整为该叶子结点的耗费函数值，然后丢弃PT表中超出目标函数界的结点，再次选取结点继续扩展。例9-1：0/1背包问题。实例：假设有4个物品，其重量分别为(4,7,5,3)，价值分别为(40,42,25,12)，背包容量W=10。将给定物品按单位重量价值从大到小排序，结果如下：物品重量(w)价值(v)价值/重量(v/w)144010274263525543124分析：问题的解可表示为n元向量{x1,x2,...xn},xi{0,1}，则可用子集树表示解空间,在树中做广度优先搜索。约束条件:目标函数:下界Vdb=40(1,0,0,0)—贪心思想；上界Vub=0+(W-0)×(v1/w1)

=0+(10-0)×10=100；上限界函数：

(式9.1)目标函数的界：[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)目标函数范围：[40,100]wi=(4,7,5,3)vi=(40,42,25,12)vi/wi=(10,6,5,4)分支限界法的一般过程：1．根据限界函数确定目标函数的界[down,up]；2．将待处理结点表PT初始化为空；3．对根结点的每个孩子结点x执行下列操作

3.1估算结点x的目标函数值value;3.2若(value>=down)，则将结点x加入表PT中；4．循环直到某个叶子结点的目标函数值在表PT中最大

4.1i=表PT中值最大的结点；

4.2对结点i的每个孩子结点x执行下列操作

4.2.1估算结点x的目标函数值value;4.2.2若(value>=down)，则将结点x加入表PT中；

4.2.3若(结点x是叶子结点且结点x的value值在表PT中最大)，则将结点x对应的解输出，算法结束；

4.2.4若(结点x是叶子结点但结点x的value值在表PT中不是最大)，则令down=value，并且将表PT中所有小于value的结点删除；常见的两种分支限界法：从表PT中选择下一扩展结点的不同方式导致不同的分支限界法：队列式(FIFO)分支限界法：从左往右依次插入结点到队尾，按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。最大优先队列：使用最大堆，体现最大效益优先。最小优先队列：使用最小堆，体现最小费用优先。例如，上例0/1背包问题，采用最大优先队列式分支限界法。应用分支限界法的其他关键问题：如何确定最优解中的各个分量？对每个扩展结点保存根结点到该结点的路径；例如，0/1背包问题。将部分解(x1,…,xi)和该部分解的目标函数的上界值都存储在待处理结点表PT中，在搜索过程中表PT的状态如下：(0)60(1,0,0)64(1,0,1,0)65(a)扩展根结点后表PT状态(b)扩展结点2后表PT状态(c)扩展结点5后表PT状态(d)扩展结点6后表PT状态，最优解为(1,0,1,0)65(0)60(1,0,1)69(1,0,0)64(1)76(0)60(0)60(1,0)70结点2结点3结点3结点5结点3结点6结点7结点3结点7结点9在搜索的过程中构建搜索经过的树结构，在求得最优解时，从叶子结点不断回溯到根结点，以确定最优解中的各个分量。例如，0/1背包问题。设一个表ST，在表PT中取出最大值结点进行扩充时，将最大值结点存储到表ST中，表PT和表ST的数据结构为(物品i-1的选择结果，<物品i,物品i的选择结果>ub)，在搜索过程中表PT和表ST的状态如下：(a)扩展根结点后(b)扩展结点2后(c)扩展结点5后(d)扩展结点6后，最优解为(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中记录的就是得到最优解的搜索路径上的各个结点！分支限界法与回溯法的区别：求解目标不同：回溯法——找出满足约束条件的所有解分支限界法——找出满足条件的一个解，或某种意义下的最优解搜索方式不同：回溯法——深度优先分支限界法——广度优先或最小耗费优先此外，在分支限界法中，每一个活结点只有一次机会成为扩展结点。9.2.1TSP问题例9-2：TSP问题。问题描述：略。各个城市间的距离用代价矩阵来表示,如果(i,j)E，则cij=∞。分析：设城市按自然数1,2,...,n编号解向量：(x1,x2,...,xn)约束条件：显式约束：xi=1,2,...,n(i=1,2,...,n)隐式约束：(xi≠xj)∧(cij≠∞)9.2

广度优先分支限界法应用举例目标函数：(k∈V’)下界：ddb=((1+3)+(3+6)+(1+2)+(3+4)+(2+3))/2=14上界：dub=16(1→3→5→4→2→1)下限界函数：设已确定的顶点集合U=(r1,r2,...,rk)(式9.2)目标函数的界：[14,

16]271563134253984C=∞31583∞67916∞42574∞38923∞(a)一个无向图(b)无向图的代价矩阵从集合U中出来的边一条进边，一条出边优先队列式分支限界法求解TSP问题:目标函数范围：[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∞对每个扩展结点保存根结点到该结点的路径：(g)扩展结点16后的状态，最优解为1→3→5→4→2→1(1,2)14(1,3)14(1,4)16(a)扩展根结点后的状态(b)扩展结点2后的状态(c)扩展结点3后的状态(d)扩展结点11后的状态(e)扩展结点13后的状态(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)扩展结点10后的状态TSP问题算法的伪代码描述：1．根据限界函数计算目标函数的下界down；采用贪心法得到上界up；2．将待处理结点表PT初始化为空；3．for(i=1;i<=n;i++)x[i]=0;4．k=1;x[1]=1;//从顶点1出发求解TSP问题5．while(k>=1)5.1i=k+1;5.2x[i]=1;5.3while(x[i]<=n)5.3.1如果路径上顶点不重复，则

5.3.1.1根据式7.2计算目标函数值db；

5.3.1.2if(db<=up)将路径上的顶点和db值存储在表PT中；

5.3.2x[i]=x[i]+1;5.4若i=n且叶子结点的目标函数值在表PT中最小，则将该叶子结点对应的最优解输出；

5.5否则，若i=n，则在表PT中取叶子结点的目标函数值最小的结点db，令up=db，将表PT中目标函数值db超出up的结点删除；

5.6k=表PT中db最小的路径上顶点个数；课后作业应用分支限界法求解下图的TSP问题。9.2.2单源最短路径问题问题描述：略。例9-3：分析：采用优先队列式分支限界法，并用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。ABsCDEFGHt492386884756866537解向量：X=(s,

x2,...,t)，s和t分别为起点和终点约束条件：显式：xi=A,B,...(i=2,...,n)隐式：cij≠∞目标函数：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)下限界函数：假设已经确定了i段(1≤i≤k)，其路径为(r1,r2,…,ri,ri+1)åå+=+>Î<=++=+kijpiEvrijjjjvrcrrcdbpi21,11]}][[{min]][[1段的最短边第＋与顶点ri+1相连的边中,代价最小的边(剩余顶点能够达到的最小代价)优先队列式分支限界法求解：64s→Adb=20231startdb=14s→Bdb=16s→Cdb=15×7B→Ddb=188B→Edb=189B→Fdb=185C→Edb=16C→Fdb=181110E→Gdb=22E→Hdb=16×目标函数范围：[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;

//加入活结点优先队列

MinHeapNode<Type>N;N.i=j;N.length=dist[j];H.Insert(N);}try{H.DeleteMin(E);}//取下一扩展结点

catch(OutOfBounds){break;}//优先队列空

}}

顶点i和j间有边，且此路径长小于原先从原点到j的路径长9.2.3装载问题问题描述：略。分析：解空间：X=(x1,x2,…,xn)，xi∈Si={0,1}，i=1,2,…,n约束函数：目标函数：下界：…上界：…上限界函数：左孩子：Ew+w[i+1]<=c1右孩子：Ew+>bestw改进搜索算法设计：队列式分支限界：while(true){

//检查左儿子结点

Typewt=Ew+w[i];//左儿子结点的重量if(wt<=c){//可行结点if(wt>bestw)bestw=wt;//加入活结点队列if(i<n)Q.Add(wt);

}//检查右儿子结点

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

Q.Delete(Ew);//取下一扩展结点if(Ew==-1){//同层结点尾部

if(Q.IsEmpty())returnbestw;Q.Add(-1);//同层结点尾部标志

Q.Delete(Ew);//取下一扩展结点

i++;r-=w[i];}//进入下一层}}提前更新bestw右儿子剪枝优先队列式分支限界：

采用最大优先队列存储活结点表。活结点x在优先队列中的优先级定义为：从根结点到结点x的路径所相应的载重量Ew+

剩余集装箱的重量r。子集树中叶结点所相应的载重量与其优先级相同，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法。实现方法：(PT表结点的结构)在活结点中保存从解空间树的根结点到该活结点的路径；搜索进程中保存当前已构造出的部分解空间树；算法描述（采用第二种方式实现PT表）：template<classType>classHeapNode;classbbnode{

friendvoidAddLiveNode(MaxHeap<HeapNode<int>>&,

bbbnode*,int,bool,int);

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

friendclassAdjacencyGraph;

private:

bbnode*parent;//指向父结点的指针

boolLChild;//左孩子结点标志};template<classType>classHeapNode{

friendvoidAddLiveNode(MaxHeap<HeapNode<Type>>&,

bbnode*,Type,bool,int);friendTypeMaxLoading(Type*,Type,int,int*);public:operatorType()const{returnuweight;}private:bbnode*ptr;//指向活结点在子集树中相应结点的指针Typeuweight;//活结点优先级(上界)intlevel;//活结点在子集树中所处的层序号};template<classType>voidAddLiveNode(MaxHeap<HeapNode<Type>>&H,bbnode*E,Typewt,boolch,intlev){//将活结点加入到表示活结点优先队列的最大堆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[]){//优先队列式分支限界法,返回最优装载重量，bestx返回最优解//定义最大堆的容量为1000MaxHeap<HeapNode<Type>>H(1000);//定义剩余重量数组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;//当前扩展结点所处的层bbnode*E=0;//当前扩展结点TypeEw=0;//扩展结点所相应的载重量//搜索子集空间树while(i!=n+1){//非叶子结点//检查当前扩展结点的孩子结点if(Ew+w[i]<=c){//左孩子结点为可行结点AddLiveNode(H,E,Ew+w[i]+r[i],true,i+1);}//右孩子结点AddLiveNode(H,E,Ew+r[i],false,i+1);//取下一扩展结点HeapNode<Type>N;H.DeleteMax(N);//非空i=N.level;E=N.prt;Ew=N.uweight–r[i-1];}//构造当前最优解for(intj=n;j>0;j--){bestx[j]=E->Lchild;E=E->parent;}returnEw;}9.2.4批处理作业调度问题例9-4：批处理作业调度问题。问题描述：给定n个作业的集合J={J1,J2,…,Jn}，每个作业都有3项任务分别在3台机器上完成，作业Ji需要机器j的处理时间为tij(1≤i≤n,1≤j≤3)，每个作业必须先由机器1处理，再由机器2处理，最后由机器3处理。批处理作业调度问题要求确定这n个作业的最优处理顺序，使得从第1个作业在机器1上处理开始，到最后一个作业在机器3上处理结束所需的时间最少。实例：设J={J1,J2,J3,J4}是4个待处理的作业，需要的处理时间如下所示。若处理顺序为(J2,J3,J1,J4)，则从作业2在机器1处理开始到作业4在机器3处理完成的调度方案如下：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目标函数:sum3=下限界函数：机器3有空闲机器3有积压，极小化其中，sum2[n]=max{sum1[n],sum2[n-1]}+tn2

；

sum1[n]=sum1[n-1]+tn1设M是已安排好的作业集合，M{1,2,...,n},|M|=k。现在要处理作业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目标函数的下界:sum3db=

说明：最理想的情况下，机器1和机器2均无空闲，最后处理的作业恰好是在机器3上处理时间最短的作业。如上实例，sum3db==36遍历并估算解空间树上各结点的目标函数的下界值：根结点：sum1=0,sum2=0,M={}

k=0T＝57910529957810J1J2J3J4机器1机器2机器3优先队列式分支限界法求解过程：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从上例可知：优先队列式分支限界法中，扩展结点表PT取得极值的叶子结点就对应的是问题的最优解；扩展结点的过程，一开始实际类似“深度优先”。思考：将例9-2和例9-4改成FIFO式分支限界法，搜索过程有何不同？在算法的实现上，FIFO式分支限界法和优先队列式分支限界法的PT表数据结构一样吗？课后作业采用分支限界法求解下列作业调度问题，4个作业J1,J2,J3,J4在机器M1,M2上处理的时间矩阵如图所示。求最佳的处理顺序，使得4个作业从开始到结束处理的时间最短。(要求：画出解空间的展开)M1M2J1J2J3J49.3最小消耗(LC)搜索法9.3.1LC检索在FIFO分枝限界法中，对下一个E-结点的选择规则相当死板，在某种意义上是盲目的。对活结点使用一个“有智力”的排序函数c(.)来选取下一个E-结点往往可以加快到达一答案结点的速度。对任意结点x，可用两种标准来量度：在生成一个答案结点之前，子树x需要生成的结点个数；在子树x中离x最近的那个答案结点到x的路径长度。使用第一种度量：图中树的根结点付出的代价是4。结点(18和34)，(29和35)以及(30和38)的代价分别是3,2和1。所有在2,3和4级上剩余结点的代价应分别大于3,2和1。以这些代价作为选择下一个E-结点的依据，则E-结点依次为1,18,29和30。另外，不得已生成的结点为2,34,50,19,24,32。使用第二种度量，则E-结点只是由根到最近的那个答案结点路径上的那些结点。图9.14-皇后问题总是生成最小数目的结点9.3.2LC方法要点对状态空间树上的一个答案结点x,定义实际代价函数cost(x)。cost(x)的内涵：从状态空间树根结点出发，到达一个答案结点x，实际需要付出的“代价”。cost(x)的定义：原则上应根据具体问题加以定义。对状态空间树上任一结点x，定义代价函数c(x)。c(x)的内涵：从状态空间树根结点出发，经过x结点，在以结点x为根的子树上，搜索到一个答案结点，所需要付出的代价。定义c(x)的一般原则：若x是答案结点，则：c(x)=cost(x)；若x不是答案结点，但以x为根的子树上至少有一个答案结点，则：c(x)=min{c(answer)|answer:x上所有答案结点}若x不是答案结点，且以x为根的子树上也没有答案结点，则：c(x)=+∞对状态空间树上结点x,定义估算函数，且使满足：≤c(x)。注：与c(x)相比，应是当前“可计算”的。设计一个活结点表L，用于存放搜索过程的“活结点”。该表的数据结构可选择有序表或堆。即要求：活结点表上的所有结点，按照它们估算函数取值，构成一个有序表或堆。=h(x)+g(x)LC法搜索过程：初始：把状态空间树的根结点，做为活结点表L的第一个结点；重复以下两步，直到找到一个解，或L为空：从L上选出具有最小的结点，作为当前E-结点。依次搜索当前E-结点的所有子结点。若子结点是答案结点，则结束；否则，把子结点加入有序表L。9.3.3LC方法应用举例15迷问题。问题描述：把编号为1~15的棋子，随意放在4×4格的棋盘上(空出一个格)。要求：经过有限步的移动，把棋盘上棋子的“初态”，变成棋子号与棋盘号一致的目标状态。(注：“移动”仅限于空格周围棋子)实例：初态目标状态124563791012813141115123456789101112131415分析：实际代价函数cost(x):

若x是目标状态，则：cost(x)等于从棋盘初态，经逐步移动棋子而到达目标状态x，实际需要移动棋子总步数。代价函数c(x):若x是目标状态，则：c(x)=cost(x)若x不是目标状态，但x所在子树上存在目标状态结点，则：c(x)=min{c(x′)|x′：x子树上所有目标状态结点}若x不是目标状态，且x所在子树上也不存在任何目标状态结点，则c(x)=+∞定义估算函数：=h(x)+g(x)其中，h(x):从状态空间树的根结点到x结点路径长度；g(x)：x状态下，没有达到“目标状态”的棋子数量。124563791012813141115124563791012813141115123456791012813141115124563791012813141115g1=6h1=01g2=7g3=5g4=7234左下右1123456791012813141115g3=5311234567910128131411151234567910128