分支定界法(branch and bound)是一种求解离散数据组合的最优化问题。该算法执行的效率取决于你所找的问题解空间的上下界，如果找到一个很紧凑的上下界进行剪枝操作，该算法的执行效率会非常高，因此它是最有可能在多项式时间内求解NP问题的算法。
使用分支定界算法的一般步骤为：
构造一棵搜索树，该搜索树指的是所有解空间，因此通过遍历该搜索树可以遍历到所有的解；
构造问题解的上下界，上界一般为之前求出的最优解，下界为无约束条件下当前搜索路径的最优解，上下界的主要作用是对搜索树进行剪枝；
通过回溯法遍历搜索树，并且不断更新上下界，如果当前解的下界已经超过上界，则进行剪枝；
遍历结束时，所求的解为最优解。
接下来通过一个实例来讲解分支定界算法：
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/204705.html原文链接：https://javaforall.net
