第7章--分支限界法NEW

©2002IBMCorporationAlgorithmAlgorithmAnalysis&ComplexityTheoryUSTB算法分析与复杂度理论•2009罗熊[e-mail]北京科技大学信息工程学院计算机系©2002IBMCorporationAlgorithmAlgorithmAnalysis&ComplexityTheoryUSTB分支限界法2009.4AlgorithmUSTBAlgorithmDesign&Analysis33提纲典型实例——0-1背包问题分支限界法的基本思想典型算法例题分析AlgorithmUSTBAlgorithmDesign&Analysis4•分支限界法首先确定一个合理的限界函数，并根据限界函数确定目标函数的界[down,up]。•然后，按照广度优先策略遍历问题的解空间树，在分支结点上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的目标函数的可能取值，如果某孩子结点的目标函数可能取得的值超出目标函数的界，则将其丢弃，因为从这个结点生成的解不会比目前已经得到的解更好；否则，将其加入待处理结点序列中。依次从序列中选取使目标函数的值取得极值的结点成为当前扩展结点.•重复上述过程，直到找到最优解。1.典型实例——0-1背包问题AlgorithmUSTBAlgorithmDesign&Analysis5例：0-1背包问题。假设有4个物品，其重量分别为(4,7,5,3)，价值分别为(40,42,25,12)，背包容量W=10。首先，将给定物品按单位重量价值从大到小排序，结果如下：物品重量(w)价值(v)价值/重量(v/w)144010274263525543124AlgorithmUSTBAlgorithmDesign&Analysis6应用贪心法求得近似解为(1,0,0,0)，获得的价值为40，这可以作为0/1背包问题的下界。如何求得0/1背包问题的一个合理的上界呢？考虑最好情况，背包中装入的全部是第1个物品且可以将背包装满，则可以得到一个非常简单的上界的计算方法：ub=W×(v1/w1)=10×10=100。于是，得到了目标函数的界[40,100]。限界函数为：)()(11iiwvwWvubAlgorithmUSTBAlgorithmDesign&Analysis7×w=0,v=0ub=100w=4,v=40ub=76w=0,v=0ub=60w=11无效解w=4,v=40ub=70w=9,v=65ub=69w=4,v=40ub=64w=12无效解w=9,v=65ub=6523456789×1分支限界法求解0/1背包问题（1）在根结点1，没有将任何物品装入背包，因此，背包的重量和获得的价值均为0，根据限界函数计算结点1的目标函数值为10×10=100；（2）在结点2，将物品1装入背包，因此，背包的重量为4，获得的价值为40，目标函数值为40+(10-4)×6=76，将结点2加入待处理结点表中；（3）在结点3，没有将物品1装入背包，因此，背包的重量和获得的价值仍为0，目标函数值为10×6＝60，将结点3加入待处理表中；在表中选取目标函数值取得极大的结点2优先进行搜索；（4）在结点4，将物品2装入背包，因此，背包的重量为11，不满足约束条件，将结点4丢弃；（5）在结点5，没有将物品2装入背包，因此，背包的重量和获得的价值与结点2相同，目标函数值为40+(10-4)×5=70，将结点5加入待处理表中；在表中选取目标函数值取得极大的结点5优先进行搜索；（6）在结点6，将物品3装入背包，因此，背包的重量为9，获得的价值为65，目标函数值为65+(10-9)×4=69，将结点6加入待处理表中；（7）在结点7，没有将物品3装入背包，因此，背包的重量和获得的价值与结点5相同，目标函数值为40+(10-4)×4＝64，将结点6加入待处理表中；在表中选取目标函数值取得极大的结点6优先进行搜索；（8）在结点8，将物品4装入背包，因此，背包的重量为12，不满足约束条件，将结点8丢弃；（9）在结点9，没有将物品4装入背包，因此，背包的重量和获得的价值与结点6相同，目标函数值为65；由于结点9是叶子结点，同时结点9的目标函数值是待处理表中的极大值，所以，结点9对应的解即是问题的最优解，搜索结束。AlgorithmUSTBAlgorithmDesign&Analysis8另一个例子：神奇的9位数找出一个9位数：这个数包括了1~9这9个数字，这个9位数的前n位都能被n整除，若这个数表示为adcdefghi，则ab可被2整除，abc可被3整除，…，adcdefghi可被9整除。直接搜索：一个9重循环，遍历各种循环。分支限界：例如在循环到b等于奇数时，由于ab必须被2整除，因此奇数不满足条件，就可以不用搜索b等于奇数的所有9位数，分支后的算法效率提高了。AlgorithmUSTBAlgorithmDesign&Analysis9分支限界法是最佳优先搜索法分支限界法就是最佳优先(包括广度优先在内)的搜索法。分支限界法将要搜索的结点按评价函数的优劣排序，让好的结点优先搜索，将坏的结点剪去。所以准确说，此方法应称为界限剪支法。分支限界法中有两个要点：(1)评价函数的构造；(2)搜索路径的构造。2.分支限界法的基本思想AlgorithmUSTBAlgorithmDesign&Analysis10评价函数的构造评价函数要能够提供一个评定候选扩展结点的方法，以便确定哪个结点最有可能在通往目标的最佳路径上。一个评价函数f(d)通常可以由两个部分构成：⑴从开始结点到结点d的已有耗损值g(d)；⑵再从结点d到达目标的期望耗损值h(d)。即：f(d)=g(d)+h(d)通常g(d)的构造较易，h(d)的构造较难。AlgorithmUSTBAlgorithmDesign&Analysis11搜索路径的构造在回溯法中，每次仅考察一条路径，因而只需要构造这一条路径即可：前进时记下相应结点，回溯时删去最末尾结点的记录。这比较容易实现。在分支限界法中，是同时考察若干条路径，那么又该如何构造搜索的路径呢？对每一个扩展的结点，建立三个信息：(1)该结点的名称；(2)它的评价函数值；(3)指向其前驱的指针；这样一旦找到目标，即可逆向构造其路径。用一个表保存准备扩展的结点，称为Open表。用一个表保存已搜索过的结点，称为Closed表。AlgorithmUSTBAlgorithmDesign&Analysis12分支限界法的一般算法⑴计算初始结点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有二种情况：①dClosed||dOpen；②dOpen&&dClosed。⑺{若([d,f’(d),p]Closed||[d,f’(d),p]Open)&&f(d)＜f’(d)，则删去旧结点并将[d,f(d),p]重新插入到Open中;否则⑻将[d,f(d),p]插入到Open中}}}。AlgorithmUSTBAlgorithmDesign&Analysis13分支限界法与回溯法的比较（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。（2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。AlgorithmUSTBAlgorithmDesign&Analysis14分支限界法求单源最短路径单源最短路径问题的评价函数的构造：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；上界初始时为∞，以后不断用取得的更短路径的长度来替代。3.典型算法例题分析AlgorithmUSTBAlgorithmDesign&Analysis15分支限界法求最短路径举例12543102050100301060赋权图G初始时，将源[1,0,0]放入Open，Closed为空。Open表[1,0,0]Closed表取出[1,0,0]放入Closed；生成其后继[2,10,1]、[4,30,1]和[5,100,1]，并依序放入Open。[1,0,0][5,100,1][4,30,1][2,10,1]取出[2,10,1]放入Closed；生成其后继[3,60,2]，并依序插入Open。[2,10,1][3,60,2][4,30,1]取出[4,30,1]放入Closed；生成其后继[3,50,4]和[5,90,4]，修订Open中已有的两个结点并依序排列。[4,30,1][5,90,4][3,50,4]取出[3,50,4]放入Closed；生成其后继[2,100,3]和[5,60,3]，前者因劣于Closed中的[2,10,1]而被抛弃，后者修订了Open中的[5,90,4]。[3,50,4][5,60,3]取出[5,60,3]，因其已经是目标结点，算法成功并终止。依据逆向指针可得最短路径为1→4→3→5。AlgorithmUSTBAlgorithmDesign&Analysis16界限(Bounding)评价函数f(d)关系着算法的效率乃至成败。因为在大多数问题中f(d)只是个估计值，所以单靠f(d)是不够的。通常还要设计它的上下界函数U(d)和L(d)。L(d)≤f(d)≤U(d)。所谓分支限界法就是通过评价函数及其上下界函数的计算，将状态空间中不可能产生最佳解的子树剪去，减少搜索的范围，提高效率。因而更准确的称呼应是“界限剪支法”AlgorithmUSTBAlgorithmDesign&Analysis17用分支限界法求TSPTSP是求排列的问题，不是仅找一条路径而已。因而需要对分支限界法的一般算法作些修改：(1)待扩展的结点如果在本路径上已经出现，则不再扩展，但若是在其他路径上出现过，则仍需要扩展。(2)新结点，无论其优劣，既不影响其它路径上的结点，也不受其它路径上的结点的影响。(3)依据上界函数决定结点是否可以剪去。AlgorithmUSTBAlgorithmDesign&Analysis18分支限界法求排列⑴计算初始结点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。}}}}AlgorithmUSTBAlgorithmDesign&Analysis19分支限界法求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的前驱。AlgorithmUSTBAlgorithmDesign&Analysis20分支限界法求TSP的搜索∞254031275∞1730251915∞6195024∞6228710∞10224