问题标签 [branch-and-bound]

有人可以为我解释一下分支定界搜索技术吗？我需要使用分支定界搜索算法从任何随机图的任何开始节点到结束节点找到一条成本最小的路径。

I'm trying to solve the TSP with Branch and bound algorithm.

I must build a matrix with costs but I have this problem: I have city with coordinates x and y.

The cost of traveling is ceil(ceil(sqrt((x1-x2)^2+(y1-y2)^2))/v) + days spent in the city. V is speed.

Days spent in the city depends from day when w comes to the city. For example if we arrived on Monday(t1) to city 1, we stay for 9 days but if we arrived on Tuesday, then we stay in the city for 4 days.

How can I solve this problem using branch and bound algorithm?

我想知道是否有用于 TSP 的分支定界算法的有用 Java 实现，或者通常包含用于 TSP 的 BnB 的 OR 框架。

谢谢你的帮助！

马可

我有一个应该用分支定界算法解决的问题，但是我很难思考如何解决它。我不知道如何启动分支定界算法。

这是问题所在：

汽车有最大的重量和体积容量，我需要用包裹装满汽车。这些包裹具有确定的重要性、重量和体积值。目标是在不超过汽车重量和体积限制的情况下，将具有最高重要性的包装组合放入汽车中。

我一直在研究这个问题，并且可以得到一些结果，但是在这里实现分支和绑定方法时遇到了麻烦。
你们能帮帮我吗？

建造仓库

描述

中了彩票后，您决定购买几辆卡车（或卡车）。您的目标是将货物运送到科英布拉的所有超市。但是现在你必须建立仓库来储存货物，你必须考虑可能的位置。理想情况下，仓库应靠近超市，以降低运输成本。然而，你不可能把所有的钱都花在到处建仓库上，所以你必须做出一个聪明的决定：考虑到在每个可能的地点建造每个仓库的固定成本以及未来 5 年从每个地点为每个超市提供服务的运输成本，您想知道应该在哪里建造仓库，以便在该期间内的总成本（运输和固定成本）最小。注意至少要建一个仓库。此外，总运输成本的计算必须考虑到必须为所有超市提供服务。

输入

每个测试用例都包含有关在给定地点建造仓库的固定成本以及与每个地点和超市相关的运输成本的信息。每个测试用例的第一行给出了可以建造仓库的可能位置的数量（n<51）和超市的数量（m<16）。然后，以下 n 行中的每一行给出了在该位置建造仓库的成本以及与从该位置供应 m 个超市中的每一个相关的运输成本。

输出

输出是建造和运营仓库的最低总成本（整数）。例子

输入：

4 5

10 8 6 10 8 10

9 1 2 10 4 8

10 6 4 2 1 5

1 10 4 6 9 3

输出：

26

http://pastebin.com/apXCMdxy

我正在研究旅行商问题的分支定界算法，但遇到了一点麻烦。我正在使用一个非常标准的队列，其中的节点代表顶点（路径）的子集。我很确定我已经解决了整个问题，但目前我有公共类 Queue，在它下面有私有类 Node，它的所有属性：当前路径、下限等。

但是，在我的主程序中，我初始化了节点队列并创建了两个起始节点，但出现错误“节点无法解析为类型”。我认为这是因为它在 Queue 类中并且主程序无法访问，但是当我将它移出时，我在连接到节点的项目上的其他任何地方都会出错。

我真的希望这是有道理的，我不确定如何解释它，但其他一切似乎都很好。这是我的代码片段以进行澄清：

那是我声明 Node 类的地方，也是我在主程序中实际使用它的地方：

我在为 b&b 背包问题实现这个（可怕的）伪 Java 代码时头疼（我想知道：为什么人们会这样做？）。到目前为止，这是我的实现，最多输出 80 个（对于教科书样本上的项目，它应该打印 90 个）。在将元素传递给算法之前，我创建了一个比较器（在 LinkedList 上）以按 Pi/Wi 对元素进行排序，但在此输入上已经预先排序。我现在正在调试（并更新发布的代码），因为我猜这是一个数组索引问题......还是边界函数有错误？

