10

我已经获得了一个证据，该证据会诋毁关于 0/1 背包问题的普遍看法，我真的很难说服自己我是对的，因为我找不到任何可以支持我的主张的东西，所以我将首先陈述我的主张，然后证明它们，我将感谢任何人试图进一步证实我的主张或反驳它们。任何合作表示赞赏。

断言：

  1. 用于解决背包问题的 bnb（分支定界）算法的大小与K（背包容量）无关。
  2. bnb 树完整空间的大小始终为 O(NK)，其中 N 是项目数，而不是O(2^N)
  3. bnb 算法在时间和空间上总是优于标准的动态规划方法。

前提假设：bnb算法容易出现无效节点（如果剩余容量小于当前item的权重，我们不打算对其进行扩展。另外，bnb算法以深度优先的方式完成。

马虎证明：

这是解决背包问题的递归公式：

值（i，k）=最大值（值（i-1，k），值（n-1，k-weight（i））+值（i）

但是如果 k < weight(i): Value(i,k) = Value(i-1,k)

现在想象这个例子：

K = 9
N = 3   
V W:   
5 4   
6 5   
3 2

现在这里是这个问题的动态解决方案和表格：

在此处输入图像描述

现在想象一下，不管这是否是一个好主意，我们只想通过记忆而不是表格使用递归公式来执行此操作，例如使用地图/字典或简单数组来存储访问的单元格。为了使用记忆化解决这个问题，我们应该解决表示的单元格：

在此处输入图像描述

现在这与我们使用 bnb 方法获得的树完全一样：

在此处输入图像描述

现在是草率的证明：

  1. Memoization 和 bnb 树的节点数相同
  2. 记忆节点取决于表大小
  3. 表大小取决于 N 和 K
  4. 因此bnb 不独立于 K
  5. 记忆空间以 NK 为界，即 O(NK)
  6. 因此bnb 树的完整空间（或者如果我们以广度优先的方式进行 bnb 的空间）总是 O(NK) 而不是 O(N^2) 因为整棵树不会被构建，它会是喜欢妈妈化。
  7. 记忆化比标准的动态规划有更好的空间。
  8. bnb 比动态规划有更好的空间（即使在广度上先做）
  9. 没有松弛（并且只是消除不可行节点）的简单 bnb 将比 memoization 有更好的时间（memoization 必须在查找表中搜索，即使查找可以忽略不计，它们仍然是相同的。）
  10. 如果我们忽略 memoization 的查找搜索，它比动态的要好。
  11. 因此，bnb 算法在时间和空间上总是优于动态算法。

问题：

如果无论如何我的证明是正确的，就会出现一些有趣的问题：

  1. 为什么要为动态规划而烦恼？根据我的经验，你可以在 dp knapsack 中做的最好的事情是拥有最后两列，如果你从下到上填充它，你可以将它进一步改进为一列，它会有 O(K) 空间但仍然不能（如果上述断言是正确的）击败 bnb 方法。
  2. 如果我们将它与松弛修剪（关于时间）相结合，我们还能说 bnb 更好吗？

ps：对不起，长篇大论！

编辑：

由于其中两个答案都集中在记忆上，我只想澄清一下我根本不关注这个！我只是使用记忆作为一种技术来证明我的断言。我的主要关注点是分支定界技术与动态编程，这是另一个问题的完整示例，由 bnb + 松弛解决（来源：Coursera - 离散优化）：

在此处输入图像描述

4

3 回答 3

6

首先，既然你是在应用记忆，你还在做DP。这基本上就是DP的定义：递归+记忆。这也很好。如果没有记忆，您的计算成本将会爆炸。试想一下，如果两个项目的权重为 2，第三个和第四个的权重为 1。它们都在树中的同一个节点处结束，您将不得不进行多次计算，最终将得到指数运行时间.

主要区别在于计算顺序。计算整个矩阵的方式称为“自下而上 DP”，因为您从 (0,0) 开始并自己向上工作。您的方式（树方法）称为“自上而下的 DP”，因为您从目标开始并沿着树向下工作。但他们都使用动态编程。

现在回答你的问题：

你高估了你真正节省了多少。N = 3是一个很小的例子。我很快尝试了一个更大的例子，使用N = 20, K=63（仍然很小）和随机值和随机权重。这是我生成的第一张图片：

