第6讲 分支限界法.ppt

第6章 分枝-限界法 学习要点 理解分支限界法的剪枝有哪些信誉好的足球投注网站策略。 掌握分支限界法的算法框架 （1）队列式(FIFO)分支限界法 （2）优先队列式分支限界法 通过应用范例学习分支限界法的设计策略。 （1）单源最短路径问题 （2）装载问题； （3）布线问题 （4）0-1背包问题； （5）最大团问题； （6）旅行售货员问题 （7）电路板排列问题 （8）批处理作业调度问题 堆 ( Heap ) 例1： 例1： 例1： 例2： 例2： 例2： 6.2 单源最短路径问题 while (true) {//有哪些信誉好的足球投注网站问题的解空间 for (int j = 1; j = n; j++) if ((a[enode.i][j]Float.MAX_VALUE) (enode.length+a[enode.i][j]dist[j])) { // 顶点i到顶点j可达，且满足控制约束 dist[j]= enode.length+c[enode.i][j]; p [j]= enode.i; // 加入活结点优先队列 HeapNode node=new HeapNode(j,dist[j]); heap.put(node); } // 取下一扩展结点 if ( heap.isEmpty( ) ) break; else enode=(HeapNode)heap.removeMin(); } } 6.3 装载问题 6.3 装载问题 6.3 装载问题 6.3 装载问题 6.5 0-1背包问题 public class BBTSP { private static class HeapNode implements Comparable { float lcost , //子树费用的下界 rcost , //x[s:n-1]中顶点最小出边费用和 cc; //当前费用 int s;//根结点到当前结点的路径为x[0:s] int [] x;//需要进一步有哪些信誉好的足球投注网站的顶点是x[s+1:n-1] …… static float [][]a;//图G的邻接矩阵 } 6.9 批处理作业调度问题 6.9 批处理作业调度问题 6.10 优先队列式分枝限界法的特性 成本函数 成本函数 成本函数 6.10 优先队列式分枝限界法的特性 6.10 优先队列式分枝限界法的特性 6.10 优先队列式分枝限界法的特性 6.10 优先队列式分枝限界法的特性 6.10 优先队列式分枝限界法的特性 6.10 优先队列式分枝限界法的特性 6.10 优先队列式分枝限界法的特性 分枝限界法和回溯法的特性 小结 分枝限界法的求解目标：满足约束条件的一个解（最优解） 队列式分枝限界法：FIFO，LIFO 优先队列式分枝限界法 优先队列式分枝限界法与队列式分枝限界法(FIFO，LIFO)的关系。 效率分析。 小结 应用： （1）单源最短路径问题 （2）装载问题； （3）布线问题 （4）0-1背包问题； （5）最大团问题； （6）旅行售货员问题 （7）电路板排列问题 （8）批处理作业调度问题 实例： 0-1背包问题 旅行商问题 电路板排列问题 批处理作业调度 1, s=0 sf2=0 bb=0 根 0,1,2;f1=0,f2=0 2, s=1 sf2=3, bb=19 0,1,2;f1=2,f2=3 3, s=1 sf2=4, bb=20 1,0,2;f1=3,f2=4 1, s=0 sf2=0 bb=0 根 0,1,2;f1=0,f2=0 4, s=1 sf2=5, bb=19 2,1,0;f1=2,f2=5 2, s=1 sf2=3, bb=19 0,1,2;f1=2,f2=3 3, s=1 sf2=4, bb=20 1,0,2;f1=3,f2=4 9, s=2 X sf2=5, bb=19 2,1,0;f1=2,f2=5 10, s=2 X sf2=5, bb=19 2,0,1;f1=2,f2=5 5, s=2 sf2=3, bb=19 0,1,2;f1=2,f2=3 6, s=2 sf2=3, bb=18 0,2,1;f1=2,f2=3 7, s=3 sf2=3, bb=18 解 0,2,1;f