第6章分支界限法

2023/2/1计算机算法设计与分析1第六章

分支限界法2023/2/1计算机算法设计与分析2分支限界法的求解目标分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出解空间树T中满足约束条件的所有解。分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。2023/2/1计算机算法设计与分析3分支限界法与回溯法的不同由于求解目标不同，导致分支限界法与回溯法有两点不同：①回溯法只通过约束条件剪去非可行解，而分支限界法不仅通过约束条件，而且通过目标函数的限界来减少无效搜索，也就是剪掉了某些不包含最优解的可行解。②在解空间树上的搜索方式也不相同。回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。2023/2/1计算机算法设计与分析4分支限界法是最佳优先搜索法分支限界法就是最佳优先(包括广度优先在内)的搜索法。分支限界法将要搜索的结点按评价函数的优劣排序，让好的结点优先搜索，将坏的结点剪去。所以准确说，此方法应称为界限剪支法。分支限界法中有两个要点：(1)评价函数的构造；(2)搜索路径的构造。2023/2/1计算机算法设计与分析5评价函数的构造评价函数要能够提供一个评定候选扩展结点的方法，以便确定哪个结点最有可能在通往目标的最佳路径上。一个评价函数f(d)通常可以由两个部分构成：⑴从开始结点到结点d的已有耗损值g(d)，和⑵再从结点d到达目标的期望耗损值h(d)。即：f(d)=g(d)+h(d)通常g(d)的构造较易，h(d)的构造较难。2023/2/1计算机算法设计与分析6搜索路径的构造在回溯法中，每次仅考察一条路径，因而只需要构造这一条路径即可：前进时记下相应结点，回溯时删去最末尾结点的记录。这比较容易实现。在分支限界法中，是同时考察若干条路径，那么又该如何构造搜索的路径呢？对每一个扩展的结点，建立三个信息：(1)该结点的名称；(2)它的评价函数值；(3)指向其前驱的指针；这样一旦找到目标，即可逆向构造其路径。用一个表保存准备扩展的结点，称为Open表。用一个表保存已搜索过的结点，称为Closed表。2023/2/1计算机算法设计与分析7分支限界法的一般算法⑴计算初始结点s的f(s);[s,f(s),nil]放入Open;⑵while(Open≠Φ){⑶从Open中取出[p,f(p),x](f(p)为最小);⑷将[p,f(p),x]放入Closed;⑸若p是目标，则成功返回；否则⑹{产生p的后继d并计算f(d)；对每个后继d有二种情况：①dClosed||dOpen；②dOpen&&dClosed。⑺{若([d,f’(d),p]Closed||[d,f’(d),p]Open)&&f(d)＜f’(d)，则删去旧结点并将[d,f(d),p]重新插入到Open中;否则⑻将[d,f(d),p]插入到Open中}}}。2023/2/1计算机算法设计与分析8分支限界法求单源最短路径单源最短路径问题的评价函数的构造：g(d)定义为从源s到结点d所走的路径长度：g(d)=g(p)+C[p][d]这里p为d的前驱结点，C[p][d]为p到d的距离。h(d)定义为0。于是f(d)=g(d)。源s的评价函数f(s)=0。

