问最优子结构

EN

在我对近似算法的研究中，我受到了一些困扰，这涉及到寻找近似最优解的动态程序。我认为，正确地考虑动态程序的正确性的方法是将(在复杂性理论意义上)从一个问题简化为一个子问题。这种缩减经常被递归地应用于回忆录，但这些都是现在的细节。

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

为了说明您的观点，对于一个特定的A-实例和一个最优的A-解决方案，不需要存在一个oracle，使管道h∘g∘f从给定实例生成该解决方案。(换句话说，h不一定是虚幻的。)另一方面，对于f构造的B实例，h必须能够处理从g到g的每一个可能的最优B解。

确保h是正确的一种常见策略是从A-解到B-解找到一个“子结构”函数k，以及一种“拼接”子结构的方法，即证明，给定A-解x和B-解y不差于k(x)，存在A-解x‘不比x差x，使k(x') =y，那么h就可以对它输入的k下的逆图像中的所有事物进行优化。没有必要将剪接应用于所有的解x，只有一个最优解。

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

现在，当我们正式证明这类算法的正确性时，这是通过归纳法完成的。我们证明了我们的‘基本子句’是正确的(通常非常容易)，然后我们假设任何比当前小的问题-也是最优的。然后利用这一假设证明了大问题的正确性。

如果我们不知道所有的解都是最优的--我们就无法证明，用额外的一步，我们就能够将最优解修改为小问题的最优解，从而解决更大的问题--我们就没有足够的信息来证明这一说法。

如果我们知道其中一些子问题是最优解，那就不足以确保使用这个子问题，也就是我们对指标的最优解，才能得到更大问题的最优解。

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

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

如果我们只知道其中一个是最优的-我们无法证明算法是正确的，因为我们可能需要‘其他’的情况下，我们没有最优解。

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