最优子结构

Question

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

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

澄清：

CLRS 对最优子结构的定义是：“如果问题的任何最优解都包含子问题的最优解，则该问题表现出最优子结构”。

为什么说“如果问题的某些最优解包含子问题的最优解，则问题表现出最优子结构”还不够？

Answer 1

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

\n\n

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

\n\n

为了阐明你的观点，对于特定的 A 实例和最佳 A 解决方案，不需要存在预言机 g ，以便管道 h \xe2\x88\x98 g \xe2\x88\x98 f 从给定的解决方案生成该解决方案实例。（换句话说，h 不必是满射的。）另一方面，对于 f 构造的 B 实例，h 必须能够处理 g 中的每个可能的最优 B 解。

\n\n

确保 h 正确的一个常见策略是找到从 A 解到 B 解的“子结构”函数 k 以及“拼接”子结构的方法，即证明，给定 A 解 x 和 a B 解 y 不比 k(x) 差，存在一个不比 x 差的 A 解 x\' 使得 k(x\') = y。然后 h 可以在其输入的 k 下优化逆图像中的所有内容。拼接不必适用于所有解决方案 x，仅适用于一种最佳解决方案。

\n