分支限界法经典案例算法分析.ppt
《分支限界法经典案例算法分析.ppt》由会员分享,可在线阅读,更多相关《分支限界法经典案例算法分析.ppt(41页珍藏版)》请在三一办公上搜索。
1、第6章 分支限界法,学习要点理解分支限界法的剪枝搜索策略。掌握分支限界法的算法框架(1)队列式(FIFO)分支限界法(2)优先队列式分支限界法 通过应用范例学习分支限界法的设计策略。(1)单源最短路径问题;(2)装载问题;(3)布线问题;(4)0-1背包问题;(5)最大团问题;(6)旅行售货员问题;,6.1分支限界法的基本思想,分支限界法与回溯法,(1)求解目标:回溯法的求解目标是找出解空间树中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出在某种意义下的最优解。,(2)搜索方式的不同:回溯法以深度优先的方式搜索解空间树,而分支限界法则以广
2、度优先或以最小耗费优先的方式搜索解空间树。,6.1分支限界法的基本思想,分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。,此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。,在分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点中,导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入活结点表中。,6.1分支限界法的基本思想,常见的两种分支限界法,(1)队列式(FIFO)分支限界法 按照队列先进先出(FIFO)原则选取下一
3、个节点为扩展节点。,(2)优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。,6.2单源最短路径问题,1.问题描述,下面以一个例子来说明单源最短路径问题:在下图所给的有向图G中,每一边都有一个非负边权。要求图G的从源顶点s到目标顶点t之间的最短路径。,6.2单源最短路径问题,1.问题描述,下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。其中,每一个结点旁边的数字表示该结点所对应的当前路长。,第1层,第2层,第4层,第5层,第3层,6.2单源最短路径问题,目前的最短路径是8,一旦发现某个节点的下界不小于这个最短路进,则剪枝,6.2单源最
4、短路径问题,利用节点的控制关系剪枝,将会产生重复的子树,剪枝,6.2单源最短路径问题,2.剪枝策略,在算法扩展结点的过程中,一旦发现一个结点的下界不小于当前找到的最短路长,则算法剪去以该结点为根的子树。在算法中,利用结点间的控制关系进行剪枝。从源顶点s出发,2条不同路径到达图G的同一顶点。由于两条路径的路长不同,因此可以将路长长的路径所对应的树中的结点为根的子树剪去。,6.2单源最短路径问题,3.算法思想,解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。,算法从图G的源顶点s和空优先队列开始。结点s被扩展后,它的儿子结点被依次插入堆中。此后,算
5、法从堆中取出具有最小当前路长的结点作为当前扩展结点,并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达,且从源出发,途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度,则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。,6.2单源最短路径问题,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间
6、有边,且此路径长小于原先从原点到j的路径长 这个判断,实现了剪枝,dist:最短距离数组prev:前驱顶点数组E:当前的扩展节点c:邻接矩阵H:活节点优先队列,记载最短路径,缺乏上界函数减枝,优先权队列 VS.先进先出队列,6.3 装载问题,1.问题描述,有一批共个集装箱要装上2艘载重量分别为C1和C2的轮船,其中集装箱i的重量为Wi,且,装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有,找出一种装载方案。,容易证明:如果一个给定装载问题有解,则采用下面的策略可得到最优装载方案。(1)首先将第一艘轮船尽可能装满;(2)将剩余的集装箱装上第二艘轮船。,6.3 装载问题
7、,将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集,使该子集中集装箱重量之和最接近。由此可知,装载问题等价于以下特殊的0-1背包问题。,例如:,6.3 装载问题,2.队列式分支限界法,在算法的while循环中,首先检测当前扩展结点的左儿子结点是否为可行结点。如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)。2个儿子结点都产生后,当前扩展结点被舍弃。活结点队列中的队首元素被取出作为当前扩展结点,由于队列中每一层结点之后都有一个尾部标记-1,故在取队首元素时,活结点队列一定不空。当取出的元素是-1时,再判断当前队列是否为空。如果队列非空,则将尾部
8、标记-1加入活结点队列,算法开始处理下一层的活结点。,6.3 装载问题,2.队列式分支限界法,while(true)/检查左儿子结点 if(Ew+wi=c)/xi=1 EnQueue(Q,Ew+wi,bestw,i,n);/右儿子结点总是可行的 EnQueue(Q,Ew,bestw,i,n);/xi=0 Q.Delete(Ew);/取下一扩展结点 if(Ew=-1)/同层结点尾部 if(Q.IsEmpty()return bestw;Q.Add(-1);/同层结点尾部标志 Q.Delete(Ew);/取下一扩展结点 i+;/进入下一层,Ew:扩展节点的载重量W:重量数组Q:活节点队列bestw
9、:当前最优载重量i:当前处理到的层数n:总货物数,6.3 装载问题,3.算法的改进,节点的左子树表示将此集装箱装上船,右子树表示不将此集装箱装上船。设bestw是当前最优解;ew是当前扩展结点所相应的重量;r是剩余集装箱的重量。则当ew+rbestw时,可将其右子树剪去,因为此时若要船装最多集装箱,就应该把此箱装上船。,另外,为了确保右子树成功剪枝,应该在算法每一次进入左子树的时候更新bestw的值。,6.3 装载问题,3.算法的改进,/检查左儿子结点 Type wt=Ew+wi;/左儿子结点的重量 if(wt bestw)bestw=wt;/加入活结点队列 if(i bestw/取下一扩展结
10、点,提前更新bestw,右儿子剪枝,6.3 装载问题,4.构造最优解,为了在算法结束后能方便地构造出与最优值相应的最优解,算法必须存储相应子集树中从活结点到根结点的路径。为此目的,可在每个结点处设置指向其父结点的指针,并设置左、右儿子标志。,class QNode QNode*parent;/指向父结点的指针 bool LChild;/左儿子标志 Type weight;/结点所相应的载重量,6.3 装载问题,找到最优值后,可以根据parent回溯到根节点,找到最优解。,4.构造最优解,/构造当前最优解for(int j=n-1;j 0;j-)bestxj=bestE-LChild;bestE
11、=bestE-parent;,LChild是左子树标志,1表示左子树,0表示右子树;bestxi取值为0/1,表示是否取该货物。,6.3 装载问题,5.优先队列式分支限界法,解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。优先队列中优先级最大的活结点成为下一个扩展结点。以结点x为根的子树中所有结点相应的路径的载重量不超过它的优先级。子集树中叶结点所相应的载重量与其优先级相同。在优先队列式分支限界法中,一旦有一个叶结点成为当前扩展结点,则可以断言该叶结点所相应的解即为最优解。此时可终止算
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 分支 限界 法经 案例 算法 分析
![提示](https://www.31ppt.com/images/bang_tan.gif)
链接地址:https://www.31ppt.com/p-6094501.html