评价函数的下界为0；上界初始时为∞，以后不断用取得的更短路径的长度来替代。2023/2/1计算机算法设计与分析9分支限界法求最短路径举例12543102050100301060赋权图G初始时，将源[1,0,0]放入Open，Closed为空。Open表Closed表取出[1,0,0]放入Closed；生成其后继[2,10,1]、[4,30,1]和[5,100,1]，并依序放入Open。取出[2,10,1]放入Closed；生成其后继[3,60,2]，并依序插入Open。取出[4,30,1]放入Closed；生成其后继[3,50,4]和[5,90,4]，修订Open中已有的两个结点并依序排列。取出[3,50,4]放入Closed；生成其后继[2,100,3]和[5,60,3]，前者因劣于Closed中的[2,10,1]而被抛弃，后者修订了Open中的[5,90,4]。取出[5,60,3]，因其已经是目标结点，算法成功并终止。依据逆向指针可得最短路径为1→4→3→5。2023/2/1计算机算法设计与分析1015迷问题在一个4×4的方格棋盘上，放着15个数字1,2,…,15，每个数字占一格，空出一格，要求通过尽量少次移动格中的数字，将一个给定的初态变成目标状态。移动的规则是：每次只能在空格的上下左右4个位置任选一个移入空格。2023/2/1计算机算法设计与分析11问题分析对任意给定的初态，状态不再现的各种可能的移动，将产生多达16！种不同的状态，而且其中只有一个状态是目标状态。在状态空间树中，用空格的移动来代表数字的相应的移动。结点d的一个儿子结点代表了从状态d经过一次合法的移动所到达的状态。用回溯法肯定可以找到所求的最优解，但比较盲目。2023/2/1计算机算法设计与分析12构造15迷问题的评价函数评价函数f(d)=g(d)+h(d)，其中：⑴从开始结点到结点d的已有耗损值g(d)，在此就设为从根到结点d的路径长。⑵从结点d到达目标的期望耗损值h(d)。在此可设为15个数字中还没有到达相应目标位置的数字的个数。搜索过程见图6.22023/2/1计算机算法设计与分析131+41+41+21+42+12+32+33+23+02023/2/1计算机算法设计与分析14界限(Bounding)评价函数f(d)关系着算法的效率乃至成败。因为在大多数问题中f(d)只是个估计值，所以单靠f(d)是不够的。通常还要设计它的上下界函数U(d)和L(d)。L(d)≤f(d)≤U(d)。所谓分支限界法就是通过评价函数及其上下界函数的计算，将状态空间中不可能产生最佳解的子树剪去，减少搜索的范围，提高效率。因而更准确的称呼应是“界限剪支法”2023/2/1计算机算法设计与分析15界限剪枝法求0-1背包问题在回溯法中的“剪枝”：通过“物品总重量不能大于背包容量”这一约束条件将非可行解剪去。界限剪枝法中的“剪枝”：通过构造更加严格的约束条件（即限界函数）将一些非最优解的可行解分支也剪去，从而大大减少搜索空间。限界函数如何构造呢？2023/2/1计算机算法设计与分析160-1背包问题的限界函数评价函数f(d)=背包中已经装载的物品价值限界函数u(d)=当前已经找到的最好的可行解的值-（背包中已经装载的物品价值+剩余可选择物品的总价值）若u(d)>0，则说明即使把剩余的所有物品都装入背包也不可能得到更优的可行解，所以无须扩展该结点，可以剪枝。算法请自行完成2023年2月1日17分支限界法的基本思想分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。2023年2月1日18常见的两种分支限界法从活结点表中选择下一扩展结点的不同方式导致不同的分支限界法：队列式(FIFO)分支限界法：将活结点表组织成一个队列，按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。优先队列式分支限界法：将活结点表组织成一个优先队列，按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。最大优先队列：使用最大堆，体现最大效益优先最小优先队列：使用最小堆，体现最小费用优先2023年2月1日19

