分支限界法-Read.PPT

第6章 分支限界法 理解分支限界法的剪枝搜索策略。 掌握分支限界法的算法框架 （1）队列式(FIFO)分支限界法 （2）优先队列式分支限界法 通过应用范例学习分支限界法的设计策略。 （1）装载问题； （2）布线问题 （3）0-1背包问题； （4）旅行售货员问题 分支限界法基本思想 常见的两种分支限界法（以迷宫老鼠、0-1背包问题和旅行售货员问题为例展开） （1）队列式(FIFO)分支限界法 （2）优先队列式分支限界法 范例学习分支限界法的设计策略 （1）装载问题； （2）布线问题 6.1 分支限界法的基本思想 6.1 分支限界法的基本思想 6.1 分支限界法的基本思想 6.1 分支限界法的基本思想 6.1 分支限界法的基本思想 6.1 分支限界法的基本思想 6.1 分支限界法的基本思想 6.1 分支限界法的基本思想 6.1 分支限界法的基本思想 6.1 分支限界法的基本思想 6.1 分支限界法的基本思想 6.3 装载问题 6.3 装载问题 6.3 装载问题 6.2 单源最短路径问题 6.2 单源最短路径问题 6.2 单源最短路径问题 6.2 单源最短路径问题 6.2 单源最短路径问题 6.3 装载问题 6.3 装载问题 6.3 装载问题 6.3 装载问题 6.3 装载问题 6.3 装载问题 6.3 装载问题 6.3 装载问题 6.4 布线问题 6.4 布线问题 6.4 布线问题 6.5 0-1背包问题 6.5 0-1背包问题 6.5 0-1背包问题 6.6 最大团问题 6.6 最大团问题 6.6 最大团问题 6.6 最大团问题 6.7 旅行售货员问题 6.7 旅行售货员问题 6.7 旅行售货员问题 6.7 旅行售货员问题 6.8 电路板排列问题 6.8 电路板排列问题 6.8 电路板排列问题 6.8 电路板排列问题 6.9 批处理作业调度问题 6.9 批处理作业调度问题 6.9 批处理作业调度问题 6.9 批处理作业调度问题 6.9 批处理作业调度问题 课后作业 习题 6-1，6-2，6-3，6-4，6-5，6-6，6-10 1. 问题描述 有一批共个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集 装箱i的重量为Wi，且 装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。 容易证明：如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。 (1)首先将第一艘轮船尽可能装满； (2)将剩余的集装箱装上第二艘轮船。 2. 队列式分支限界法 在算法的while循环中，首先检测当前扩展结点的左儿子结点是否为可行结点。如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)。2个儿子结点都产生后，当前扩展结点被舍弃。 活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记-1，故在取队首元素时，活结点队列一定不空。当取出的元素是-1时，再判断当前队列是否为空。如果队列非空，则将尾部标记-1加入活结点队列，算法开始处理下一层的活结点。 2. 队列式分支限界法 while (true) { // 检查左儿子结点 if (Ew + w[i] = c) // x[i] = 1 EnQueue(Q, Ew + w[i], bestw, i, n); // 右儿子结点总是可行的 EnQueue(Q, Ew, bestw, i, n); // x[i] = 0 Q.Delete(Ew); // 取下一扩展结点 if (Ew == -1) { // 同层结点尾部 if (Q.IsEmpty()) return bestw; Q.Add(-1); // 同层结点尾部标志 Q.Delete(Ew); // 取下一扩展结点 i++;} // 进入下一层 } } 3. 算法的改进 节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。设bestw是当前最优解；ew是当前扩展结点所相应的重量；r是剩余集装箱的重量。则当ew+r?bestw时，可将其右子树剪去，因为此时若要船装最多集装箱，就应该把此箱装上船。 另外，为了确保右子树成功剪枝，应该在算法每一次进入左子树的时候更新bestw的值。 3. 算法的改进 // 检查左儿子结点 Type wt = Ew + w[i]; // 左儿子结点的重量 i