【精选】算法设计与分析（第六章分支限界法）

前言

总结算法设计与分析课程期末必记知识点。

第六章分支限界法

1、分支限界法与回溯法的区别

求解目标不同，分支限界法是找出满足约束条件的一个解。回溯法是找出满足约束条件的所有解。

2、如何组织活结点表

根据选择下一个扩展结点的方式来组织活结点表，不同的活结点表对应不同的分枝搜索方式，常见的有队列式分枝限界法和优先队列式分枝限界法两种

3、采用分枝限界法求解的3个关键问题

(1)如何确定合适的限界函数 (2)如何组织待处理结点的活结点表。 (3)如何确定解向量的各个分量

4、分支限界法优缺点

归纳起来，与回溯法相比，分枝限界法算法的优点是可以更快地找到一个解或者最优解，其缺点是要存储结点的限界值等信息，占用的内存空间较多。另外，求解效率基本上由限界函数决定，若限界估计不好，在极端情况下将与穷举搜索没多大区别。

结语

第六章分支限界法结束，下一章——第七章贪心法