队列式分支限界法的搜索解空间树的方式类似于解空间树的宽度优先搜索，不同的是队列式分支限界法不搜索以不可行结点（已经被判定不能导致可行解或不能导致最优解的结点）为根的子树。这是因为，按照规则，这样的结点未被列入活结点表。2023年2月1日20优先队列式分支限界法的搜索方式是根据活结点的优先级确定下一个扩展结点。结点的优先级常用一个与该结点有关的评价函数值f(d)来表示。最大优先队列规定f(d)值较大的结点的优先级较高。在算法实现时通常用一个最大堆来实现最大优先队列，用最大堆的Deletemax运算抽取堆中的下一个结点作为当前扩展结点，体现最大效益优先的原则。类似地，最小优先队列规定f(d)值较小的结点的优先级较高。在算法实现时，常用一个最小堆来实现，用最小堆的Deletemin运算抽取堆中下一个结点作为当前扩展结点，体现最小耗费优先的原则。如何确定合适的评价函数好的评价函数不仅计算简单，还要保证最优解在搜索空间中，更重要的是能在搜索的早期对超出目标函数界的结点进行丢弃，减少搜索空间，从而尽快找到问题的最优解。2023年2月1日212023/2/1计算机算法设计与分析22用分支限界法求TSPTSP是求排列的问题，不是仅找一条路径而已。因而需要对分支限界法的一般算法作些修改：(1)待扩展的结点如果在本路径上已经出现，则不再扩展，但若是在其他路径上出现过，则仍需要扩展。(2)新结点，无论其优劣，既不影响其它路径上的结点，也不受其它路径上的结点的影响。(3)依据上界函数决定结点是否可以剪去。2023/2/1计算机算法设计与分析23分支限界法求排列⑴计算初始结点s的f(s);[s,f(s),nil]放入Open;⑵while(Open≠Φ){⑶从Open中取出[p,f(p),L];//L是路径已有结点⑷若f(p)≥U，则抛弃该路径；⑸若p是目标，则考虑修改上界函数值；否则⑹{将[p,f(p),L]放入Closed;⑺在该路径上扩展结点p；对每个后继d⑻{计算f(d)；⑼若f(d)＜U,则{L=L{p};将[d,f(d),L]依序放入Open。}}}}2023/2/1计算机算法设计与分析24分支限界法求TSP举例设有向图G=(V,E)的边的代价矩阵为C=[cij]。若不存在有向边<i,j>∈E，则定义cij=∞且规定cii=∞。不失一般性，设周游路线均以顶点1为起点。左下为一个有向图G的代价矩阵C。∞254031275∞1730251915∞6195024∞6228710∞评价函数f(d)为1到d的代价减去已经走过的边数。初始时f(1)=0;f(d)=f(p)+cpd–1，这里p是d的前驱。2023/2/1计算机算法设计与分析25分支限界法求TSP的搜索∞254031275∞1730251915∞6195024∞6228710∞102243394305262340453548523333243542793535453246437234946242843584286找到了第一条周游路线1→5→3→4→2→1，其长度为95。这不是最短周游路线，需要修改上界后继续搜索。2023/2/1计算机算法设计与分析26归约矩阵以及约数前面的搜索的效率不高，几乎要搜索全部的状态空间。其原因是评价函数以及上下界的估计太低。为了设计求解TSP问题的更好的评价函数，先定义其代价矩阵的归约矩阵和约数。给定代价矩阵C，从C的任何行i(或列i)的各元素中减去此行(或此列)的最小元素的值r(i)(或r’(i))，称为对i行(或i列)的归约。将C的各行和各列都归约后的矩阵称为C的归约矩阵。和数r=∑i≤nr(i)+∑i≤nr’(i)

称为C的约数。2023/2/1计算机算法设计与分析27例子中的归约矩阵和约数计算前面例子中的归约矩阵及其约数如下：∞254031275∞1730251915∞6195024∞6228710∞先做行归约：r(1)=25∞01562r(2)=50∞122520r(3)=11814∞50r(4)=634421∞0r(5)=715103∞再做列归约：r’(1)=r’(2)=r’(3)=r’(5)=0r’(4)=33222∞0约数r=47。2023/2/1计算机算法设计与分析28约数是周游路线长度的下界定理：设C是图G的代价矩阵，P是周游路线，则P的代价，即∑<i,j>∈Pcij=r+∑<i,j>∈Pc’ij，式中C’=[c’ij]是C的归约矩阵，r为约数。证明：由归约矩阵的构造可知：c’ij=cij–r(i)–r’(j)

即cij=c’ij+r(i)+r’(j)。任何周游路线包含n条边并且对应在C中的每行每列有且仅有一条边。于是∑<i,j>∈Pcij=∑<i,j>∈P(c’ij+r(i)+r’(j))。r+∑<i,j>∈Pc’ij。

2023/2/1计算机算法设计与分析29定义期望函数h(d)对开始结点1，令g(1)=0，h(1)=r，f(1)=r。若从结点1选择了一条边，不妨设边<1,2>，则令g(2)=f(1)+从1到2的距离l，显然l应该是c’12，而不应该再是c12了。

那么h(2)=？自然可以想到h(2)可以是从2开始的路线的下界r2。是否也可用类似求r一样去求新的约数r2呢？可以，但在此之前应将边<1,2>和所有边<1,k>和边<k,2>都删去，即置c’12、c’1k和c’k2为∞。设C’p为某路线上结点p的归约矩阵。从p选择边<p,d>所得到结点d的归约矩阵C’d和约数rd为：(1)将C’p中的c’pd，c’pk和c’kd置为∞，1≤k≤n；(2)依照求归约矩阵C’的方法对C’p进行行归约和列归约，便得到了C’d和rd。令f(1)=

g(1)+

h(1)，其中g(1)=0，h(1)=r。对任意路线上的结点d，设p是其前驱结点，则f(d)=g(d)+h(d)，其中，g(d)=f(p)+C’p[p][d]，h(d)=rd。2023/2/1计算机算法设计与分析30用新的评价函数求TSP下面用新的评价函数求前面的例子，我们已经求得了它的归约矩阵C’和约数r=47。∞015320∞1222201814∞2034418∞015100∞1472g(2)=47+0=47∞∞∞∞∞∞∞∞010801512h(2)=12+3=15f(2)=47+15=62623∞015320∞1222201814∞2034418∞015100∞g(3)=47+15=62

∞∞∞∞∞∞∞∞04313h(3)=1f(3)=63634类似地可求出f(4)=51。515类似地可求出f(5)=50。50下面优先扩展的是结点5。2此时C’2是在C’5的基础上进行。右边就是C’5。∞∞∞∞∞0∞1222∞1814∞2∞34418∞∞

∞000∞g(2)=50+0=50∞∞∞∞∞01601503h(2)=17f(2)=67673类似地计算出f(3)=68684类似地计算出f(4)=8181下面扩展f(4)=51的结点4。并用同样方法计算它们的评价函数值。2121369464154下面要扩展的结点是f(2)=62的结点2。右边是其对应的归约矩阵C’2。2∞∞

∞

∞

∞∞∞010815∞∞200∞18∞012∞00∞3g(3)=62+0=62；对C’2进行归约，∞∞∞∞∞得h(3)=0；于是f(3)=62。62对结点2的另外两个儿子进行同样的计算，得：f(4)=84，f(5)=72。484572下面对f(3)=62的结点3进行扩展。它有两个后继结点。345对结点4，g(4)=62+2=64。∞∞∞∞0h(4)=12，于是f(4)=64+12=7676对结点5，g(5)=62+0=62。∞∞

∞

∞

∞∞∞∞

∞

∞15∞∞200∞∞∞012∞∞0∞∞∞∞∞∞h(5)=0，于是f(5)=62+0=6262对结点5(f(5)=62)再进行扩展。54g(4)=62+0=62，∞∞h(4)=0，f(4)=62。62结点4是目标结点，找到了第一条路线。4这条路线的长度为62，以其为上界。其余未扩展的结点的评价函数值均超过上界，因而不再需要扩展了。××××××××××于是找到了一条最短的周游路线：1→2→3→5→4→1。2023/2/1计算机算法设计与分析31分支边与二叉树在构造求TSP的搜索树时，还有另外一种算法稍有点不同，就是将搜索树构造成二叉树。给定一条最短周游路线P，对于任一条边<i,j>只有两种情况，即<i,j>P或者<i,j>P。这就可以表示成右边的二叉树：km<i,j>n____<i,