分支限界法ppt课件.ppt

第9章分支限界法,1,学习要点:理解分支限界法的剪枝搜索策略掌握分支限界法的算法框架队列式(FIFO)分支限界法优先队列式分支限界法通过应用范例学习分支限界算法设计策略,2,9.1概述,9.1.1分支限界法分支限界法类似于回溯法，也是一种在问题的解空间树T中搜索问题解的算法。分支限界法常以广度优先或以最小耗费(LC)优先的方式搜索问题的解空间树。在遍历过程中，对已经扩展出的每一个结点根据限界函数估算目标函数的可能取值，从中选取使目标函数取得极值的结点优先进行广度优先搜索，从而不断调整搜索方向，尽快找到问题的解。适用于求解最优化问题。,3,9.1.2分支限界法的设计思想首先，确定一个合理的限界函数，并根据限界函数确定问题的目标函数的界down,up(具体问题可以只有下界down，或上界up)；然后，按照广度优先策略遍历问题的解空间树：当搜索到达一个扩展结点时，一次性扩展它的所有孩子，估算每一个孩子结点的目标函数的可能取值(又称为耗费函数值)；将那些满足约束条件且耗费函数值不超过目标函数的界的孩子，插入活动结点表PT中，再从PT表中取耗费函数值极大(小)的下一结点同样扩展；直到找到所需的解或PT表为空为止。,怎样确定“限界函数”？又如何求得目标函数的界呢？,4,对于PT中的叶子结点：其耗费函数值是极值(极大或极小)，则该叶子结点对应的解就是问题的最优解；否则，将问题目标函数的界(down,up)调整为该叶子结点的耗费函数值，然后丢弃PT表中超出目标函数界的结点，再次选取结点继续扩展。,5,例9-1：0/1背包问题。实例：假设有4个物品，其重量分别为(4,7,5,3)，价值分别为(40,42,25,12)，背包容量W=10。将给定物品按单位重量价值从大到小排序，结果如下：,6,分析：问题的解可表示为n元向量x1,x2,.xn,xi0,1，则可用子集树表示解空间,在树中做广度优先搜索。约束条件:目标函数:下界Vdb=40(1,0,0,0)贪心思想；上界Vub=0+(W-0)(v1/w1)=0+(10-0)10=100；上限界函数：(式9.1),目标函数的界：40,100,前i个物品获得的价值,剩余容量全部装入物品i+1，最多能够获得的价值,7,分支限界法求解0/1背包问题：,w=0,v=0ub=100,w=4,v=40ub=76,w=0,v=0ub=60,w=11,w=4,v=40ub=70,w=9,v=65ub=69,w=4,v=40ub=64,w=12,w=9,v=65ub=65,2,3,4,5,6,7,8,9,1,PT=2,3,无效解,PT=5,3,PT=6,7,3,无效解,x1=1,x1=0,x2=1,x2=0,x3=1,x3=0,x4=1,x4=0,PT=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),8,分支限界法的一般过程：,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的结点删除；,9,常见的两种分支限界法：从表PT中选择下一扩展结点的不同方式导致不同的分支限界法：队列式(FIFO)分支限界法：从左往右依次插入结点到队尾，按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。最大优先队列：使用最大堆，体现最大效益优先。最小优先队列：使用最小堆，体现最小费用优先。例如，上例0/1背包问题，采用最大优先队列式分支限界法。,10,应用分支限界法的其他关键问题：如何确定最优解中的各个分量？对每个扩展结点保存根结点到该结点的路径；例如，0/1背包问题。将部分解(x1,xi)和该部分解的目标函数的上界值都存储在待处理结点表PT中，在搜索过程中表PT的状态如下：,11,在搜索的过程中构建搜索经过的树结构，在求得最优解时，从叶子结点不断回溯到根结点，以确定最优解中的各个分量。例如，0/1背包问题。设一个表ST，在表PT中取出最大值结点进行扩充时，将最大值结点存储到表ST中，表PT和表ST的数据结构为(物品i-1的选择结果，ub)，在搜索过程中表PT和表ST的状态如下：,说明：ST中记录的就是得到最优解的搜索路径上的各个结点！,12,分支限界法与回溯法的区别：求解目标不同：回溯法找出满足约束条件的所有解分支限界法找出满足条件的一个解，或某种意义下的最优解搜索方式不同：回溯法深度优先分支限界法广度优先或最小耗费优先此外，在分支限界法中，每一个活结点只有一次机会成为扩展结点。,13,9.2广度优先分支限界法应用举例,9.2.1TSP问题例9-2：TSP问题。问题描述：略。各个城市间的距离用代价矩阵来表示,如果(i,j)E，则cij=。分析：设城市按自然数1,2,.,n编号解向量：(x1,x2,.,xn)约束条件：显式约束：xi=1,2,.,n(i=1,2,.,n)隐式约束：(xixj)(cij),14,目标函数：(kV)下界：ddb=(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14上界：dub=16(135421)下限界函数：设已确定的顶点集合U=(r1,r2,.,rk)(式9.2),目标函数的界：14,16,从集合U中出来的边,一条进边，一条出边,15,优先队列式分支限界法求解TSP问题:,目标函数范围：14,16,4,12db=14,2,3,5,6,7,8,1,startdb=14,13db=14,14db=16,15db=19,23db=16,24db=16,25db=19,32db=16,34db=15,35db=14,9,10,11,52db=19,54db=14,12,13,42db=16,14,42db=18,45db=15,15,16,52db=20,17,db=19,PT=2,3,4,db=19,PT=6,7,9,10,11,4,db=18,db=19,PT=6,7,9,16,14,4,db=20,PT=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=16135421,16,对每个扩展结点保存根结点到该结点的路径：,17,TSP问题算法的伪代码描述：1根据限界函数计算目标函数的下界down；采用贪心法得到上界up；2将待处理结点表PT初始化为空；3for(i=1;i=1)5.1i=k+1;5.2xi=1;5.3while(xi=n)5.3.1如果路径上顶点不重复，则5.3.1.1根据式7.2计算目标函数值db；5.3.1.2if(db,27,friendTypeMaxLoading(Type*,Type,int,int*);public:operatorType()constreturnuweight;private:bbnode*ptr;/指向活结点在子集树中相应结点的指针Typeuweight;/活结点优先级(上界)intlevel;/活结点在子集树中所处的层序号;templatevoidAddLiveNode(MaxHeap,28,N.uweight=wt;N.level=lev;N.ptr=b;H.Inset(N);templateTypeMaxLoading(Typew,Typec,intn,intbestx)/优先队列式分支限界法,返回最优装载重量，bestx返回最优解/定义最大堆的容量为1000MaxHeapH(1000);/定义剩余重量数组rType*r=newTypen+1;rn=0;for(intj=n-1;j0;j-)rj=rj+1+wj+1;,29,/初始化inti=1;/当前扩展结点所处的层bbnode*E=0;/当前扩展结点TypeEw=0;/扩展结点所相应的载重量/搜索子集空间树while(i!=n+1)/非叶子结点/检查当前扩展结点的孩子结点if(Ew+wiN;H.DeleteMax(N);/非空i=N.level;E=N.prt;,30,Ew=N.uweightri-1;/构造当前最优解for(intj=n;j0;j-)bestxj=E-Lchild;E=E-parent;returnEw;,31,9.2.4批处理作业调度问题例9-4：批处理作业调度问题。问题描述：给定n个作业的集合J=J1,J2,Jn，每个作业都有3项任务分别在3台机器上完成，作业Ji需要机器j的处理时间为tij(1in,1j3)，每个作业必须先由机器1处理，再由机器2处理，最后由机器3处理。批处理作业调度问题要求确定这n个作业的最优处理顺序，使得从第1个作业在机器1上处理开始，到最后一个作业在机器3上处理结束所需的时间最少。,32,实例：设J=J1,J2,J3,J4是4个待处理的作业，需要的处理时间如下所示。若处理顺序为(J2,J3,J1,J4)，则从作业2在机器1处理开始到作业4在机器3处理完成的调度方案如下：,等待时间+处理时间,33,分析：解向量：X=(x1,x2,.,xn)排列树约束条件：显式：xi=J1,J2,.,Jn目标函数:sum3=下限界函数：,机器3有空闲,机器3有积压,，极小化,其中，sum2n=maxsum1n,sum2n-1+tn2；sum1n=sum1n-1+tn1,设M是已安排好的作业集合，M1,2,.,n,|M|=k。现在要处理作业k+1，有：,sum1k+1=sum1k+tk+1,1sum2k+1=maxsum1k+1,sum2k+tk+1,2,maxsum2n,sum3n-1+tn3,34,目标函数的下界:sum3db=说明：最理想的情况下，机器1和机器2均无空闲，最后处理的作业恰好是在机器3上处理时间最短的作业。如上实例，sum3db=36遍历并估算解空间树上各结点的目标函数的下界值：根结点：sum1=0,sum2=0,M=k=0,35,优先队列式分支限界法求解过程：,J4,sum1=0+7db=38sum2=15,2M=k=1,J1,sum1=0+5db=36sum2=5+7=12,1M=k=0,startsum1=0,sum2=0,3M=k=1,J2,sum1=0+10db=44sum2=12,4M=k=1,J3,sum1=0+9db=40sum2=18,5M=k=1,6M=1k=2,J1J2,sum1=15db=42sum2=20,7M=1k=2,J1J3,sum1=14db=38sum2=22,8M=1k=2,J1J4,sum1=12db=36sum2=20,9M=1,4k=3,J1J4J2,sum1=22db=41sum2=27,10M=1,4k=3,J1J4J3,sum1=21db=37sum2=30,11M=1,4,3k=4,J1J4J3J2,sum1=31db=36sum24=36,PT=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=sum24+t23=38,sum1k=sum1k-1+tk,1sum2k=maxsum1k,sum2k-1+tk,2,下界sum3db=36,36,从上例可知：优先队列式分支限界法中，扩展结点表PT取得极值的叶子结点就对应的是问题的最优解；扩展结点的过程，一开始实际类似“深度优先”。思考：将例9-2和例9-4改成FIFO式分支限界法，搜索过程有何不同？在算法的实现上，FIFO式分支限界法和优先队列式分支限界法的PT表数据结构一样吗？,37,课后作业,采用分支限界法求解下列作业调度问题，4个作业J1,J2,J3,J4在机器M1,M2上处理的时间矩阵如图所示。求最佳的处理顺序，使得4个作业从开始到结束处理的时间最短。(要求：画出解空间的展开),M1,M2,J1,J2,J3,J4,38,9.3最小消耗(LC)搜索法,9.3.1LC检索在FIFO分枝限界法中，对下一个E-结点的选择规则相当死板，在某种意义上是盲目的。对活结点使用一个“有智力”的排序函数c(.)来选取下一个E-结点往往可以加快到达一答案结点的速度。对任意结点x，可用两种标准来量度：在生成一个答案结点之前，子树x需要生成的结点个数；在子树x中离x最近的那个答案结点到x的路径长度。,39,使用第一种度量：图中树的根结点付出的代价是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-皇后问题,总是生成最小数目的结点,40,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)；,41,若x不是答案结点，但以x为根的子树上至少有一个答案结点，则：c(x)=minc(answer)|answer:x上所有答案结点若x不是答案结点，且以x为根的子树上也没有答案结点，则：c(x)=+对状态空间树上结点x,定义估算函数，且使满足：c(x)。注：与c(x)相比，应是当前“可计算”的。设计一个活结点表L，用于存放搜索过程的“活结点”。该表的数据结构可选择有序表或堆。即要求：活结点表上的所有结点，按照它们估算函数取值，构成一个有序表或堆。,=h(x)+g(x),42,LC法搜索过程：初始：把状态空间树的根结点，做为活结点表L的第一个结点；重复以下两步，直到找到一个解，或L为空：从L上选出具有最小的结点，作为当前E-结点。依次搜索当前E-结点的所有子结点。若子结点是答案结点，则结束；否则，把子结点加入有序表L。,43,9.3.3LC方法应用举例15迷问题。问题描述：把编号为115的棋子，随意放在44格的棋盘上(空出一个格)。要求：经过有限步的移动，把棋盘上棋子的“初态”，变成棋子号与棋盘号一致的目标状态。(注：“移动”仅限于空格周围棋子)实例：初态目标状态,44,分析：实际代价函数cost(x):若x是目标状态，则：cost(x)等于从棋盘初态，经逐步移动棋子而到达目标状态x，实际需要移动棋子总步数。代价函数c(x):若x是目标状态，则：c(x)=cost(x)若x不是目标状态，但x所在子树上存在目标状态结点，则：c(x)=minc(x)|x：x子树上所有目标状态结点若x不是目标状态，且x所在子树上也不存在任何目标状态结点，则c(x)=+,45,定义估算函数：=h(x)+g(x)其中，h(x):从状态空间树的根结点到x结点路径长度；g(x)：x状态下，没有达到“目标状态”的棋子数量。,g1=6,h1=0,1,g2=7,g3=5,g4=7,2,3,4,左,下,右,1,46,g3=5,3,1,g5=6,6,5,7,左,右,下,g6=4,g7=5,2,g9=3,g8=5,下,上,9,8,3,47,g9=3,9,3,10,11,左,