values: [4, 10, 9, 1, 1, 2, 1, 2, 6, 4, 8, 9, 8, 2, 8, 8, 4, 10, 2, 6]
weights: [6, 4, 1, 10, 1, 2, 9, 9, 1, 6, 2, 3, 10, 7, 2, 4, 10, 9, 8, 2]
111111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111111
011111111111111111111111111111111111111111111111111111111111101
000001011111111111111111111111111111111111111111111111111111101
000000010111111111111111111111111111111111111111111111111111101
000000000010101011111111111111111111111111111111111111111010101
000000000000000000001010101111111111111111111111111111111010101
000000000000000000000000000101010101111111111111111111101010101
000000000000000000000000000001010101011111111111111111101010101
000000000000000000000000000000000101000001111100001111100000101
000000000000000000000000000000000000000000010100000111100000101
000000000000000000000000000000000000000000000000000010100000101
000000000000000000000000000000000000000000000000000000000000101
000000000000000000000000000000000000000000000000000000000000001

这张图片是您显示的矩阵的转置版本。行代表i值（i数组中的第一个元素），列代表k值（允许的权重）。1 是您将在树方法中访问的 DP 矩阵中的位置。当然你会看到很多0s 在矩阵的底部，但您将访问上半部分的每个位置。矩阵中大约 68% 的位置被访问。在这种情况下，自下而上的 DP 解决方案会更快。递归调用速度较慢，因为您必须为每个递归调用分配一个新的堆栈帧。使用循环而不是递归调用的 2 倍加速并不是不典型的，这已经足以使自下而上的方法更快。我们甚至还没有谈到树方法的记忆成本。

请注意，我在这里没有使用实际的 bnb。我不太确定你将如何做绑定部分，因为你实际上只有在通过访问它的子节点来计算它时才知道节点的值。

根据我的输入数据，自下而上的方法显然是赢家。但这并不意味着您的方法不好。恰恰相反。它实际上可以很好。这一切都取决于输入数据。让我们想象一下，K = 10^18你所有的重量都大约是10^16. 自下而上的方法甚至找不到足够的内存来分配矩阵，而您的方法很快就会成功。

但是，您可能可以通过执行 A* 而不是 bnb 来改进您的版本。(i, k)您可以使用此启发式估计每个节点的最佳值int(k / max(weight[1..i]) * min(values[1..i])并修剪大量节点。

于 2017-07-27T20:40:10.777 回答
6

我认为您有一个误解，即动态编程是背包问题的最先进的解决方案。该算法在大学中教授，因为它是动态规划和伪多项式时间算法的简单且很好的示例。

我没有该领域的专业知识，也不知道现在的最新技术是什么，但是分支定界方法已经使用了相当长的一段时间来解决背包问题：Knapsak-Problems一书Martello and Toth已经很老了，但对分支定界的处理相当广泛。

尽管如此，从你的角度来看，这是一个很好的观察，分支和绑定方法可以用于背包 - 唉，你出生太晚了，不能成为第一个有这个想法的人:)

您的证明中有一些我不明白的地方，我认为需要更多解释：

  1. 你需要记忆，否则你的树会有O(2^N)节点（显然会有这样的情况，否则背包不会是 NP-hard）。我在您的证明中看不到任何东西，可以确保记忆记忆/计算步骤小于O(NK).
  2. 动态编程只需要O(K)内存空间，所以我不明白为什么你可以声称“bnb 算法在时间和空间上总是比动态更好”。

也许您的说法是正确的，但是我无法按照现在的证明方式看到它。

另一个问题是“更好”的定义。如果分支定界方法更适合大多数问题或常见问题，或者它必须更​​适合最坏情况（在现实生活中不会发挥任何作用），那么分支定界方法是否更好？

我链接到的书也对算法的运行时间进行了一些比较。基于动态规划的算法（显然比在学校教授的算法更复杂）对于某些类型的问题甚至更好——参见第 2.10.1 节。对于一个完全的笑话来说还不错！

于 2017-07-30T20:32:16.300 回答
2

实际上，对于整数 0/1 背包，动态规划可能更好，因为：

  1. 没有递归意味着你永远不会遇到堆栈溢出
  2. 无需对每个节点进行查找搜索，因此通常更快
  3. 如您所述，存储最后两列意味着内存要求较低
  4. 代码更简单（不需要记忆表）
于 2017-07-27T18:31:46.010 回答