基本算法——分支定界法

大家好，欢迎来到IT知识分享网。

“分枝界限法”把问题的可行解展开如树的分枝，再经由各个分枝中寻找最佳解。

采用广度优先产生状态空间树的结点，并使用剪枝函数的方法称为分枝限界法。
所谓“
分支”是采用广度优先的策略，依次生成扩展结点的所有分支（即：儿子结点）。
所谓“
限界”是在结点扩展过程中，计算结点的上界（或下界），边搜索边减掉搜索树的某些分支，从而提高搜索效率。

分支定界法设计思想：

• 先确定一个合理的定界函数
• 由定界函数确定目标函数的界【down，up】
• 仍以穷举法的解空间树为基础，但以广度优先的原理搜索该节点的所有孩子节点，分别估算这些孩子节点的目标函数的可能取值决定取舍
• 如果某孩子节点的目标函数可能取值超出目标函数的界，则将其丢弃，因为从这个节点生成的解不会比目前已经得到的解更好；否则，将其加入待处理节点表(PT表，简称活节点表）
• 一次从PT表中选取使目标函数取极值的节点成为当前扩展的节点，重复上述过程，直到找到最优解。

目标函数的界【down,up】的确定：

• 对最大化问题

up由定界函数确定，down由眸子启发方式得到，如贪心算法

• 对最小化问题

donw由定界函数得到，up由某种启发方式得到，如贪心算法

分支定界法复杂性：

• 一个更好的定界函数，通常需要花费更多的时间计算相应的目标函数值，而且对于具体的问题实例，通常需要进行大量的实验，才能确定一个好的定界函数；
• 由于分支定界法对解空间树中节点的处理是跳跃式的，因此，在搜索到某个叶子节点得到最优解时，为了从该叶子节点求出对应的最优解中的各个分量，需要对每个扩展节点保存该节点到根节点的路径
• 算法需要维护一个待处理节点PT表，并且需要在PT表中快速查找取得极值的节点，等等。这都需要较大的存储空间，在最坏的情况下，分支定界法需要的空间复杂性是指数级的。