算法导论课件第15讲分支定界法

第6章 分支限界法,理解分支限界法的剪枝搜索策略。 掌握分支限界法的算法框架： （1）队列式(FIFO)分支限界法 （2）优先队列式分支限界法 通过应用范例学习分支限界法的设计策略。,学习要点,分支限界法的基本思想,分支限界法与回溯法,（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。,（2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。,分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。,此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。,在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。,分支限界法的基本思想,分支限界法的基本思想,常见的两种分支限界法,（1）队列式(FIFO)分支限界法 按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。,（2）优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。,分支限界法首先确定一个合理的限界函数，并根据限界函数确定目标函数的界down, up 。然后，按照广度优先策略遍历问题的解空间树，在分支结点上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的目标函数的可能取值。 如果某孩子结点的目标函数可能取得的值超出目标函数的界，则将其丢弃，因为从这个结点生成的解不会比目前已经得到的解更好；否则，将其加入待处理结点表中。依次从表PT中选取使目标函数的值取得极值的结点成为当前扩展结点，重复上述过程，直到找到最优解。,随着这个遍历过程的不断深入，表PT中所估算的目标函数的界越来越接近问题的最优解。 当搜索到一个叶子结点时，如果该结点的目标函数值是表PT中的极值（对于最小化问题，是极小值；对于最大化问题，是极大值），则该叶子结点对应的解就是问题的最优解；否则，根据这个叶子结点调整目标函数的界（对于最小化问题，调整上界；对于最大化问题，调整下界），依次考察表PT中的结点，将超出目标函数界的结点丢弃，然后从表PT中选取使目标函数取得极值的结点继续进行扩展。,单源最短路径问题,单源最短路径问题,1. 问题描述,下面以一个例子来说明单源最短路径问题：在下图所给的有向图G中，每一边都有一个非负边权。要求图G的从源顶点s到目标顶点t之间的最短路径。,单源最短路径问题,2. 剪枝策略,在算法扩展结点的过程中，一旦发现一个结点的下界不小于当前找到的最短路长，则算法剪去以该结点为根的子树。 在算法中，利用结点间的控制关系进行剪枝。从源顶点s出发，2条不同路径到达图G的同一顶点。由于两条路径的路长不同，因此可以将路长长的路径所对应的树中的结点为根的子树剪去。,单源最短路径问题,3. 算法思想,解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。,算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆（待处理结点表，以下简称表PT）中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。,单源最短路径问题,1. 问题描述,下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。,第1层,第2层,第4层,第5层,第3层,目前的最短路径是8，一旦发现某个节点的下界不小于这个最短路进，则剪枝。,利用节点的控制关系剪枝,将会产生重复的子树，剪枝,while (true) for (int j = 1; j N; N.node=j; /顶点编号为j N.length=distj; H.Insert(N); try H.DeleteMin(E); / 取下一扩展结点 catch (OutOfBounds) break; / 优先队列空 ,顶点i和j间有边，且此路径长小于原先从原点到j的路径长。 这个判断，实现了剪枝,dist:最短距离数组 prev: 前驱顶点数组 E：当前的扩展节点 c: 邻接矩阵 H： 活节点优先队列,记载最短路径,缺乏上界 函数减枝,优先权队列 VS. 先进先出队列,0/1背包问题,0/1背包问题。假设有4个物品，其重量分别为(4, 7, 5, 3)，价值分别为(40, 42, 25, 12)，背包容量W=10。首先，将给定物品按单位重量价值从大到小排序，结果如下：,应用贪心法求得近似解为(1, 0, 0, 0)，获得的价值为40，这可以作为0/1背包问题的下界。 如何求得0/1背包问题的一个合理的上界呢？考虑最好情况，背包中装入的全部是第1个物品且可以将背包装满，则可以得到一个非常简单的上界的计算方法：ub=W×(v1/w1)=10×10=100。于是，得到了目标函数的界40, 100。 限界函数为：,分支限界法求解0/1背包问题,分支限界法求解0/1背包问题，具体的搜索过程如下： （1）在根结点1，没有将任何物品装入背包，因此，背包的重量和获得的价值均为0，根据限界函数计算结点1的目标函数值为10×10=100； （2）在结点2，将物品1装入背包，因此，背包的重量为4，获得的价值为40，目标函数值为40 + (10-4)×6=76，将结点2加入待处理结点表PT中；在结点3，没有将物品1装入背包，因此，背包的重量和获得的价值仍为0，目标函数值为10×660，将结点3加入表PT中； （3）在表PT中选取目标函数值取得极大的结点2优先进行搜索；,（4）在结点4，将物品2装入背包，因此，背包的重量为11，不满足约束条件，将结点4丢弃；在结点5，没有将物品2装入背包，因此，背包的重量和获得的价值与结点2相同，目标函数值为40 + (10-4)×5=70，将结点5加入表PT中； （5）在表PT中选取目标函数值取得极大的结点5优先进行搜索； （6）在结点6，将物品3装入背包，因此，背包的重量为9，获得的价值为65，目标函数值为65 + (10-9)×4=69，将结点6加入表PT中；在结点7，没有将物品3装入背包，因此，背包的重量和获得的价值与结点5相同，目标函数值为40 + (10-4)×464，将结点6加入表PT中；,（7）在表PT中选取目标函数值取得极大的结点6优先进行搜索； （8）在结点8，将物品4装入背包，因此，背包的重量为12，不满足约束条件，将结点8丢弃；在结点9，没有将物品4装入背包，因此，背包的重量和获得的价值与结点6相同，目标函数值为65； （9）由于结点9是叶子结点，同时结点9的目标函数值是表PT中的极大值，所以，结点9对应的解即是问题的最优解，搜索结束。,分支限界法的时间性能,分支限界法和回溯法实际上都属于穷举法，当然不能指望它有很好的最坏时间复杂性，遍历具有指数阶个结点的解空间树，在最坏情况下，时间复杂性肯定为指数阶。 与回溯法不同的是，分支限界法首先扩展解空间树中的上层结点，并采用限界函数，有利于实行大范围剪枝，同时，根据限界函数不断调整搜索方向，选择最有可能取得最优解的子树优先进行搜索。所以，如果选择了结点的合理扩展顺序以及设计了一个好的限界函数，分支界限法可以快速得到问题的解。,分支限界法的较高效率是以付出一定代价为基础的，其工作方式也造成了算法设计的复杂性。 首先，一个更好的限界函数通常需要花费更多的时间计算相应的目标函数值，而且对于具体的问题实例，通常需要进行大量实验，才能确定一个好的限界函数； 其次，由于分支限界法对解空间树中结点的处理是跳跃式的，因此，在搜索到某个叶子结点得到最优值时，为了从该叶子结点求出对应的最优解中的各个分量，需要对每个扩展结点保存该结点到根结点的路径，或者在搜索过程中构建搜索经过的树结构，这使得算法的设计较为复杂；,再次，算法要维护一个待处理结点表PT，并且需要在表PT中快速查找取得极值的结点，等等。这都需要较大的存储空间，在最坏情况下，分支限界法需要的空间复杂性是指数阶。,任务分配问题,任务分配问题要求把n项任务分配给n个人，每个人完成每项任务的成本不同，要求分配总成本最小的最优分配方案。如下图所示是一个任务分配的成本矩阵。,求最优分配成本的上界和下界 考虑任意一个可行解，例如矩阵中的对角线是一个合法的选择，表示将任务1分配给人员a、任务2分配给人员b、任务3分配给人员c、任务4分配给人员d，其成本是9+4+1+4=18；或者应用贪心法求得一个近似解：将任务2分配给人员a、任务3分配给人员b、任务1分配给人员c、任务4分配给人员d，其成本是2+3+5+4=14。,显然，14是一个更好的上界。为了获得下界，考虑人员a执行所有任务的最小代价是2，人员b执行所有任务的最小代价是3，人员c执行所有任务的最小代价是1，人员d执行所有任务的最小代价是4。因此，将每一行的最小元素加起来就得到解的下界，其成本是2+3+1+4=10。需要强调的是，这个解并不是一个合法的选择（3和1来自于矩阵的同一列），它仅仅给出了一个参考下界，这样，最优值一定是10, 14之间的某个值。,设当前已对人员1i分配了任务，并且获得了成本v，则限界函数可以定义为：,（2）在结点2，将任务1分配给人员a，获得的成本为9，目标函数值为9 + (3+1+4)=17，超出目标函数的界10, 14，将结点2丢弃；在结点3，将任务2分配给人员a，获得的成本为2，目标函数值为2 + (3+1+4)=10，将结点3加入待处理结点表PT中；在结点4，将任务3分配给人员a，获得的成本为7，目标函数值为7 + (3+1+4)=15，超出目标函数的界10, 14，将结点4丢弃；在结点5，将任务4分配给人员a，获得的成本为8，目标函数值为8 + (3+1+4)=16，超出目标函数的界10, 14，将结点5丢弃；,应用分支限界法求解任务分配问题，具体的搜索过程如下： （1）在根结点1，没有分配任务，根据限界函数估算目标函数值为2+3+1+4=10；,（3）在表PT中选取目标函数值极小的结点3优先进行搜索； （4）在结点6，将任务1分配给人员b，获得的成本为2+6=8，目标函数值为8+(1+4)13，将结点6加入表PT中；在结点7，将任务3分配给人员b，获得的成本为2+3=5，目标函数值为5+(1+4)10，将结点7加入表PT中；在结点8。将任务4分配给人员b，获得的成本为2+7=9，目标函数值为9+(1+4)14，将结点8加入表PT中；,（5）在表PT中选取目标函数值极小的结点7优先进行搜索； （6）在结点9，将任务1分配给人员c，获得的成本为5+5=10，目标函数值为10+4=14，将结点9加入表PT中；在结点10，将任务4分配给人员c，获得的成本为5+8=13，目标函数值为13+4=17，超出目标函数的界10, 14，将结点10丢弃；,（7）在表PT中选取目标函数值极小的结点6优先进行搜索； （8）在结点11，将任务3分配给人员c，获得的成本为8+1=9，目标函数值为9+4=13，将结点11加入表PT中；在结点12，将任务4分配给人员c，获得的成本为8+8=16，目标函数值为16+4=20，超出目标函数的界10, 14，将结点12丢弃；,（9）在表PT中选取目标函数值极小的结点11优先进行搜索； （10）