问题标签 [branch-and-bound]

我正在研究一个近似匹配问题，其中我在未知图 (A) 和部分图 (B) 中有一组路径，其中 B 是增量生成和增长的。

问题是将路径中的边与图 B 匹配，同时保留路径和图上边的顺序。在我的问题中，图节点是无关紧要的，并且边缘具有执行匹配的非唯一标签。此外，要匹配的路径可以在匹配图 B 时添加/删除任意边。如果我对当前的解决方案不满意，我可以查询一个预言机，这给了我一个更完整（更大）的图（即我的意思是增长）但我想最小化查询，因为图表可能是无限的。

如何概括 3D 单箱包装算法以找到可以包含项目集的最小箱尺寸？

我正在研究分支定界算法，是否有条件让我切分支而不是当前的最佳解决方案？

我希望足够清楚，并感谢任何帮助！

我想实现像这样的 BAB 树结构，

我正在尝试使用 R、matlab 和 CPLEX，但无法弄清楚。

我正在尝试实现分支定界技术，以用轴平行线覆盖点。对于每个子问题，我将我的 LP 解决方案视为 LB，将迭代舍入解决方案视为 UB。首先，我正在考虑一个小数值变量（在应用 LP 之后），对于 0 和 1 值，我正在考虑 SP1 和 SP2 作为我的子问题。对于每个 SP1，我有 UB1 和 LB1，对于每个 SP2，我有前面提到的 UB2 和 LB2。然后我正在检查

i) 如果 (LB1=UB1 或 LB2=UB2) 然后停止

ii) 如果 (UB1 >= LB2) 然后求解 SP2

iii) 如果 (UB2 >= LB1) 然后求解 SP1

我不确定，我正在考虑正确的方法。因为在大多数节点中，ii) 和 iii) 都在发生（尽管一次只有一个“if”正在执行）。我使用正确的方法吗？任何帮助将不胜感激。

谢谢。

我正在研究一个必须用分支定界算法解决的问题。假设我们有 n 个加油站，距离起点不同。站有不同的利润。我们想要最大化利润，但每个站点必须远离至少 K 长度。我用动态算法解决了这个问题，但找不到分支定界算法的解决方案。实际上，我需要一个好的目标函数来确定界限。我尝试了很多功能，但都失败了。谢谢。

示例：n=5 k=10

距离值 l1= 5, l2=15, l3=23, l4=30, l5=38

利润：p1=7, p2=3, p3=10, p4=12, p5=6

在回溯中，我们同时使用 bfs 和 dfs。即使在分支定界中，我们也使用 bfs 和 dfs 来进行最低成本搜索。

所以我们什么时候使用回溯，什么时候使用分支定界

使用分支定界会降低时间复杂度吗？

什么是分支定界中的最低成本搜索？

我正在尝试在 java 中实现分支和绑定搜索算法。我知道它的概念（它是如何工作的），但我不确定如何实现它。

我在谷歌上找到了一些例子，但它们更复杂，我似乎无法理解它们。我想以一种简单的方式实现它。而且它们中的大多数不在java中。

以下是我的搜索开始的相关方法（这只是我的代码的一部分）。我认为我的 for 循环需要进行适当修改以存储前沿节点和成本，然后获取成本最低的节点，然后再次执行搜索，直到找到目标节点并添加累积成本。
所以我猜递归方法最适合这个。但我不确定如何实施。

以下内容没有给我任何编译错误，而是给了我运行时错误为Node1 cannot be cast to java.lang.Comparable. 有人好心研究这个问题吗？几个小时以来我一直在尝试这样做，但似乎找不到任何解决方案。

此外，任何能引导我走上正确道路的小代码都会很有帮助。

以下是存储文件信息的 Node1 类

以下是文件格式（startNode endNode 成本）

[编辑]：

我想实现分支定界搜索，程序要求用户输入startNode，goalNode然后访问Node1类中的数据（存储文件中的数据），然后程序输入search方法（上述方法）传递所有nodes,startNode和length of nodes(size). 如果 startNode 与 node1[].getStartNode 中的任何一个匹配，则它将相应的扩展节点frontierNodes及其相应的成本存储在frontierCosts优先级队列中（以选择最低成本）。然后程序 peeks() 优先级队列并选择成本最低的节点（队列的前面），然后以该特定节点作为 startNode 再次搜索（递归调用上述搜索方法？）并继续搜索。
当程序到达新节点时，每个新节点的成本应该得到到目前为止访问的路径的累积成本，程序应该输出路径和成本。

我正在尝试为分支定界算法实现递归函数。每次递归调用我的算法时，我都会在递归调用中更改我的 lb 和 ub 值。它显示错误UB must be a real valued nx by 1 column vertor error in MATLAB。我的代码附在下面：

它显示ub(round_value)=0和的错误lb(round_value)=1。任何帮助将不胜感激

我们考虑一个简单的图 G =(V; E)。众所周知的路径覆盖问题 ( https://en.wikipedia.org/wiki/Path_cover ) 在哈密顿路径问题是 NP 完全的所有图类上都是 NP 完全的，包括平面图、二分图和弦图。文献中已经为这个问题是多项式的特殊图类提出了许多多项式算法，但是我没有找到任何精确的方法来找到二部图（甚至平面图和弦图）的最小顶点不相交路径覆盖，尤其是分支定界算法。

您是否知道任何确切的方法，特别是分支定界算法，用于解决该问题是 NP-hard 的图类（二分图、平面图和弦图）上的路径覆盖问题？

先感谢您。

我需要用分支定界算法解决 TSP 问题。这是代码。问题是，该代码仅适用于小型实例（即三个城市），但并非每次都有效。

我一直在寻找一些错误，但我找不到任何错误。成本矩阵是我代码中的 macierz，城市数量存储在变量 ileMiast 中。我认为其余的很清楚。不要打扰 sort 函数或 FinalMatrix 数组。只是为了呈现最终的顺序。

提前致谢