• / 38
  • 下载费用:10 金币  

分支限界法 ppt.ppt

关 键 词:
分支限界法 ppt.ppt
资源描述:
第6章 分支限界法(Branch and Bound) 6.1 分支限界法的基本思想,用于求解最优化问题 1、分支限界法与回溯法的不同 分支限界法与回溯法类似,也是在问题的解空间上搜索问题解的算法。其不同点如下: 1)求解目标:回溯法的求解目标是找出解空间树中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出在某种意义下的最优解。 2)搜索方式的不同:回溯法以深度优先的方式搜索解空间树,而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。,2. 分支限界法基本思想 分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。 在分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点中,导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入活结点表中。 此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 由此可见,两种算法的最主要区别在于它们对当前扩展节点所采用的扩展方式不同。在分支限界法中,每个或结点只有一次机会成为扩展节点。,3. 常见的两种分支限界法 从活结点表中选择下一扩展结点的不同方式导致不同的分支界限法。最常见的有以下两种方式: (1)队列式(FIFO)分支限界法 按照队列先进先出(FIFO)原则选取下一个节点为扩展节点。 (2)优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 优先队列中规定的节点优先级通常用一个与该节点相关的数值p来表示。结点优先级的高低与p值的大小有关。最大优先队列规定p值较大的结点优先级高。在算法实现是通常采用最大堆来实现最大优先队列,用最大堆的Deletemax运算抽取堆中下一结点成为当前扩展节点,体现最大利益优先的原则。类似的,最小优先队列用最小堆实现。,在问题的边带权的解空间树中进行广度优先搜索. 找一个回答结点使其对应路径的权最小(最大)。当搜索到达一个扩展结点时,一次性扩展它的所有儿子,将那些满足约束条件且最小耗费函数目标函数限界的儿子,插入活动结点表中, 再从活动结点表中取下一结点同样扩展. 直到找到所需的解或活动结点表为空为止。,4、形式化描述,算法设计与分析 分支限界法,,,通常采用优先队列方式组织, c(x)小者优先。,结点x的最小耗费函数c(x):以x为根的子树所包含的回答结点中,路权最小者。若x是回答结点, 则c(x)即为该点的目标函数值; 若x是根结点, 则c(x)即为最优解值。c(x)为单增函数。若x*是任一回答结点, 且c(x*)U时, x将不必扩展(剪枝)。,目标函数限界U的调整:初始U可取,随回答结点值的求出逐步更新 为U=c(x*), x*为已知回答结点中值最小者。,活动结点表:,,算法设计与分析 分支限界法,1.取U=U(T). 2.扩展根结点的所有儿子.对每一子结点x判定其是否满足约束条件, 对满足约束条件的 x 计算 , 将 U的x 加入活动结点表. 3. x为叶结点时,检查是否c(x)U, 是则用c(x)更新U. 4.取活动结点表中的第一个结点为根, 重复2.,分支限界法解题步骤:,最小耗费函数c(x)的估算:c(x)不能即时求得, 为此取能即时计算的下界函数 代替, 应具有单调性, 且在回答结点上 =c(x),1.分支限界法不仅通过约束条件,而且可通过目标函数的限界来减 少无效搜索. 2.回溯法是深度优先搜索,而分支限界法是广度优先搜索.采用广度优先搜索策略的目的是:尽早发现剪枝点.,分支限界法与回溯法的差别:,问题陈述 设有n个物体和一个背包,物体i的重量为wi价值为pi ,背包 的载荷为M,若将物体i(1 i n,)装入背包,则有价值为pi . 目标是找到一个方案,使得能放入背包的物体总价值最高.,算法设计与分析 分枝限界法,设N=3, W=(16,15,15), P=(45,25,25), C=30,实例:0-1背包问题(0-1Knapsack Problem ),C=14 U=45,U=0,U=45,C=15 U=25,U=50 C=0,U=0,,,{B, C}, {C,E,}, {E,F,G}, {F,G}, {G},,,,,,,,,,C=14 U=45,,,,,,,,,队列式分支限界法 活动结点表:,设N=3, W=(16,15,15), P=(45,25,25), C=30,C=14 U=45,U=0,U=45,U=25,U=50,U=0,,,{B, C}, {E, C,}, {C}, {F, G,}, {G},,,,,,,,,C=14 U=
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:分支限界法 ppt.ppt
链接地址:https://www.weizhuannet.com/p-9832107.html
微传网是一个办公文档、学习资料下载的在线文档分享平台!

微传网博客

网站资源均来自网络,如有侵权,请联系客服删除!

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开