计算机科学中有很多优化问题，其中很多问题都具有有限数量的图或最小生成树中可行的最短路径，可以在多项式时间内解决。通常，这些问题需要所有可能排列的最坏情况。分支定界算法为最佳解决方案创建分支定界。
分支定界算法通过探索整个搜索空间为NP-Hard问题提供最优解。通过探索整个搜索空间，分支定界算法逐步确定可能的候选解。
在本文中，我们将详细讨论分支定界算法。
什么时候应用分支限界算法？
如果给定的问题是离散优化，则使用分支限界方法是合适的。离散优化是指变量属于离散集的问题。此类问题的示例包括0-1整数规划和网络流问题。
当涉及到组合优化问题时，分支定界法也能很好的被应用。优化问题是通过组合优化来优化的，方法是根据其目标函数找到其最大值或最小值。组合优化问题包括布尔可满足性和整数线性规划。
分支定界解的类型
分支和边界问题的解决方案可以用两种方式表示：
可变大小解决方案：使用此解决方案，我们可以找到给定集合的子集，该子集为给定问题提供了优化解决方案。例如，如果我们必须从{A,B,C,D}中选择一个元素组合来优化给定的问题，并且发现A和B一起给出了最佳解决方案，那么解决方案将是{A,B}。
定长解：该解中有0和1，第i位的数字表示是否包含第i个元素，如上例，解为{1,1,0,0}，这里1代表我们选择了第i个位置的元素，0代表我们没有选择第i个位置的元素。
分支定界问题的分类
根据搜索状态空间树的顺序，分支定界法可以分为三种类型。
- FIFO分支定界法
- 后进先出分支限界法
- 最小成本分支定界
1.FIFO分支定界算法
先进先出是一种解决分支定界问题的方法，它使用队列方法创建状态空间树。这种情况下进行的是广度优先搜索，即搜索完某一层的元素，再从上一层的第一个节点的第一个子节点开始搜索下一层的元素。
2.后进先出分支限界法
此问题的后进先出方法使用堆栈来创建状态空间树。当节点被添加到状态空间树时，它们被添加到堆栈中。添加了关卡的所有节点后，我们从堆栈中弹出最顶层的元素并探索它。
3.最小成本分支定界算法
为了探索状态空间树，此方法使用成本函数。前两种方法也计算每个节点的成本函数，但成本未用于进一步探索。
在这种算法中，节点是根据它们的成本进行探索的，节点的成本可以使用问题来定义，并且在给定问题的帮助下，我们可以定义成本函数。一旦定义了成本函数，就可以定义节点的成本。
现在，考虑一个成本已确定的节点。如果此值大于U0，则此节点或其子节点将无法给出解决方案。结果，我们可以杀死这个节点而不探索它的进一步分支。因此，这种方法可以防止不值得的探索，这样会更有效率。
分支定界算法的优点
1.不会探索分支定界算法中的所有节点。因此，分支限界算法的时间复杂度低于其他算法。
2.只要问题很小并且可以在合理的时间内完成分支，算法就会找到最优解。
3.通过使用分支定界算法，可以在最短的时间内找到最优解。
分支定界算法的缺点
1.运行分支定界算法需要很长时间。
2.在最坏的情况下，根据问题的大小，树中的节点数可能太大。
