算法课件第6章分支限界法.pptVIP

* * * * * * * * * * * * * * * * * * * * * * * 旅行商问题 对于树中的第 i 层节点W 路径上已选顶点为{v1, v2, …, vi} 当前路径的长度为 P 剩余顶点为为{vi+1, …, vn} 连接 vj 的最短出边的长度为Minout(vj) bound(W)=P+ 以W为根的子树中的解的代价不少于bound(W) * 旅行商问题 堆式分支限界法2 优先级测度：bound(W) —— 最小堆 直到某个叶节点Y成为扩展节点 bound(Y)等于Y的路径长度 堆中其它节点的代价都大于bound(Y) 优化 bestp：当前最优值 剪去当前代价大于等于bestp的节点及其子树 * 旅行商问题 堆式分支限界法2 a b c d 30 6 10 5 4 20 Minout(a)=4 Minout(b)=5 Minout(c)=4 Minout(d)=5 最小堆 {F, G, H} {F, K, L, H} {I, J, K, L, H} {I, P, K, L, H} {I, P, K, R, H} {I, P, K, X, H} 最优解：X (acdba) bestp=25 * 批处理作业调度问题 输入 n个作业{1, …, n} 两台机器（M1和M2） 作业 i 在M1和M2上的处理时间分别为 a[i] 和 b[i] 每个作业必须现由M1处理，再由M2处理 输出 作业调度方案使得总等待时间最小 作业 i在M1和M2上的完成时间分别为 A[i] 和 B[i] 总等待时间为 * 批处理作业调度问题 解空间树 作业 a[i] b[i] Job 1 2 1 Job 2 3 1 Job 3 2 3 * 批处理作业调度问题 对于树中第 i 层节点V V已经安排了作业{J1, J2, …, Ji} 已安排的作业的等待时间为 * 批处理作业调度问题 对于树中第 i 层节点V 设以V为根的子树中某个叶节点W的调度为 {J1, …, Ji ，Ji+1 , …, Jn} 如果从Ji+1开始机器1没有空闲，则 {Ji+1 , …, Jn}的总等待时间不少于 … 如果a[Jx]在x?i+1时按非递减序排列 S1取得极小值S’1 {Ji+1 , …, Jn}的总等待时间? S’1 * 批处理作业调度问题 对于树中第 i 层节点V 设以V为根的子树中某个叶节点W的调度为 {J1, …, Ji ，Ji+1 , …, Jn} 如果从Ji+1开始机器2没有空闲，则 {Ji+1 , …, Jn}的总等待时间? … 如果b[Jx]在x?i+1时按非递减序排列 S2取得极小值S’2 {Ji+1 , …, Jn}的总等待时间? S’2 * 批处理作业调度问题 对于树中第 i 层节点V V已经安排了作业{J1, J2, …, Ji} 以其为根的子树的叶节点的总等待时间下界为 a[Jx]在x?i+1时按非递减序排列 b[Jx]在x?i+1时按非递减序排列 * 批处理作业调度问题 堆式分支限界法 优先级测度：bound(V) —— 最小堆 直到某个叶节点Y成为扩展节点 bound(Y)等于Y的总等待时间 堆中其它节点的等待时间都大于等于bound(Y) * 总结 理解分支限界法的剪枝有哪些信誉好的足球投注网站策略 掌握分支限界法的算法框架 队列式(FIFO)分支限界法 优先队列式分支限界法 * 总结 课件下载 /s/15Tf2z http://115.com/lb/5lbajyeclb6 * 欢迎辞 * * * * * * * * * * * * * * * * * * * 智能信息处理研究中心（RCIIP） 智能信息处理研究中心（RCIIP） * 第6章 分支限界法 马志强 * 学习要点 分支限界法的算法框架 队列式（FIFO）分支限界法 优先队列式分支限界法——堆式分支限界法 应用分支限界法解决 单源最短路径问题 装载问题； 0-1背包问题； 旅行售货员问题 批处理作业调度问题 * 分支限界法基础 8-Puzzle问题 输入: 具有8个编号小方块的魔方 输出: 移动序列, 经过这些移动, 魔方达目标状态 1 2 8 4 5 6 7 3 2 1 8 4 5 6 7 3 * 分支限界法基础 队列式（FIFO）分支限界法 广度优先有哪些信誉好的足球投注网站解空间树 2 1 8 4 5 6 7 3 2 1 8 4 5 6 7 3 2 1 8 4 5 6 7 3 2 1 8 4 5 6 7 3 2 1 8 4 5 6 7 3 2 1