第6章_分支限界法选读.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 旅行售货员问题 堆式分支限界法1 优先级测度：当前路径长度（最小堆） bestp：当前最优值 剪去当前代价大于等于bestp的节点及其子树 * 旅行售货员问题 实例——优先队列式(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 * 旅行售货员问题 对于树中的第 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 1 C 2 D H 2 N 4 I 4 E J 2 P 3 K 3 3 4 1 3 4 2 30 6 10 5 4 20 C,D,E C,D,J,K B C,K C,J,K,H,I C,J,K,I * 批处理作业调度问题（回溯法） 输入 n个作业{1, …, n} 两台机器（M1和M2） 作业 i 在M1和M2上的处理时间分别为 a[i] 和 b[i] 每个作业必须现由M1处理，再由M2处理 输出 作业调度方案使得总等待时间最小 作业 i在M1和M2上的完成时间分别为 A[i] 和 B[i] 总等待时间为 * 批处理作业调度问题（回溯法） 可能的调度方案 123，132，213， 231，312，321 最佳方案是132（总等待时间：18） 作业 a[i] b[i] Job 1 2 1 Job 2 3 1 Job 3 2 3 M1 M2 Job 1 Job 1 B[1]=3 Job 3 Job 3 B[3]=7 Job 2 Job 2 B[2]=8 A[1]=2 A[3]=4 A[2]=7 * 批处理作业调度问题（回溯法） 计算调度{J1, J2, …, Jn}的等待时间 计算B[Ji] 计算A[Ji]=A[Ji-1] + a[Ji] 比较A[Ji]和B[Ji－1] B[Ji]＝较大者 + b[Ji] * 批处理作业调度问题（回溯法） 解空间树 排列树 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 * 批处理作业调度问题（回溯法） 回溯法（有哪些信誉好的足球投注网站排列树） 初始时：x[n]=（1,2,3,…,n） void Backtrack(int t){ if (tn) 输出x； else for(i=t; i=n; i++){ Swap(x[t], x[i]); if (Bound(t)) //如果当前的部分解可行 且 可能产生最优解 Backtrack(t+1) ； Swap(x[t], x[i]); } } 时间复杂性：O(n!) 空间复杂性：O(n) * 批处理作业调度问题（回溯法） 剪枝 限界函数 Bound(t)： * 批处理作业调度问题 对于树中第 i 层节点V V已经安排了作业{J1, J2, …, Ji} 已安排的作业的等待时间为 计算B[Ji]方法 计算A[Ji]=A[Ji-1] + a[Ji] 比较A[Ji]和B[Ji－1] B[Ji]＝较大者 + b[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 , …