算法设计的与分析(第六章).pptVIP

* 队列式分支限界法 while (true) { if (ew + w[i] = c) enQueue(ew + w[i], i); // 检查左儿子结点 enQueue(ew, i); //右儿子结点总是可行的 ew = ((Integer) queue.remove()).intValue(); // 取下一扩展结点 if (ew == -1) { if (queue.isEmpty()) return bestw; queue.put(new Integer(-1)); // 同层结点尾部标志 ew = ((Integer) queue.remove()).intValue(); // 取下一扩展结点 i++; // 进入下一层 } } * 算法的改进 节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。设bestw是当前最优解；ew是当前扩展结点所相应的重量；r是剩余集装箱的重量。则当ew+r?bestw时，可将其右子树剪去，因为此时若要船装最多集装箱，就应该把此箱装上船。 另外，为了确保右子树成功剪枝，应该在算法每一次进入左子树的时候更新bestw的值。 * 算法的改进 // 检查左儿子结点 int wt = ew + w[i]; if (wt = c) { // 可行结点 if (wt bestw) bestw = wt; // 加入活结点队列 if (i n) queue.put(new Integer(wt)); } 提前更新bestw // 检查右儿子结点 if (ew + r bestw i n) // 可能含最优解 queue.put(new Integer(ew)); ew=((Integer)queue.remove()) .intValue(); // 取下一扩展结点 右儿子剪枝 * 构造最优解 为了在算法结束后能方便地构造出与最优值相应的最优解，算法必须存储相应子集树中从活结点到根结点的路径。为此目的，可在每个结点处设置指向其父结点的指针，并设置左、右儿子标志。 private static class QNode { QNode parent; // 父结点 boolean leftChild; // 左儿子标志 int weight; // 结点所相应的载重量 * 构造最优解 找到最优值后，可以根据parent回溯到根节点，找到最优解。 // 构造当前最优解 for (int j = n; j 0; j--) { bestx[j] = (e.leftChild) ? 1 : 0; e = e.parent; } * 优先队列式分支限界法 解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。 优先队列中优先级最大的活结点成为下一个扩展结点。以结点x为根的子树中所有结点相应的路径的载重量不超过它的优先级。子集树中叶结点所相应的载重量与其优先级相同。 在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法。 * 0-1背包问题 算法的思想 首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。 在下面描述的优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。