Optimal substructure

Question

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.

To clarify:

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"?

Answer 1

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.

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.)

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.

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.

Answer 2

In Dynamic programming we split the problem to smaller sub-problems, do some manipulation and provide answer for a bigger answer - very similar to recursion approach (and by no coincidence).

Now, when we come to formally prove correctness of such algorithm, this is done by induction. We prove that our 'base clause' is correct (usually very easy), and then we assume that any problem smaller than the current one - is also optimal. We then use this hypothesis to prove the correctness of out bigger problem.

If we didn't know all solutions are optimal - we wouldn't be able to prove that using the one extra step we were able to modify optimal solution to smaller problem to optimal solution to bigger problem - there would just not be enough information to prove this claim.

If we knew that some of the subproblems are optimal solution - it would not be enough to ensure that using this subproblem, which we have an optimal solution to - indeeds is the one we need to get the optimal solution to the bigger problem.

---

Have a look on knapsack for example, and let's have a look on its DP step:

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

If we knew only one of them is optimal - we were not able to prove the algorithm is correct, because we might have needed the 'other' case, where we do not have optimal solution to.

If we chose f(x,i-1) in the max() - it might have been the wrong choice. By ensuring we have optimal solution to all subproblems, we make sure this cannot happen.