xdhu 3
5.3 分支定界
分支定界方法从本质上讲是一类分而治之方法，它与动态
规划方法也十分类似。 给定一个优化问题的实例 I，它保存一些
子实例 I
i
的集合 S，使得：
子实例 I
i
的可行解集的并等于原实例 I 的可行解集。
初始时，S 仅包含实例 I。 然后，对问题的实例 I 进行一个分解
运算，称为分支，得到一组互不相交的子实例 I
i
。我们用一棵判
定树来刻画这个过程，树上的每一个节点都对应一个子实例。
这个方法的关键是，对产生的新的子实例运用回溯技巧，
并保存和更新当前已得到的最优解的信息 ，从而减少需要考虑
和求解的子实例的数目。
评论0