算法设计与分析_总结0

3）如果某孩子结点的限界函数可能取得的值超出目标函数的界，则将其丢弃；否则，将其加入待处理结点表（以下简称表PT）中；

4）依次从表PT中选取使限界函数的值是极值的结点成为当前扩展结点；

5）重复上述过程，直到找到搜索到叶子结点，如果叶子结点的限界函数的值是极值，则就是问题的最优解，否则，找到其他极值结点重复扩展搜索。 步骤： 确定解空间树 确定限界函数

按广度优先搜索解空间树，计算限界函数的值，填入PT表

从PT表中寻找极值，继续扩展结点，直到找到限界函数值为极值的叶子结点。

了解可以使用分支限界法解决的问题：

TSP问题，多段图的最短路径问题，任务分配问题，批处理作业调度问题，0/1背包问题。 掌握任务分配问题的分支限界法（P195-197），习题9-5 掌握0/1背包问题的分支限界法（P184-185），习题9-6 掌握批处理作业问题的分支限界法（P198-200），习题9-7