最佳子结构 [英] Optimal substructure

问题描述

我试图更全面地了解动态编程中最佳子结构属性的使用，但我一直对为什么我们必须证明该问题的 any 最佳解决方案一无所知.其中包含子问题的最佳解决方案.

I'm trying to get a fuller picture of the use of the optimal substructure property in dynamic programming, yet I've gone blind on why we have to prove that any optimal solution to the problem contains within it optimal solutions to the sub-problems.

仅仅证明问题的一些具有此属性是不够的，然后用它来论证说由于我们的递归算法构建的解决方案至少与一个最优的解决方案，它本身就是最优的吗?换句话说，我无法在算法的正确性参数中指出我们需要所有最优解包含子问题的最优解的地方.

Wouldn't it be enough to show that some optimal solution to the problem has this property, and then use this to argue that since the solution built by our recursive algorithm is at least as good as an optimal solution, it will itself be optimal? In other words, I fail to spot where in the correctness argument for our algorithm we need that all optimal solutions contain optimal solutions to sub-problems.

要澄清:

最佳子结构的CLRS定义说:如果问题的任何最优解中包含子问题的最优解，那么问题就表现出最优子结构".

The CLRS definition of optimal substructure says that "a problem exhibits optimal substructure if any optimal solution to the problem contains within it optimal solutions to subproblems".

为什么仅仅说如果问题的最优解中包含子问题的最优解，那么问题就表现出最优子结构"还不够吗?

Why wouldn't it not be enough to say that "a problem exhibits optimal substructure if some optimal solution to the problem contains within it optimal solutions to subproblems"?

推荐答案

在我对近似算法的研究中，我对此感到有些不安，该算法涉及寻找近似最优解的动态程序.我认为，考虑动态程序的正确性的正确方法是，从问题到子问题的减少(就复杂性理论而言).这种减少通常是通过递归和备忘录进行递归应用的，但是现在这些只是细节.

I've been bothered a bit by this in my research on approximation algorithms, which involves dynamic programs that find approximately optimal solutions. The right way to think about the correctness of dynamic programs, I believe, is as a reduction (in the complexity theory sense) from a problem to a subproblem. This reduction often is applied recursively and with memoization, but those are details right now.

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

Let A be the problem and B be the subproblem. There's only one subproblem because we can combine multiple independent subproblems into one via a generalized Cartesian product. The reduction consists of two functions: f, from an A-instance to a B-instance, and h, from a B-solution to an A-solution. The correctness property that we need is that, for every function g from each B-instance to a corresponding optimal B-solution (the oracle), the composition h ∘ g ∘ f is a function from each A-instance to a corresponding optimal A-solution. (If h needs access to the A-instance, then extend B so that its instances contain an A-instance that must be copied verbatim into the corresponding B-solution.)

要说明您的观点，对于特定的A实例和最佳的A解决方案，不需要存在预言g，以使管道h∘g∘f从给定实例生成该解决方案. (换句话说，h不必是排斥的.)另一方面，对于由f构造的B实例，h必须能够处理g中所有可能的最优B解.

To make your point, for a particular A-instance and an optimal A-solution, there need not exist an oracle g such that the pipeline h ∘ g ∘ f produces that solution from the given instance. (In other words, h need not be surjective.) On the other hand, h must be able to handle every possible optimal B-solution from g for the B-instance constructed by f.

确保h正确的一种常见策略是找到从A解到B解的子结构"函数k以及拼接"子结构的方法，也就是说，证明给定A解x和不小于k(x)的B解y，存在不小于x的A解x'使得k(x')= y.然后，h可以优化逆向图像在其输入k下的所有内容.不必将拼接应用于所有解决方案x，只需将其应用于一个最佳解决方案即可.

One common strategy for ensuring that h is correct is to find a "substructure" function k from A-solutions to B-solutions and a way to "splice" substructure, that is, a proof that, given an A-solution x and a B-solution y no worse than k(x), there exists an A-solution x' no worse than x such that k(x') = y. Then h can optimize over everything in the inverse image under k of its input. It is not necessary that splicing apply to all solutions x, just one optimal one.

这篇关于最佳子结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！