分而治之是否利用了最优化的子结构？

Question

在分而治之的方法中，子问题是相互独立的。

因此，重叠的子问题不能被利用。

最优子结构状态的CLRS定义：

“如果问题的最优解包含子问题的最优解，则该问题显示出最优子结构。”

我们知道使用分而治之的方法解决子问题是最优的吗？如果是这样的话，我猜最优子结构适用于分而治之的方法。

Answer 1

是。它很快就能证明给自己看。

给定一个具有分而治之解决方案的算法，假设它没有最优子结构。我将编写一些简单的符号:P是总体问题，PL和PR是左右子问题。S( P )是P的解。

根据分治法的定义，要求S(P) = S(PL) + S(PR)，其中+是子问题解的重组。

根据已知不存在最优子结构的问题的定义，S(P) = S(PL) + S(PR)不一定是这样的。

从定义上看，这是一个直接的矛盾。该假设与给定的假设相矛盾，因此该假设一定是错误的。

您可以切换给定和假设，以获得相同的矛盾。

因此，说一个问题有一个最优子结构相当于说这个问题有一个分而治之的解决方案。