算法设计-第6章.ppt

第6章 分支限界法 学习要点 理解分支限界法的剪枝有哪些信誉好的足球投注网站策略。 掌握分支限界法的算法框架 （1）队列式(FIFO)分支限界法 （2）优先队列式分支限界法 通过应用范例学习分支限界法的设计策略。 （1）单源最短路径问题 （2）装载问题； （3）0-1背包问题； （5）最大团问题； （6）旅行售货员问题 6.1 分支限界法的基本思想 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 装载问题 应用分支限界法分关键问题 （1）如何确定合适的限界函数； （2）如何组织待处理节点表； （3）如何确定最优解中的各个分量。 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.9 批处理作业调度问题 6.9 批处理作业调度问题 6.9 批处理作业调度问题 6.9 批处理作业调度问题 6.9 批处理作业调度问题 3. 算法的改进 // 检查左儿子结点 Type wt = Ew + w[i]; // 左儿子结点的重量 if (wt = c) { // 可行结点 if (wt bestw) bestw = wt; // 加入活结点队列 if (i n) Q.Add(wt); } 提前更新bestw // 检查右儿子结点 if (Ew + r bestw i n) Q.Add(Ew); // 可能含最 优解 Q.Delete(Ew); // 取下一扩展结点 右儿子剪枝 4. 构造最优解 为了在算法结束后能方便地构造出与最优值相应的最优解，算法必须存储相应子集树中从活结点到根结点的路径。为此目的，可在每个结点处设置指向其父结点的指针，并设置左、右儿子标志。 class QNode {QNode *parent; // 指向父结点的指针 bool LChild; // 左儿子标志 Type weight; // 结点所相应的载重量 找到最优值后，可以根据parent回溯到根节点，找到最优解。 4. 构造最优解 // 构造当前最优解 for (int j = n - 1; j 0; j--) { bestx[j] = bestE-LChild; bestE = bestE-parent; } 5. 优先队列式分支限界法 解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。 优先队列中优先级最大的活结点成为下一个扩展结点。以结点x为根的子树中所有结点相应的路径的载重量不超过它的优先级。子集树中叶结点所相应的载重量与其优先级相同。 在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法。 分支限界法对问题的解空间树中结点的处理是跳跃式的，回溯也不是单纯的沿着双亲结点一层一层地向上回溯，因此当有哪些信誉好的足球投注网站到某个叶子结点且该叶子结点的目标函数值在活节点表中最大时（假设求最大化问题），求得了问题的最优值，但是却无法求得该叶子结点对应的最优解中的各个分量。这个问题可以用下面2种方法之一解决： （1）对每个扩展结点保存该结点到根结点的路径； （2）在有哪些信誉好的足球投注网站过程中构建有哪些信誉好的足球投注网站经过的树结构，在求得最优解时，从叶子结点不断回溯到根结点，以确定最优解中的各个分量。 算法的思想 首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。 在下面描述的优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。 算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。 上界函数 Typep KnapTypew,Typep::Bound