最优子结构

Question

我试图更全面地了解动态规划中最优子结构属性的使用，但我对为什么我们必须证明问题的任何最优解都包含子问题的最优解视而不见。

难道仅仅证明问题的某些最优解决方案具有这个属性，然后用它来论证由于我们的递归算法构建的解决方案至少与最优解决方案一样好，它本身将是最优的，这还不够吗？换句话说，我未能发现在我们的算法的正确性参数中，我们需要所有最优解都包含子问题的最优解。

要澄清：

最佳子结构的CLRS定义说，“如果问题的任何最佳解决方案包含子问题的最佳解决方案，则问题表现出最佳子结构”。

为什么说“如果一个问题的某个最优解包含子问题的最优解，那么这个问题就表现出最优子结构”还不够呢？

Answer 1

在动态规划中，我们将问题拆分为更小的子问题，进行一些操作并为更大的答案提供答案——非常类似于递归方法（绝非巧合）。

现在，当我们正式证明这种算法的正确性时，这是通过归纳来完成的。我们证明我们的“基本子句”是正确的（通常很容易），然后我们假设任何比当前问题小的问题 - 也是最优的。然后，我们用这个假设来证明更大的问题的正确性。

如果我们不知道所有的解决方案都是最优的，我们就无法证明，利用这额外的一步，我们就能够将小问题的最优解决方案修改为大问题的最优解决方案，也就没有足够的信息来证明这个观点。

如果我们知道一些子问题是最优解——这将不足以确保使用这个子问题，我们有一个最优解——实际上是我们需要得到更大问题的最优解的子问题。

例如，看看背包，让我们看看它的DP步骤：

f(x,i) = max(f(x-weight[i],i-1) +val[i], f(x,i-1))

如果我们知道其中只有一个是最优的，我们就不能证明算法是正确的，因为我们可能需要“另一个”的情况，在这种情况下我们没有最优解。

如果我们在max（）中选择f（x，i-1），那可能是错误的选择。通过确保我们对所有子问题都有最优的解决方案，我们确保这不会发生。

Answer 2

在我对近似算法的研究中，我一直对此感到困扰，这涉及找到近似最优解的动态程序。我认为，思考动态程序正确性的正确方法是（在复杂性理论意义上）从问题到子问题的简化。这种减少通常是递归和记忆应用的，但这些都是现在的细节。

设 A 是问题，B 是子问题。只有一个子问题，因为我们可以通过广义笛卡尔积将多个独立的子问题组合成一个。归约由两个函数组成：f，从 A 实例到 B 实例，h，从 B 解到 A 解。我们需要的正确性属性是，对于从每个 B 实例到相应最优 B 解（预言机）的每个函数 g，组合 h ∘ g ∘ f 是从每个 A 实例到相应最优 A 解的函数。（如果 h 需要访问 A 实例，则扩展 B，使其实例包含必须逐字复制到相应 B 解决方案中的 A 实例。

为了说明你的观点，对于一个特定的A实例和一个最优的A解，不需要存在一个预言机g，使得流水线h g f从给定的实例产生那个解。（换句话说，h不需要是假设的。）另一方面，对于由f构造的B实例，h必须能够从g处理所有可能的最优B解。

确保h正确的一个常用策略是从A-解到B-解找到一个“子结构”函数k，并找到一种“拼接”子结构的方法，即证明给定一个A-解x和一个B-解y不差于k(x)，存在一个A-解x’不差于x，使得k(x’)= y。拼接不必适用于所有的解x，只要一个最优解即可。