《算法设计与分析Chapter6Veron》由会员分享，可在线阅读，更多相关《算法设计与分析Chapter6Veron（48页珍藏版）》请在金锄头文库上搜索。
1、分支限界法,Veron,学习要点,分支限界法的算法框架 队列式（FIFO）分支限界法 优先队列式分支限界法堆式分支限界法 应用分支限界法解决 单源最短路径问题 装载问题； 0-1背包问题； 旅行售货员问题 批处理作业调度问题,分支限界法基础,分支限界法基础,8-Puzzle问题 输入: 具有8个编号小方块的魔方 输出: 移动序列, 经过这些移动, 魔方达目标状态,分支限界法基础,队列式（FIFO）分支限界法 广度优先搜索解空间树,A,B,C,D,E,F,G,A,B,C,D,E,F,G,分支限界法基础,优先队列式分支限界法堆式分支限界 为解空间树中的每个节点指定一个优先级测度函数 每次扩展树中优
2、先级最高的节点 用最大（最小）堆来保存待搜索节点 8-Puzzle问题 测度函数 f (v) =节点v中处于错误位置的方块数 每次扩展 f (v) 值最小的节点,B(3),C(3),D(4),E(4),F(2),G(4),H(1),I(0),J(2),A,A,B,C,D,E,F,G,H,最小堆,分支限界法基础,思想 广度优先或者优先级优先搜索解空间树 实现 每个节点只有一次机会成为扩展节点 一旦节点v成为扩展节点 将 v 的所有孩子加入到队列或者堆中 接着选取队列顶或堆顶节点作为下一个扩展节点 效率 耗时比回溯法少 需要空间比回溯法多,单源最短路径问题,单源最短路径问题,输入 有向带权图G=(
3、V, E) 图中顶点s 输出 s到图中其它顶点的最短路径,单源最短路径问题,解空间树,单源最短路径问题,优先队列式分支限界法 优先级测度：当前路径长度 （最小堆）,单源最短路径问题,剪枝策略 节点b:50控制b:60 将b:60 及其子树剪去 当前扩展节点有儿子v: x 如果x=distv，不扩展v 如果xdistv，扩展v，将v的孩子加入堆中,0-1背包问题,0-1背包问题,输入： , , 和C 输出： (x1, x2, , xn)，xi0, 1满足 优化目标：,0-1背包问题,解空间树,w=16，15，15 v=45，25，25 背包容量30,0-1背包问题,FIFO队列式分支限界法,FI
4、FO队列,A, B,D, E, F,J, K, L, M, N,节点C对应：x1=1, x2=1 节点K对应：x1=0, x2=1, x3=1,0-1背包问题,对于树中的第i层节点V 已经完成了对物品1, i的取舍，剩余物品为i+1, ., n 设已选择的物品价值为p，背包剩余容量为C 限界函数bound(V) = p + q 其中q是针对输入i+1, ., n和C的一般背包问题的最优解 可以按价重比顺序依次向背包中装入物品得到q 以V为根的子树中节点的价值不会超过bound(V),物品按价重比排序为1, , n,0-1背包问题,优先队列式分支限界法 优先级测度：bound(V) 最大堆 直到
5、某个叶节点x成为扩展节点结束 叶节点x的bound(x)等于拿走物品的总价值 堆中剩余节点及其子树的价值不会超过bound(x),0-1背包问题,优先队列式分支限界法 优先级测度：bound(V) 最大堆,w=16，15，15 v=45，25，25 背包容量30,最优解：K (0, 1, 1) 总价值：50,最大堆,A, B,D, B,B, J,E, J, F,K, J, L, F,0-1背包问题,队列（堆）中的每个元素 存储已经获得的部分解 D入队列：存储x1=1, x2=0 K入队列：存储x1=0, x2=1, x3=1 存储已构造的解空间树 B入队列：存储B的父亲为，B是其右孩子 E入队
6、列：存储E的父亲为B，E是其左孩子 K入队列：存储K的父亲为E，K是其左孩子 K对应的解：x3=1, x2=1, x1=0,0-1背包问题,分支限界法优化 限界函数：bound(v) 当前的最优值：bestp 如果bound(v)bestp 剪去v及其子树,装载问题,装载问题,输入 n个集装箱，其中集装箱i的重量为wi 载重量分别为C1和C2的轮船 输出 （是否有）合理的装载方案将所有集装箱装上船 等价于,s.t.,特殊的0-1背包问题：每种物品的价值等于重量,装载问题,解空间树,w=16，15，15 C1载重量30,装载问题,FIFO队列式分支限界法,w=16，15，15 C1载重量30,装
7、载问题,解空间树的第i层节点v 已经完成了对集装箱1, i的取舍，剩余集装箱为i+1, ., n 已经装上第一艘船的集装箱重量和为p 剩余集装箱的重量和为r 限界函数bound(v)=p+r 以v为根的子树中的解的总重量不会超过bound(v),装载问题,优先队列式分支限界法 优先级测度：bound(v) 最大堆 直到某个叶节点x成为扩展节点结束 叶节点x的bound(x)等于拿走物品的总重量 堆中剩余节点及其子树的总重量不会超过bound(x),装载问题,优先队列式分支限界法,w=16，15，15 C1载重量30,最大堆,A, B,A, B,D, B,B, J,E, J, F,K, J, F
8、, L,最优解：K (0, 1, 1) 总重量：30,旅行商问题,旅行商问题,输入 完全无向带权图G=(V, E) |V|=n, |E|=m 对于E中的某条边e，其长度为c(e) 输出 最短的哈密尔顿回路 经过每个节点一次且仅一次的回路,NP难问题,旅行商问题,解空间树,旅行商问题,FIFO队列式分支限界法,旅行商问题,堆式分支限界法1 优先级测度：当前路径长度（最小堆） bestp：当前最优值 剪去当前代价大于等于bestp的节点及其子树,旅行商问题,堆式分支限界法1,最优解：X (acdba) bestp=25,最小堆,F, G, H,I, P, K, R, H,F, K, L, H,I,
9、 J, K, L, H,I, P, K, L, H,I, P, K, H, ,I, K, H,I, H,H,旅行商问题,对于树中的第 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：当前最优值 剪去当前代价大于等于be
10、stp的节点及其子树,旅行商问题,堆式分支限界法2,最小堆,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上的处理时间分别为 ai 和 bi 每个作业必须现由M1处理，再由M2处理 输出 作业调度方案使得总等待时间最小 作业 i在M1和M2上的完成时间分别为 Ai 和 Bi 总等待时间为,批处理作业调度问题,解空间树,批处理作业调度问
11、题,对于树中第 i 层节点V V已经安排了作业J1, J2, , Ji 已安排的作业的等待时间为,批处理作业调度问题,对于树中第 i 层节点V 设以V为根的子树中某个叶节点W的调度为 J1, , Ji ，Ji+1 , , Jn 如果从Ji+1开始机器1没有空闲，则 Ji+1 , , Jn的总等待时间不少于,如果aJx在xi+1时按非递减序排列 S1取得极小值S1 Ji+1 , , Jn的总等待时间 S1,批处理作业调度问题,对于树中第 i 层节点V 设以V为根的子树中某个叶节点W的调度为 J1, , Ji ，Ji+1 , , Jn 如果从Ji+1开始机器2没有空闲，则 Ji+1 , , Jn的
12、总等待时间,如果bJx在xi+1时按非递减序排列 S2取得极小值S2 Ji+1 , , Jn的总等待时间 S2,批处理作业调度问题,对于树中第 i 层节点V V已经安排了作业J1, J2, , Ji 以其为根的子树的叶节点的总等待时间下界为 aJx在xi+1时按非递减序排列 bJx在xi+1时按非递减序排列,批处理作业调度问题,堆式分支限界法 优先级测度：bound(V) 最小堆 直到某个叶节点Y成为扩展节点 bound(Y)等于Y的总等待时间 堆中其它节点的等待时间都大于等于bound(Y),47,总结,理解分支限界法的剪枝搜索策略 掌握分支限界法的算法框架 队列式(FIFO)分支限界法 优先队列式分支限界法,课件下载 http:/ http:/
