【算法】分支定界算法

分支定界算法

概念

分支定界(branch and bound)算法是一种在问题的解空间上搜索问题的解的方法。但与回溯算法不同，分支定界算法采用广度优先或最小耗费优先的方法搜索解空间树。并且，在分支定界算法中，每一个活结点只有一次机会称为扩展结点。

​ 利用分支定界算法对问题的解空间树进行搜索，它的搜索策略是：

1. 产生当前扩展结点的所有孩子结点。
2. 在产生的孩子结点中，抛弃那些不可能产生可行解(或)最优解的结点。
3. 将其余的孩子结点加入活结点表。
4. 从活结点表中选择下一个活结点作为新的扩展结点。

如此循环，直到找到问题的可行解(最优解)或活结点表为空。

从活结点表中选择下一个活结点作为新的扩展结点，根据选择的方式不同，分支定界算法通常可以分为两种形式。

1. FIFO(First In First Out) 分支定界算法：按照先进先出原则选择下一个活结点作为扩展结点，即从活结点表中取出结点的顺序与加入结点的顺序相同。
2. 最小耗费或最大收益分支定界算法：在这种情况下，每个结点都有一个耗费或收益。假如要查找一个具有最小耗费的解，那么要选择的下一个扩展结点就是活结点表中具有最小耗费的活结点，假如要查找一个具有最大收益的解，那么要选择的下一个扩展结点就是活结点表中具有最大收益的活结点。

补充: A *算法（最小消耗优先法搜索解空间树）(未完待续…)