第6章 分支限界法.ppt

《第6章 分支限界法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第6章分支限界法1学习要点理解分支限界法的剪枝搜索策略。掌握分支限界法的算法框架（1）队列式(FIFO)分支限界法（2）优先队列式分支限界法通过应用范例学习分支限界法的设计策略。（1）单源最短路径问题（2）装载问题；（3）布线问题（4）0-1背包问题；（5）最大团问题；（6）旅行售货员问题（7）电路板排列问题（8）批处理作业调度问题26.1分支限界法的基本思想分支限界法与回溯法（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。（2）搜索方式：回溯法以深

2、度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。类似于回溯法，分支限界法也是一种在问题的解空间树T上搜索问题解的算法。3分支限界法以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。4分支限界法解题步骤在问题的边带权的解空间树中进行广度

3、优先搜索找一个叶结点使其对应路径的权最小(最大)当搜索到达一个扩展结点时,一次性扩展它的所有儿子将满足约束条件且最小耗费函数目标函数限界的儿子,插入活结点表中从活结点表中取下一结点同样扩展直到找到所需的解或活动结点表为空为止5分支限界法与回溯法的差别分支限界法不仅通过约束条件,而且可通过目标函数的限界来减少无效搜索.回溯法是深度优先搜索,而分支限界法是广度优先搜索.采用广度优先搜索策略的目的是:尽早发现剪枝点.6常见的两种分支限界法（1）队列式(FIFO)分支限界法将活结点表组织成一个队列，按照先进先出（FIFO）原则选取下一个结点为扩展结点。（2）优先队列式分支限界法

4、将活结点表组织成一个优先队列，按照规定的优先级选取优先级最高的结点成为当前扩展结点。7算法实现时，通常用极大（小）堆来实现最大（小）优先队列，提取堆中下一个结点为当前扩展结点，体现最大（小）费用优先的原则。极大堆满足一个节点必定不小于其子节点，极小堆正好相反。极大堆中最大的元素必定是其根节点，堆排序算法正是根据这个特性而产生的：对一个序列，将其构造为极大堆，然后将根节点（数组首元素）和数组的尾元素交换，之后对除了尾元素之外的序列继续以上过程，直到排序完成。8堆排序堆的定义n个元素的序列{k1,k2,…,kn}当且仅当满足下列关系时，称为堆：ki≤k2iki≥k2ii=1,

5、2,…,n/2ki≤k2i+1ki≥k2i+1堆排序思路建立在树形选择排序基础上将待排序列建成堆（初始堆生成）后，序列的第一个元素（堆顶元素）就一定是序列中的最大元素；将其与序列的最后一个元素交换，将序列长度减一；再将序列建成堆（堆调整）后，堆顶元素仍是序列中的最大元素，再次将其与序列最后一个元素交换并缩短序列长度；反复此过程，直至序列长度为一，所得序列即为排序后结果。{{或910111213堆排序举例待排记录的关键字{32，12，91，26，74，58，63，85}堆排序的结果为：{12，26，32，58，63，74，85，91}。8526745863911232268

6、58526639163911285128526121226329132916332326312911285851212747412853274323274745858636358631258121258582632262632321212262612261214问题陈述设有n个物体和一个背包,物体i的重量为wi价值为pi,背包的载荷为M,若将物体i(1in,)装入背包,则有价值为pi.目标是找到一个方案,使得能放入背包的物体总价值最高.设N=3,W=(16,15,15),P=(45,25,25),C=30例1：0-1背包问题(0-1KnapsackProblem)1.

7、队列式分支限界法2.优先队列式分支限界法150-1背包问题：队列式分支限界法用一个队列存储活结点表，初始为空A为当前扩展结点，其儿子结点B和C均为可行结点，将其按从左到右顺序加入活结点队列，并舍弃A。按FIFO原则，下一扩展结点为B，其儿子结点D不可行，舍弃；E可行，加入。舍弃BC为当前扩展结点，儿子结点F、G均为可行结点，加入活结点表，舍弃C扩展结点E的儿子结点J不可行而舍弃；K为可行的叶结点，是问题的一个可行解，价值为45m=45m=0m=45m=25m=50m=0m=4516当前活结点队列的队首为F,儿子结点L、M为可行