什么是分支定界法?基本思想是什么?一般用于解决什么问题?

layman2007 1年前他留下的回答 已收到2个回答

dodo4 网友

该名网友总共回答了20个问题，此问答他的回答如下：采纳率：80%

分支定界 (branch and bound) 算法是一种在问题的解空间树上搜索问题的解的方法.但与回溯算法不同,分支定界算法采用广度优先或最小耗费优先的方法搜索解空间树,并且,在分支定界算法中,每一个活结点只有一次机会成为扩展结点.
利用分支定界算法对问题的解空间树进行搜索,它的搜索策略是：
1 ．产生当前扩展结点的所有子结点；
2 ．在产生的子结点中,抛弃那些不可能产生可行解（或最优解）的结点；
3 ．将其余的子结点加入活结点表；
4 ．从活结点表中选择下一个活结点作为新的扩展结点.
如此循环,直到找到问题的可行解（最优解）或活结点表为空.
分支定界法本质还是一种枚举法,但是是隐枚举法.它是整数规划领域中非常重要的一类算法思想.是很多重要算法的源头.它能解决的实际问题很多,最著名的一个应该就是求解背包问题.

1年前他留下的回答 追问

6

layman2007

那么其缺点是什么？

dodo4

缺点就是它依然是一种枚举法，从算法上来讲不是一种最好的方法，如果有些问题是NPhard的，分支定界就可能没有办法有效求解了。

忧郁的阿飞 网友

该名网友总共回答了8个问题，此问答他的回答如下：

用C#编程通过分支定界法解决背包问题。急急急。 using System; using 问题解决函数 ///

1年前他留下的回答

2

　　以上就是小编为大家介绍的什么是分支定界法?基本思想是什么?一般用于解决什么问题? 的全部内容，如果大家还对相关的内容感兴趣，请持续关注上海建站网！