问题标签 [branch-and-bound]

我知道 DP 为许多 NP 完全问题（如 TSP）提供了更好的性能。虽然所需的空间很大，但它很好地降低了复杂性。

但是与蛮力搜索相比，我无法理解分支定界和回溯的效率。

在最坏的情况下，蛮力是否等于 b&b 或回溯？

我正在尝试使用分支和边界来实现这个背包问题的 C++ 实现。这个网站上有一个Java版本：Implementing branch and bound for knapsack

我试图让我的 C++ 版本打印出它应该打印出的 90，但它没有这样做，而是打印出 5。

有谁知道问题可能出在哪里和什么地方？

CLRS 似乎没有涵盖回溯/分支绑定。我在网上尝试了几个资源，虽然我得到了这些背后的想法，但我无法为背包问题编写代码。所以，我想要的东西，可能是，解决一个问题，用这 3 种方法解决它，至少给出伪代码。或者任何你喜欢的资源都会有帮助。

在http://penguin.ewu.edu/cscd501/Wint-2011/BranchAndBound/Knap01BnB.txt的main()函数中

使用上面的代码，我尝试运行 Bandp.txt，它没有问题。我在尝试使用十进制小数值运行 txt 文件时遇到问题：

我需要更改代码的哪一部分以便可以显示十进制值并且它们不会显示输入不匹配。

我的txt文件如下图：data.txt

100 20
12.64 8.43 4.21 8.45 17.56 8.31 13.85 12.39 19.32 14.29 4.03 17.14 8.24 1.24 0.79 5.59 6.6 12.18 12.24 1.67 6.45 19.43 9.88 8.75 18.37 15.64 8.24 5.55 3.6 6.4 6.69 18.44 3.07 0.71 11.28 10.25 14.26 12.14 0.71 2.37

这是 BandP.txt 中的值：

15 7 5 25 11 45 3 12 2 7 2 6 7 10 5 4

我读过不止一本书（包括 Wolsey），在实现分支定界算法时，不需要存储整个树，只需要存储活动节点的列表（据我所知，叶节点）。

问题是，如果我没有每个祖先的边界，我无法理解如何在分支后计算出新的边界。

对此进行一些澄清将不胜感激。

我只是想知道 TSP 的所有算法是否都会给出相同的最佳路线？我认为会是这种情况，但我实现了分支和绑定以及 A*，它们都对相同的输入给出了非常不同的结果，我只是想知道这是否正常？

分支定界的一般描述

来自维基百科的分支和绑定：

此步骤称为修剪，通常通过维护一个全局变量m（在树的所有节点之间共享）来实现，该变量记录迄今为止检查的所有子区域中看到的最小上限。任何下界大于m的节点都可以被丢弃。

实际例子：旅行推销员问题

旅行商问题的一个简单解决方案是保留一个变量，例如best，它表示迄今为止发现的最短哈密顿回路（上限）。

每次我们考虑潜在的新电路中的新步骤时，我们都会计算当前点的路径成本，例如cost，这是该路径成本的下限，并将其与best变量进行比较。如果在任何时候cost >= best，我们都不需要考虑这条路径；我们可能会修剪以该子路径开头的所有潜在路径。

这在诸如 C 之类的过程语言中实现起来并不难，我们可以在其中创建一个在函数范围内的变量。例如，

我的实际问题

我不清楚这种算法将如何纯粹从功能上实现。有没有办法模拟维基百科定义中提到的全局变量m ？

我知道在 Lisp 中拥有一个全局变量很简单，但是在更纯粹的函数式语言（如 Haskell）中这是否可能？

所以我认为我在正确的轨道上使用分支定界方法来解决我对旅行问题的启发式解决方案，但是，我的“最小”功能出现分段错误，但我仍然很难理解围绕算法。任何解决此问题的帮助将不胜感激。基本上该功能的要求（因为我的主要功能看起来很有趣）是程序应该占用多达 150 个城市，如果它在 60 秒内读取，我会得到奖励积分（这意味着我不会失败）输入文件会看起来like（例如）： c 1 c 2 a 1 2 300 其中“c”表示“创建城市”，“a”表示“添加边界”。这就是为什么我的程序是这样设置的。

使用分支定界算法，我已经评估了一组给定项目的最佳利润，但现在我希望找出哪些项目包含在这个最优解决方案中。我正在评估最佳背包的利润值如下（改编自此处）：

那么，我怎样才能得到构成最优解的项目，而不仅仅是利润呢？

我只知道通过分支定界，可以减少获得解决方案的过程，但这仅有助于具有解决方案空间树的问题。