特征选择 分支定界法

Question

如题所述

Answer 1

分支定界 (branch and bound) 算法是一种在问题的解空间树上搜索问题的解的方法.但与回溯算法不同,分支定界算法采用广度优先或最小耗费优先的方法搜索解空间树。

分枝界限法也能够使用在混合整数规划问题上，其为一种系统化的解法，以一般线性规划之单形法解得最佳解后。

将非整数值之决策变量分割成为最接近的两个整数，分列条件，加入原问题中，形成两个子问题(或分枝)分别求解，如此便可求得目标函数值的上限（上界）或下限（下界），从其中寻得最佳解。

分支定界法算法分析：

1、算法优点：可以求得最优解、平均速度快。

因为从最小下界分支，每次算完限界后，把搜索树上当前所有的叶子结点的限界进行比较，找出限界最小的结点，此结点即为下次分支的结点。这种决策的优点是检查子问题较少，能较快的求得最佳解。

2、缺点：要存储很多叶子结点的限界和对应的耗费矩阵。花费很多内存空间。

存在的问题：分支定界法可应用于大量组合优化问题。其关键技术在于各结点权值如何估计，可以说一个分支定界求解方法的效率基本上由值界方法决定，若界估计不好，在极端情况下将与穷举搜索没多大区别。