问题标签 [branch-and-bound]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
optimization - 何时从动态规划(二维表)切换到分支定界算法?
我正在做一个涉及动态编程和分支与界限的背包优化问题。我注意到,当问题的容量和项目变大时,为动态规划算法填充 2D 表将呈指数级变慢。在某些时候我会假设我想根据问题的大小切换算法(因为讲座给出了两种类型的优化)?
我试图谷歌在什么时候(什么大小)我应该从动态编程切换到分支和绑定,但我无法得到我想要的结果。
或者,是否有另一种看待背包问题的方法,我可以将动态编程和分支与界限结合为一个算法,而不是根据问题的大小切换算法?
谢谢。
search - 分支定界与最佳优先搜索之间的差异
我正在研究分支和绑定和最佳优先搜索我的论文工作,但在网上发现了很多关于这两个概念的矛盾。首先,我认为分支和绑定仅修剪以高成本解决方案结尾的分支(使用启发式)并且不优先搜索(在修剪后对树的其余部分执行简单的 DFS 或 BFS)。但是,后来我发现许多资源说 BB 也对状态进行排名,并优先考虑排名较高的节点(优先搜索)。如果是这样,BB和最佳优先搜索之间到底有什么区别?
python - 在算法上比较许多客户的多种价格选择
我们有 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 分配分数并基于此进行过滤来进行手动分析,我对更多的计算解决方案感兴趣。
有什么方法可以推荐吗?
python - 为多个客户寻找最合适的价格
在算法上为许多客户比较多种价格选项的重述,几乎没有太多的麻烦。
我们有 1,000,000 名客户。每种商品的销售成本可以表示为价格 A 或价格 B。
价格 A << 价格 B。
价格 A 和价格 B 彼此之间不是线性的。在某些情况下,B 的价格是其 2 倍,在某些情况下是 100 倍。
A 上所有客户的成本为
实际上,如果 A 上所有客户的平均成本小于 100,则将四舍五入到 100。
B没有这样的限制。
我想在他们的商品上花最少的钱。
如何最大化
我一直认为这是双背包问题的一种形式,但我做错了......
我很可能会在 Python 中解决这个问题,尽管我怀疑这很重要。
我已经通过为 xyz 分配分数并基于此进行过滤来进行手动分析,我对更多的计算解决方案感兴趣。
有什么方法可以推荐吗?
algorithm - Branch and Bound:如何确定下限成本
我想编写一个程序来解决棋盘游戏。在这个游戏中,有两个棋盘。一个是源棋盘 S。另一个是目标棋盘 T。我的目标是移动棋盘 S 中的棋子,使它们看起来与棋盘 T 中的棋子相同,且移动次数最少。每次我只能移动一件物品。此外,我只能将项目移动到相邻的空间(“~”表示空间)。可能有多个“~”。所以我想用分支定界算法来解决这个问题。但是我不知道如何确定下限成本(将当前状态更改为目标状态的最少动作)。
algorithm - 背包分支和绑定
我有以下数据:
容量为 10。如何继续计算节点 0 的上限?我正在计算节点 0 的上限,如下所示:
或者我是否需要按价值/重量的降序对项目进行排序,分别为 12、9、8、5、5?然后计算上限?或者我做得对,没有排序,计算上限并继续下一项?
在没有排序的方法中,我不会在节点 0 处获得最大上限,我认为是这样。
已经感谢您的帮助。
c - C语言追逐游戏
我遇到了一个非常复杂的问题:
在包含一只鸡、一只老鹰和一个院子的MxN场上,鸡试图逃离老鹰(通过进入院子),而老鹰试图抓住鸡。鸡伸到院子里逃跑,老鹰和鸡在同一位置时抓住鸡。鹰一步可以移动一个或两个小方格,鸡可以向任何方向移动一个方格。该程序应显示一条消息,说明鸡是否可以获胜。它应该计算移动,并且在每个步骤中,它应该在输出文件中写入该字段的当前配置,并且它还应该在屏幕上直观地表示它。场地的尺寸、鸡和鹰的位置以及院子的位置都在文件中给出。
我已经通过创建字段(矩阵)解决了这个问题,但我不知道如何解决这个问题。也许回溯是一个想法,但它非常复杂,我无法处理。我想我应该找到一种方法来找出鸡和院子之间的距离,以及老鹰和院子之间的距离,并以某种方式处理它。它必须在 C 中。欢迎任何建议和想法!先感谢您!
ip - 分支定界树中的层数
给定具有 n 个整数变量和 m 个约束的 ILP(整数线性规划)优化,并实现分支定界树以解决典型问题,
- 树需要多少层(树的高度)才能达到全整数最优解?
- 该算法需要多少个分支才能达到全整数最优解?
mapreduce - MapReduce 版本 2 入门
早上好,
我没有成功在 YARN 上找到 mapReduce 示例(即 MapReduce 的第二个版本),始终显示的是 WordCount,它与 MapReduce 的第一个版本上显示的代码完全相同。甚至“Hadoop:权威指南”在 YARN 中也没有代码!
你能提供一个代码来告诉我在以前的版本和最新版本中编写 mapReduce 代码的区别吗?
事实上,我曾尝试在 MR1 上编写分支和绑定代码,但后来我发现 YARN 可以使事情变得更容易,这要归功于 BranchReduce。
任何帮助表示赞赏,在此先感谢
python - Python背包分支和绑定
我花了一周的时间来研究背包问题的分支和绑定代码,并且我查看了许多关于该主题的文章和书籍。但是,当我运行我的代码时,我没有得到我期望的结果。从文本文件接收输入,例如:
其中第一行是容量,随后的每一行都是值/权重对。我使用这个文件得到的结果是“8”而不是“10”(除非我弄错了,所有物品都不适合放在背包里)。这是我的代码:
我的索引关闭了吗?我没有正确遍历树或计算边界吗?