7--分枝-限界法解析

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,7 分枝-限界法branch and bound,分支限界法类似于回溯法，也是一种在问题的解空间树T上搜寻问题解的算法。,但分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的全部解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在某种意义下的最优解。,分支限界法的搜寻方式,分支限界法则以广度优先或以最小消耗优先的方式搜寻解空间树T。,7.1 搜寻方法,在扩展结点处，先生成其全部的儿子结点分支，将它们存入活节点表，然后再从当前的活结点表中选择下一个扩展节点。,为了有效地选择下一扩展结点，以加速搜寻的进程，在每一活结点处，计算一个函数值限界，并依据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜寻朝着解空间树上有最优解的分支推动，以便尽快地找出一个最优解。,7.1.1 广度优先,当前扩展节点E的全部儿子进展检测，满足约束条件的儿子，放入活结点表中，该扩展节点E完成其使命，成为死节点，再从或节点表中取出的其它节点，作为新的扩展节点。,1,2,3,4,活节点表,L=(2,3,4),两种广度搜寻策略,FIFO检索 活节点表中的活节点按先进先出取出的方式，称为(First in First Out)，,LIFO检索 活节点表中的活节点按后进先出取出的方式，称为(Last in First Out)。,1,2,3,4,L,=(2,3,4),5,1,2,3,4,6,L,=(3,4,5,6),1,2,3,4,6,1,2,3,4,5,L,=(2,3,5,6),L,=(2,3,4),X2=3,1,2,3,4,5,6,7,12,8,13,16,9,14,17,10,11,15,X1=1,X1=2,X1=3,X1=4,X2=3,X2=4,X2=4,X2=1,X2=1,X3=2,X3=1,X3=4,X3=3,X4=3,X4=2,以4后问题的状态空间树的FIFO搜寻为例：,最初E-为1，产生儿子2，3，4，5，放入活节点表。,L=(2,3,4,5),L=(3,4,5,6,7),L=(,4,5,6,7,8),L=(5,6,7,8,9),L=(6,7,8,9,10,11),L=(8,9,10,11,12),L=(9,10,11,12,13),L=(11,13,14),L=(13,14,15),L=(14,15),L=(15),L=(),LIFO和FIFO搜寻对下一个E-结点的选择规章是“盲目的”，不能保证这种选择规章可以尽快地找到问题的解。,7.1.2 最小代价搜寻(LC检索),对活结点使用一个代价排序函数c()来选取下一个E-结点希望花最小的代价找到问题的解，或是找到最小代价的解。,代价函数,c(X),：,对于任一结点,X,，要付出的代价：,在子树,X,中离,X,最近的答案结点到,X,的路径长度。,r,x,a,.,用c()表示“有智力的”排序函数，又称为结点本钱函数。它的定义如下：,假设X是答案结点，则c(X)是由状态空间树的根结点到X的本钱，,假设X不是答案结点且子树X 不包含任何答案结点，则c(X)。,r,.,x,c(X)=c(a),c(X),r,.,a,x,c(X),问题：如何计算 c()？要得到结点本钱函数c()所用的计算工作量与解原问题具有一样的简单度。,引入估值函数：,用估量代价的方法在算法中对活结点排序。,h(X)：由根结点到结点X的本钱。,r,.h(x),x,a,.,：是由X到达一个答案结点的代价估量。则,对于任意节点,x,，设,最小代价搜寻：用本钱估量函数,选择下一个E-节点。,检索策略总是选取 有最小本钱估值的活结点作为下一个E-结点。因此，这种检索策略称之为最小代价检索，简称LC-检索leastCostSearch。,伴之有界函数的LC-检索称为LC搜寻。,1,2,3,4,L,=(2,3,4),假设有 LeastCost(L)=3,则用3作为下一个扩展节点,6,1,2,3,4,5,L,=(2,4,5,6),例7.1 用最小代价搜寻9宫问题的解。9宫问题如下：在如下图的3*3的棋盘上，要求用最少的步骤，将8个处于初始状态的数字移动到目标状态。移动规章是：只能在空格的上下左右4个数字中人选一个移入方格。本例的初始状态是可以到目标状态的。,2,3,1,6,4,7,5,8,1,3,8,4,7,6,5,2,初始状态 目标状态,分析：,1)状态节点为棋盘的某一状态。,2)子节点为可以移动数字块到达的状态。,3)代价函数为从初始状态到达目标状态所移动的步骤。,最小代价估量函数：,=从初始状态到X所移动的次数+还未到位的数字方块数,从初始状态到X所移动的次数是实际消耗的代价，还未到位的数字方块数表示至少还要移动的次数。初始状态为根节点，有：,2,3,1,6,4,7,1,5,8,1,3,8,4,7,6,5,2,初始状态 目标状态,1,2,3,1,4,7,6,5,8,2,3,1,6,4,7,5,8,2,3,1,6,4,7,5,8,2,8,3,1,4,7,6,5,2,3,1,8,4,7,6,5,2,3,1,4,7,6,5,8,8,3,2,1,4,7,6,5,2,8,3,7,1,4,6,5,3,1,8,4,7,6,5,2,2,1,8,4,7,6,5,3,1,3,8,4,7,6,5,2,1,3,8,4,7,6,5,2,2,8,3,1,6,4,7,5,1,2,3,4,5,6,7,8,9,10,11,12,4,6,4,6,5,5,6,6,6,5,6,5,C(13)=5,13,L=(3,2,4),L=(5,6,2,4,7),L=(6,2,4,7,8,9),L=(10,2,4,7,8,9,11),L=(12,2,4,7,8,9,11),找到一个解,L=(2,4,7,8,9,11),找最优解的LC搜寻算法,设Cost(x)为可行解的本钱，(最小)优化问题要求找有最小本钱的可行解。,定义状态空间树上任一结点x的本钱函数C(x)如下:,如x为可行叶结点则C(x)=Cost(x);否则C(x)=以x为根的子树中可行解本钱的最小值,如其子树中无可行解则C(x)=,LC-检索的抽象化掌握,procedure LC-(T),E T /根节点为扩展节点,parentT 0,while(true),if E是答案节点且 then return,for E 的每个儿子节点X,Add(X)/参加活节点表,parentX E /记住父节点,从答案节点回溯,if 活节点表空 return(“no answer”),E从活节点表中取出有最小(X)的活节点X，并删除X,2,3,1,4,7,6,5,8,2,3,1,6,4,7,5,8,2,3,1,6,4,7,5,8,2,8,3,1,4,7,6,5,2,3,1,8,4,7,6,5,2,3,1,4,7,6,5,8,8,3,2,1,4,7,6,5,2,8,3,7,1,4,6,5,3,1,8,4,7,6,5,2,2,1,8,4,7,6,5,3,1,3,8,4,7,6,5,2,1,3,8,4,7,6,5,2,2,8,3,1,6,4,7,5,1,2,3,4,5,6,7,8,9,10,11,12,4,6,4,6,5,5,6,6,6,5,6,5,C(13)=5,13,L=(3,2,6)P1=0,L=(5,6,2,4,7),P2=P3=P4=1,L=(6,2,4,7,8,9),L=(10,2,4,7,8,9,11),L=(12,2,4,7,8,9,11),找到一个解,L=(2,4,7,8,9,11),P5=P6=,P7=3,P8=P9=5,P10=P11=6,P12=10,P13=12,算法正确性证明：,当算法完毕在第4行时(E)=c(E);,且对活节点表中其它节点X都有,(X)(E)及c(X)(X),所以E是最小本钱答案节点,例,7.2,单源最短路径问题,1.,问题描述,下面以一个例子来说明单源最短路径问题：在以下图所给的有向图G中，每一边都有一个非负边权。要求图G的从源顶点s到目标顶点t之间的最短路径。,2.,状态空间树,以下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。,1)最小代价估值函数：节点对应的当前路长。有,(X),c(X),3.,算法思想,解单源最短路径问题选择活节点的优先级是,节,点所对应的当前路长。,算法从图G的源顶点s和空优先队列开头。顶点s被扩展后，它的儿子结点被依次插入活节点队列中。此后，算法从队列中取出具有最小当前路长的节点作为当前扩展节点，并依次检查与当前扩展节点相邻的全部顶点。,假设从当前顶点i到顶点j有边可达，且从源动身，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活节点插入到活节点优先队列中。这个节点的扩展过程始终连续到活节点优先队列为空时为止。,4,、数据描述,原图用矩阵G表示。Gi,j=表示顶点i,j之间无边,解空间树的节点用构造表示：,i：解空间树的节点号,j：图的顶点号,length：路长,1,2,3,4,6,7,5,5,3,12,2,8,6,1,4,7,6,3,1,1,2,3,4,5,8,6,(2,4,3),5,2,3,4,6,3,6,9,8,(4,3,6,5),7,8,3,5,7,9,(7,3,6,5,8),9,6,10,5,7,13,9,14,(3,6,5,810,9,11),11,到达了目标节点7，但 c(X)(X)，不能确定1,4,3,7是最短路线.,因此，需要连续搜寻,1,2,3,4,6,7,5,5,3,12,2,8,6,1,4,7,6,3,1,1,2,3,4,5,8,6,(2,4,3),5,2,3,4,6,3,6,9,8,(4,3,6,5),7,8,3,5,7,9,(7,3,6,5,8),9,6,10,5,7,13,9,14,(3,6,5,810,9),11,3,8,6,12,10,13,7,15,5,14,14,(6,5,810,12,9,14),6,9,16,7,21,3,6,(5,810,12,9,14),5,9,6,11,7,16,5,3,措施：,增加限界值，即到达定点j的最短路径，假设某条到达j的路径大于这个最短路径值，该条路径就可以不考虑了。,设置全局变量 distj：从s到j的最短路长，Pj：最短路径上节点j的父节点。,1,2,3,4,6,7,5,5,3,12,2,8,6,1,4,7,6,3,1,1,2,3,4,5,8,6,(2,4,3),5,2,3,4,6,3,6,9,8,(4,3,5,6),7,8,3,5,7,9,(7,3,5,6,8),9,6,10,5,7,13,9,14,(3,5,6,810,9,11),11,(6,8),0,5,8,6,8,9,dist,迷途的,LC-,检索,不能尽快找到,1,2,3,4,6,5,5,10 0,20 0,20,10,10 10,LC没能到达这个最小本钱答案结点的缘由在于有两个这样的结点X和Y，当其c(X)c(Y)时，,假设使每一对c(X)c(Y)的X，Y结点都有,那么，LC-总会找到一个最小本钱答案结点。,7.1.3 分枝限界搜寻,令U为当前优化(解)本钱值，作为上界函数。,当活节点表中节点的下界估量均U时算法完毕,(x)U可以用来在搜寻中进展限界,假设 (x)U,活节点X可以被杀死，这是由于由X可以到达,的全部答案节点有C(X)(x)U,这种限界方法也可用于,FIFO,活节点表上，称为,FIFO,分枝,-,限界。,U,初始为，其后用新得到的可行解值加以修改。,承受下界函数使算法，削减了盲目性,通过设置最小本钱 的上界U使算法进一步加速。,2)单源最短路线问题的上界函数U(x),从源顶点s动身，2条不同路径到达图G的同一顶点。由于两条路径的路长不同，因此可以将路长较长所对应的树中的结点为根的子树剪去。,3.,算法思想,解单源最短路径问题选择活节点的优先级是,节,点所对应的当前路长。,算