s-第6章_heaven-14分析.ppt

  1. 1、本文档共46页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
学习要点 理解分支限界法的剪枝有哪些信誉好的足球投注网站策略 掌握分支限界法的算法框架 队列式(FIFO)分支限界法 优先队列式分支限界法 通过应用范例学习分支限界法的设计策略 单源最短路径问题 装载问题; 0-1背包问题; 最大团问题; 旅行售货员问题 批处理作业调度问题 总结 理解分支限界法的剪枝有哪些信誉好的足球投注网站策略 掌握分支限界法的算法框架 队列式(FIFO)分支限界法 优先队列式分支限界法 本书中,bestp和下界L合二为一 装载问题 构造最优解 为了在算法结束后能方便地构造出与最优值相应的最优解,算法必须存储相应子集树中从活结点到根结点的路径。为此目的,可在每个结点处设置指向其父结点的指针,并设置左、右儿子标志。 找到最优值后,可以根据parent回溯到根节点,找到最优解。 装载问题 优先队列式分支限界法 解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。 优先队列中优先级最大的活结点成为下一个扩展结点。以结点x为根的子树中所有结点相应的路径的载重量不超过它的优先级。 在优先队列式分支限界法中,一旦有一个叶结点成为当前扩展结点,则可以断言该叶结点所相应的解即为最优解。此时可终止算法。 旅行售货员问题 问题描述 给定n个顶点的带权图G=(V, E),图中各边的权为正数,图中的一条周游路线是包括V中的每个顶点在内的一条回路,一条周游路线的费用是这条路线上所有边的权之和。 旅行商问题(Traveling Salesperson)是要在图G中找出一条有最小费用的周游路线。此问题是NP完全问题。 旅行售货员问题 实例——FIFO队列式 A B 1 C 2 F 3 L 4 G 4 M 3 D H 2 N 4 I 4 O 2 E J 2 P 3 K 3 Q 2 3 4 1 3 4 2 30 6 10 5 4 20 C,D,E F,G,H,I,J,K B L,M,N,P,Q 59 66 25 26 旅行售货员问题 实例——优先队列式(1) A B 1 C 2 D H 2 N 4 E J 2 K 3 3 4 1 3 4 2 30 6 10 5 4 20 E,D,C B 25 J,K,N,I,C K,N,I,C N,I,C I 4 D,J,K,C H,J,K,I,C 旅行售货员问题 实例——优先队列式(2) 1 3 4 2 30 6 10 5 4 20 A B 1 C 2 D H 2 N 4 E J 2 P 3 K 3 3 4 25 25 I 4 旅行售货员问题 实例——归约矩阵法 -10 -2 -2 -3 -4 21 行约数 = -1 -0 -3 -0 -0 4 列 约 数 || 矩阵约数r=行约数+列约数=25 最小代价函数C’(1)=25 旅行售货员问题 实例——归约矩阵法 1 3 4 2 30 6 10 5 4 20 旅行售货员问题 4?1 旅行售货员问题 4?1 3?2 旅行售货员问题 4?1 3?2 1?3 旅行售货员问题 4?1 3?2 1?3 2?4 周游路径:1?3?2?4?1 最小耗费:25 批处理作业调度问题 问题的描述 给定n个作业的集合{J1,J2,…,Jn}。 每个作业必须先由机器1处理,然后由机器2处理。 作业Ji需要机器j的处理时间为tji。 对于一个确定的作业调度,设Fji是作业i在机器j上完成处理的时间。所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。 批处理作业调度问题 对于给定的n个作业,制定最佳作业调度方案,使其完成时间和达到最小。 批处理作业调度问题 实例 最佳调度方案是1,3,2,其完成时间和为18。 B C 1 F 2 L 3 G 3 M 2 D H 1 N 3 I 3 O 1 E J 1 P 2 K 2 Q 1 2 3 19 18 20 21 19 19 3 2 作业3 1 3 作业2 1 2 作业1 机器2 机器1 tji 注意到如果选择Pk,使t1pk在k=r+1时依非减序排列,S1则取得极小值。同理如果选择Pk使t2pk依非减序排列,则S2取得极小值。 这可以作为优先队列式分支限界法中的限界函数。 批处理作业调度问题 限界函数 在结点E处相应子树中叶结点完成时间和的下界是 欢迎辞 * 智能信息处理研究中心(RCIIP) P a n P a n * 智能信息处理研究中心(RCIIP) P a n 第6章 分支限界法 潘海为 Birds of a feather flock together ——物以类聚、一丘之貉 分支限界法的背景——理查德.卡普 在IBM期间,深入研究了与实

文档评论(0)

风凰传奇 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档