算法设计与分析复习(8)

优先队列式(priority queue)分支限界法

按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。在算法实现时通常用堆来表示。

6.2 单源最短路径

解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。

掌握剪枝策略。

掌握用分支限界法求解单源最短路径的算法思想。

6.3 装载问题

掌握用优先队列式分支限界法求解装载问题：

存储活结点的方式: 最大堆存储活结点表。

活结点x在优先队列中的优先级定义: 从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。

扩展结点的选择：优优先级最大的活结点成为下一个扩展结点。

算法终止条件：子集树中叶结点所相应的载重量与其优先级相同，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法。

掌握MaxLoading方法。

6.5 0-1背包问题

活结点优先队列中结点元素N的优先级由该结点的上界函数Bound计算出的值uprofit给出。

以结点N为根的子树中任一结点的价值不超过N.profit。

掌握MaxKnapsack方法。

8/8