输入：

我正在使用 Haskell 从生物信息学领域实现一个主题查找算法。除了说它是分支定界中值字符串搜索之外，我不会详细介绍该算法。我曾计划通过实现并发方法（以及后来的 STM 方法）来使我的实现更有趣，以便获得多核加速但在使用以下标志编译之后

并打印配置文件我看到了一些有趣的东西（也许很明显）：

很明显，无需接近多核编程就可以获得显着的加速（尽管这已经完成，我只需要找到一些好的测试数据并为此整理出标准）。

无论如何，这两个功能都是纯功能性的，绝不是并发的。他们也在做一些非常简单的事情，所以我很惊讶他们花了这么多时间。这是他们的代码：

请注意，在 hammingDistance 的两个参数中，我实际上可以假设 xs 将是 x 长并且 ys 将小于或等于它，如果这为改进提供了空间。

如您所见，hammingDistance 计算两个基序（核苷酸列表）之间的汉明距离。主题函数接受一个数字和一个列表并返回该长度的所有子字符串，例如：

由于所涉及的算法过程非常简单，我想不出进一步优化它的方法。然而，我确实有两个关于我应该去哪里的猜测：

1. HammingDistance：我使用的数据类型（NukeTides 和 []）很慢/很笨拙。这只是一个猜测，因为我不熟悉他们的实现，但我认为定义我自己的数据类型，虽然更易读，但可能涉及比我想要的更多的开销。模式匹配对我来说也是陌生的，我不知道这是微不足道的还是昂贵的。
2. 主题：如果我没看错的话，70% 的内存分配是由主题完成的，我认为有时必须进行垃圾收集。再次使用通用列表可能会减慢我或列表理解的速度，因为我非常不清楚这样做的成本。

有人对这里的常规程序有什么建议吗？如果数据类型是问题所在，那么数组会是正确的答案吗？（我听说它们是装在盒子里的）

谢谢您的帮助。

编辑：我突然想到，如果我描述调用这两个函数的方式可能会很有用：

此函数是另一个函数的结果，并在树中的节点周围传递。在树中的每个节点上，对核苷酸（长度 <= n，即如果 == n 则它是叶节点）进行评估，使用 totalDistance 对节点进行评分。从那时起，它就是典型的分支定界算法。

编辑：约翰要求我打印出我所做的改变，这实际上消除了图案的成本：

我在原始帖子中没有说清楚，但 scoreFunction 只调用一次，结果在树遍历/分支中传递并绑定并用于评估节点。回想起来，在每一步重新计算图案并不是我做过的最聪明的事情之一。

我正在寻找一种能够以最有效的方式解决我的问题的算法。

问题描述：

我有一个项目列表（只允许使用正整数）和固定数量的相同容量的垃圾箱。到目前为止，我考虑过分支定界算法，但我不太确定它是否是这种情况下的最佳方法。

例子：

给定一个项目列表：

和三个容量为 9 的箱子，我需要将它们打包：（物品的顺序无关紧要）

我认为这是装箱问题的一个变体（我知道这是 NP 完全问题），但由于我并没有试图最小化使用的箱数，我想知道是否有更好的解决方案。

在我的学士论文中，我需要实现一个分支定界算法来证明存储管理分配策略的有效性。我不是程序员，我对 C 有一些了解，但我可以意识到这个算法不能马上写出来，因为它是一种人工智能，需要做出决定。

我想知道解决这个问题的方法是什么。

我有迭代 1 的工作代码，以便它计算每个节点所需的一切，但我将数据存储在一个简单的结构数组中，表示级别 1 的节点。问题是现在，如果 x 是级别节点，我必须分别从节点 1,2,3,... 开始创建 x-1,x-2,x-3,.... 新节点

所以我问是否有人会这么好心让我以正确的方式解决问题。

这是我到目前为止的代码，用于第一次迭代，抱歉，注释是意大利语：