5

通过动态规划技术解决算法的两个标准是

  1. 子问题应该是独立的。
  2. 子问题应该重叠。

我想我明白重叠意味着什么。它基本上意味着子问题具有可能相同的子子问题。因此，我们不是一次又一次地解决子子问题，而是一次解决，把它放在一个哈希表或数组中，然后可以查找它所需的嵌套时间。但是第 1 点（即子问题的独立性）在这里意味着什么？如果它们有一些共同的子子问题，我们如何称它们为独立的？我的意思是在这个阶段这对我来说听起来非常违反直觉。

编辑：这个标准实际上是在著名的书中给出的：CLRS 在动态编程一章中介绍算法。

4

6 回答 6

1

请告诉我们您在哪里阅读 DP 适用于重叠和独立子问题的问题。我不认为这是正确的，出于与您给出的相同直观原因 - 如果问题重叠，它们就不是独立的。

我通常将独立的子问题作为分而治之的算法的标准，而我将重叠的子问题和最佳子结构作为动态编程系列的标准。（直观地说，最优子结构是指一个更大问题的最优解是由子问题的最优解组成的。经典的例子是图问题中的最短路径：如果你知道从 A 到 B 的最短路径经过C，那么你也知道从 A 到 B 的最短路径经过 C 的那部分恰好是从 A 到 C 的最短路径。）

更新：哦，我明白了——是的，我想他们确实提到了独立性。但是我没有像您那样强调这一点。意思是，他们在最优子结构的更大和更重要概念的背景下或作为一种理解方式提到了独立性。

他们所说的独立性的具体含义是，即使两个问题重叠，它们也是“独立的”，因为它们不相互作用——一个问题的解决方案并不真正依赖于另一个问题的解决方案。他们实际上使用了我所做的相同示例，最短路径。最短路径问题的子问题是较小的独立最短路径问题：如果从 A 到 B 的最短路径经过 C，那么从 A 到 C 的最短路径不使用从 C 到 C 的最短路径中的任何边B.相比之下，最长路径问题不具有子问题的独立性。

我不认为 CLRS 提出独立性是错误的，但我确实认为他们使用的语言有点模棱两可。

于 2012-09-05T16:34:51.480 回答
1

正如 CLRS 中所提供的，作者解决了子问题的独立属性和重叠属性之间的区别。他们写，

“动态规划依赖于既独立又重叠的子问题似乎很奇怪。虽然这些要求可能听起来自相矛盾，但它们描述了两个不同的概念，而不是同一轴上的两个点。同一问题的两个子问题如果它们是独立的不共享资源。如果两个子问题确实是作为不同问题的子问题出现的同一个子问题，则它们是重叠的”（CLRS 第 3 版，386）。

于 2020-09-21T23:58:24.360 回答
0

我认为这些标准的措辞很糟糕，因为重叠和独立具有某种冲突的含义。

无论如何，为了能够有效地使用你需要的 DP 方法

  1. 可以根据更简单的问题递归定义的问题
  2. 部分解决方案的概念，其中剩余部分的解决方案不取决于您如何到达当前点

示例：如果您想计算从第一行开始在矩阵中移动并且每个步骤都在下一行并且在同一列或相邻列中移动时的最大和路径是什么，您可以将当前总和用作“状态” ，当前行和当前列，因为对于解决方案，用于到达当前位置的路径无关紧要。

1  4 [3] 2  1  4  9
2  1 [3] 1  2  3  1
9 [8] 3  0  1  2  9
0 [0] 2  4  1  6  3
1  2 [6] 3  0  4  1

在上面的模式中，这条路径的总和为 3+3+8+0+6。为了使总和最大化，您可以观察到从某个点经过的路径的最大值可以作为到达那里的最大值和从那里到矩阵末端的最大值。因此，解决方案可以拆分为独立的子问题，您可以缓存从矩阵的给定点到最后的最大总和的结果（独立于您如何到达该点）。

def maxsum(x, y):
    if (x, y) in cache:
        return cache[(x, y)]

    if y == height - 1:
        return matrix[y][x]

    if x == 0:
        left = -1
    else:
        left = matrix[y][x] + maxsum(x-1, y+1)

    center = matrix[y][x] + maxsum(x, y+1)

    if x == width-1:
        right = -1
    else:
        right = matrix[y][x] + maxsum(x+1, y+1)

    result = cache[(x, y)] = max(left, center, right)
    return result

如果我添加到规则中允许不超过三个“9”但是你不能只使用坐标作为状态，因为后面的子问题（到最后）将受到前一个的影响（即有多少个“9” “你在到达中间位置时已经收集了）。

您仍然可以使用动态编程方法，但具有更大的状态空间，例如将收集到的“9”的数量添加到当前状态表示中。

def maxsum(x, y, number_of_nines):
    if (x, y, number_of_nines) in cache:
        return cache[(x, y, number_of_nines)]
    ...
于 2012-09-06T06:39:41.687 回答
0

我不认为子问题应该是依赖的。事实上，如果子问题是独立的，那就太好了，但这不是必需的。

具有相关子问题的 dp 问题的一个很好的例子是： Paint Houses - Algorithmic questions (paint house problem)

在这里，子问题的解决方案取决于前一个房子的颜色。这种依赖性可以通过向 dp 数组添加一个维度并根据前一个房子的颜色构建解决方案来解决。

于 2020-07-22T05:25:43.353 回答
0

子问题是独立的。

分而治之并不存在独立。例如。在合并排序中。子问题在划分后合并，这意味着解决方案有共同的子问题。一切都需要合并，没有一条路可以给出答案。每个子问题都共享子问题，需要解决这些子问题才能获得最终答案。

                       (1, 4)
                     /         \
             (1, 2)             (3, 4)
          /        \            /       \
      (1,1)         (2,2)  (3,3)          (4,4)
          \          /          \        /
              (1,2)               (3, 4)
                      \         /  
                         (1, 4)
于 2020-04-10T14:23:37.873 回答
0

我的理解是子问题应该独立于父级更大的问题来解决。就像回溯子问题一样，确实取决于您在更大的问题中选择的解决方案。

于 2019-10-27T03:10:25.317 回答