时间戳

首页 > 解决方案 > 证明最优子结构的不同方法？

algorithm - 证明最优子结构的不同方法？

问题描述

对于最优子结构性质，它指出通过组合其子问题的最优解可以得到给定问题的最优解。

我们可以把它写成 Opt(给定问题) = f(Opt(subproblem 1), Opt(subproblem 2), ...)。其中 f 结合了子问题的最优解。

通常，为了证明最优子结构，我们证明如果 $Opt(given problem)$ 实际上是一个最优解，那么 Opt(subproblem 1), Opt(subproblem 2), ..., 也是最优的。例如，在 Cormen (CLRS) 书中可以看到这一点。

我的问题是：我们可以证明相反的吗？也就是说，我们证明如果 Opt(subproblem 1), Opt(subproblem 2), ..., 都是最优的，那么 Opt(given problem) 也是最优的吗？

标签： algorithmdynamic-programmingmathematical-optimization

解决方案

推荐阅读