问题标签 [branch-and-bound]

我正在做一个涉及动态编程和分支与界限的背包优化问题。我注意到，当问题的容量和项目变大时，为动态规划算法填充 2D 表将呈指数级变慢。在某些时候我会假设我想根据问题的大小切换算法（因为讲座给出了两种类型的优化）？

我试图谷歌在什么时候（什么大小）我应该从动态编程切换到分支和绑定，但我无法得到我想要的结果。

或者，是否有另一种看待背包问题的方法，我可以将动态编程和分支与界限结合为一个算法，而不是根据问题的大小切换算法？

谢谢。

我正在研究分支和绑定和最佳优先搜索我的论文工作，但在网上发现了很多关于这两个概念的矛盾。首先，我认为分支和绑定仅修剪以高成本解决方案结尾的分支（使用启发式）并且不优先搜索（在修剪后对树的其余部分执行简单的 DFS 或 BFS）。但是，后来我发现许多资源说 BB 也对状态进行排名，并优先考虑排名较高的节点（优先搜索）。如果是这样，BB和最佳优先搜索之间到底有什么区别？

我们有 1,000,000 名客户。每种商品的销售成本可以表示为价格 A 或价格 B。

价格 A << 价格 B。

价格 A 和价格 B 彼此之间不是线性的。在某些情况下，B 的价格是其 2 倍，在某些情况下是 100 倍。

A 上所有客户的成本为

min( (sum(A)/count(A)) , 100 ) * count(A) 实际上，如果 A 上所有客户的平均成本小于 100，则将四舍五入为 100。

B没有这样的限制。

我想在他们的商品上花最少的钱。

如何最大化

cost=min( (sum(A)/count(A)) , 100 ) * count(A) + sum(B) 我一直认为这是双背包问题的一种形式，但我做错了。 ..

我很可能会在 Python 中解决这个问题，尽管我怀疑这很重要。

我已经通过为 xyz 分配分数并基于此进行过滤来进行手动分析，我对更多的计算解决方案感兴趣。

有什么方法可以推荐吗？

在算法上为许多客户比较多种价格选项的重述，几乎没有太多的麻烦。

我们有 1,000,000 名客户。每种商品的销售成本可以表示为价格 A 或价格 B。

价格 A << 价格 B。

价格 A 和价格 B 彼此之间不是线性的。在某些情况下，B 的价格是其 2 倍，在某些情况下是 100 倍。

A 上所有客户的成本为

实际上，如果 A 上所有客户的平均成本小于 100，则将四舍五入到 100。

B没有这样的限制。

我想在他们的商品上花最少的钱。

如何最大化

我一直认为这是双背包问题的一种形式，但我做错了......

我很可能会在 Python 中解决这个问题，尽管我怀疑这很重要。

我已经通过为 xyz 分配分数并基于此进行过滤来进行手动分析，我对更多的计算解决方案感兴趣。

有什么方法可以推荐吗？

我想编写一个程序来解决棋盘游戏。在这个游戏中，有两个棋盘。一个是源棋盘 S。另一个是目标棋盘 T。我的目标是移动棋盘 S 中的棋子，使它们看起来与棋盘 T 中的棋子相同，且移动次数最少。每次我只能移动一件物品。此外，我只能将项目移动到相邻的空间（“~”表示空间）。可能有多个“~”。所以我想用分支定界算法来解决这个问题。但是我不知道如何确定下限成本（将当前状态更改为目标状态的最少动作）。

我有以下数据：

容量为 10。如何继续计算节点 0 的上限？我正在计算节点 0 的上限，如下所示：

或者我是否需要按价值/重量的降序对项目进行排序，分别为 12、9、8、5、5？然后计算上限？或者我做得对，没有排序，计算上限并继续下一项？

在没有排序的方法中，我不会在节点 0 处获得最大上限，我认为是这样。

已经感谢您的帮助。

我遇到了一个非常复杂的问题：

在包含一只鸡、一只老鹰和一个院子的MxN场上，鸡试图逃离老鹰（通过进入院子），而老鹰试图抓住鸡。鸡伸到院子里逃跑，老鹰和鸡在同一位置时抓住鸡。鹰一步可以移动一个或两个小方格，鸡可以向任何方向移动一个方格。该程序应显示一条消息，说明鸡是否可以获胜。它应该计算移动，并且在每个步骤中，它应该在输出文件中写入该字段的当前配置，并且它还应该在屏幕上直观地表示它。场地的尺寸、鸡和鹰的位置以及院子的位置都在文件中给出。

我已经通过创建字段（矩阵）解决了这个问题，但我不知道如何解决这个问题。也许回溯是一个想法，但它非常复杂，我无法处理。我想我应该找到一种方法来找出鸡和院子之间的距离，以及老鹰和院子之间的距离，并以某种方式处理它。它必须在 C 中。欢迎任何建议和想法！先感谢您！

给定具有 n 个整数变量和 m 个约束的 ILP（整数线性规划）优化，并实现分支定界树以解决典型问题，

1. 树需要多少层（树的高度）才能达到全整数最优解？
2. 该算法需要多少个分支才能达到全整数最优解？

早上好，

我没有成功在 YARN 上找到 mapReduce 示例（即 MapReduce 的第二个版本），始终显示的是 WordCount，它与 MapReduce 的第一个版本上显示的代码完全相同。甚至“Hadoop：权威指南”在 YARN 中也没有代码！

你能提供一个代码来告诉我在以前的版本和最新版本中编写 mapReduce 代码的区别吗？

事实上，我曾尝试在 MR1 上编写分支和绑定代码，但后来我发现 YARN 可以使事情变得更容易，这要归功于 BranchReduce。

任何帮助表示赞赏，在此先感谢

我花了一周的时间来研究背包问题的分支和绑定代码，并且我查看了许多关于该主题的文章和书籍。但是，当我运行我的代码时，我没有得到我期望的结果。从文本文件接收输入，例如：

其中第一行是容量，随后的每一行都是值/权重对。我使用这个文件得到的结果是“8”而不是“10”（除非我弄错了，所有物品都不适合放在背包里）。这是我的代码：

我的索引关闭了吗？我没有正确遍历树或计算边界吗？