6

假设我有这样的问题：

  • 背包容量=2000万
  • 项目数 = 500
  • 每个项目的重量是100到2000万之间的随机数
  • 每个项目的利润是1到10之间的随机数

那么哪个是解决我的问题的最佳方法？遗传算法还是动态规划？

请给我一个简单的解释，因为我是这方面的新手..

4

4 回答 4

5

动态规划（DP）：

  • 精确算法 - 找到全局最优解
  • 运行时间长
  • 占用大量内存
  • 实现起来非常简单

遗传算法（GA）：

  • 估计 - 不一定找到全局最优解
  • 运行时间短
  • 内存使用量取决于个人数量，但通常是可管理的
  • 解决方案的质量取决于选择有效的表示+让它运行足够长的时间
  • 实施起来相当简单，设计决策可能会稍微复杂一些，特别是如果您没有丰富的 GA 经验

爬山：

  • 估计 - 不一定找到全局最优解。比 GA 更容易在局部最优处停止，尽管有一些方法可以减少这种情况发生的机会
  • 运行时间短
  • 非常低的内存使用率
  • 实现起来非常简单

DP（或任何用于 NP 完全问题的精确算法）通常仅适用于相当小的问题，或者如果找到全局最优是最重要的事情。

DP有两种方法：（有一个相当简单的优化，你只存储2行，我的内存使用分析假设使用了这个优化）

  • 有一个项目 x 权重矩阵，单元格值是最大值

    矩阵大小 = 500 x 20 000 000

    运行时间 = O(500 * 20 000 000) = O(10 000 000 000)

    内存 = 最大值 10 * 500 -> 5 000 -> 短 = 2 字节 -> 2 * 20 000 000 * 2 = 80 000 000 < 80 MB

    说明： 下面的 A[i,j] 表示可从权重小于或等于j的元素 1 到 i 的任何子集获得的最佳（最高）值。下面的更新规则意味着 - 在不包括当前元素（因此重量和值保持不变）或包括它之间找到最佳值（因此查找（当前重量减去当前项目的重量）的最佳值并添加当前项目的值给它）。然后只返回 A[500, 20000000]，它表示可从所有元素的任何子集中获得的最大值，其最大重量为背包大小。

    算法：

    A[0, 0..20000000] = 0
for i = 1:500
for x = 0:20000000
  A[i, x] = max(A[i-1, x], value(i) + A[i-1, x-weight(i)])
// ignore value(i) + A[i-1, x-weight(i)] when weight(i) > x
return A[500, 20000000]

  • 有一个项目 x 值矩阵，单元格值是最小权重

    矩阵大小 = 500 x 10*500

    运行时间 = O(500 * 10*500) = O(2 500 000)

    内存 = 最大值 20 000 000 -> int = 4 字节 -> 2 * 500 * 4 = 4 000 < 4 KB

    解释：下面的 A[i,j] 表示从元素 1 到 i 的任何子集可获得的最低权重，其值等于j。下面的更新规则意味着 - 在不包括当前元素（因此重量和值保持不变）或包括它（因此查找最佳值（当前值减去当前项目的值）之间找到最佳值并添加当前项目的重量）。任何单元格的值都是生成该值的子集的确切权重，因此我们需要查看所有单元格 A[500, x]，它表示任何值 x 的元素的最小权重子集。

    算法：

    A[0, 0] = 0
A[0, 1..5000] = ∞
for i = 1:500
for x = 0:5000
  A[i, x] = min(A[i-1, x], weight(i) + A[i-1, x-value(i)])
// interpret A[i-1, x-value(i)] as 0 when value(i) > x
return largest x that A[500, x] <= 20000000

所以，是的，复杂性几乎不言自明，第一种方式您将等待几个小时，但第二种方式只需几秒钟，并且内存使用量也有类似的差异（尽管 80 MB 仍然几乎可以忽略不计）（注意这与规则相差甚远，每个案例都需要单独分析）。

于 2013-02-13T08:34:08.053 回答
3

动态编程可以在时间O(numItems * knapsackCapacity)和O(knapsackCapacity)内存中运行。这意味着，对于您的规格，您将拥有：

  • 关于20.000.000 x 500 = 10.000.000.000操作 - 可能会在几个小时内完成执行，具体取决于您的机器；
  • 由于一件商品的利润最多为 10，而您最多可以拥有 500 件商品，这意味着您的最大理论利润不能超过10 x 500 = 5000. 这可以用 2 个字节（一个短字节）表示。所以你还需要2 x 20.000.000 / 1024 / 1024 ~= 38 MB内存来存储你的 DP 数组。再说一次，没那么多。

其他人已经提到了每个的优点和缺点。GA 会更快完成，但 DP 解决方案也应该在几个小时内完成，它会给你一个准确的答案。

就个人而言，如果等待几个小时解决问题不是问题，我会选择 DP。

注意：这是使用O(knapsackCapacity)内存运行的 DP：

dp[i] = maximum profit obtainable for weight i
for i = 1 to numItems do
  for j = knapsackCapacity down to items[i].weight do
    dp[j] = max(dp[j], dp[j - items[i].weight] + items[i].profit)
于 2013-02-13T14:16:14.723 回答
0

没有“最好”的方法，每种方法都有其优点和缺点。
在这种情况下，权衡是在找到的解决方案的最优性之间 - GA 不以任何方式保证找到最佳解决方案。
计算解决方案所需的时间/空间 - 使用动态编程将为您节省一些冗余计算，但您仍然必须至少计算一次所有可能的组合才能找到最佳解决方案（甚至可能是任何解决方案）。

于 2013-02-13T08:31:36.307 回答
0

首先，您需要将动态规划视为一种精确算法，它可以保证答案将是最佳答案。另一方面，GA 是一种启发式算法，通常会收敛到局部最优值。背包有一个动态规划解决方案，如果它们是整数，则它是伪线性的 (O(capacity*number_of_items))。在您的情况下，您需要大约 1e10 的操作和内存。这对于单台计算机是可行的。因此，如果找到最佳答案对您很重要并且您有足够的时间（大约几个小时），您可以使用动态编程方法。否则，您可能更喜欢使用启发式算法，例如 GA。

于 2013-02-13T08:37:27.750 回答