搜狗做题网什么是分支定界法?基本思想是什么?一般用于解决什么问题?
来源：学生作业帮 编辑：搜狗做题网作业帮 分类：数学作业 时间：2024/04/27 22:50:08
什么是分支定界法?基本思想是什么?一般用于解决什么问题?
分支定界 (branch and bound) 算法是一种在问题的解空间树上搜索问题的解的方法.但与回溯算法不同,分支定界算法采用广度优先或最小耗费优先的方法搜索解空间树,并且,在分支定界算法中,每一个活结点只有一次机会成为扩展结点.
利用分支定界算法对问题的解空间树进行搜索,它的搜索策略是：
1 ．产生当前扩展结点的所有子结点；
2 ．在产生的子结点中,抛弃那些不可能产生可行解（或最优解）的结点；
3 ．将其余的子结点加入活结点表；
4 ．从活结点表中选择下一个活结点作为新的扩展结点.
如此循环,直到找到问题的可行解（最优解）或活结点表为空.
分支定界法本质还是一种枚举法,但是是隐枚举法.它是整数规划领域中非常重要的一类算法思想.是很多重要算法的源头.它能解决的实际问题很多,最著名的一个应该就是求解背包问题.
再问： 那么其缺点是什么？
再答： 缺点就是它依然是一种枚举法，从算法上来讲不是一种最好的方法，如果有些问题是NPhard的，分支定界就可能没有办法有效求解了。
利用分支定界算法对问题的解空间树进行搜索,它的搜索策略是：
1 ．产生当前扩展结点的所有子结点；
2 ．在产生的子结点中,抛弃那些不可能产生可行解（或最优解）的结点；
3 ．将其余的子结点加入活结点表；
4 ．从活结点表中选择下一个活结点作为新的扩展结点.
如此循环,直到找到问题的可行解（最优解）或活结点表为空.
分支定界法本质还是一种枚举法,但是是隐枚举法.它是整数规划领域中非常重要的一类算法思想.是很多重要算法的源头.它能解决的实际问题很多,最著名的一个应该就是求解背包问题.
再问： 那么其缺点是什么？
再答： 缺点就是它依然是一种枚举法，从算法上来讲不是一种最好的方法，如果有些问题是NPhard的，分支定界就可能没有办法有效求解了。