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

Megacycle

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.

Kamseen

Hi David, thanks for answering! I like the reduction approach; so CLRS is basically saying that your h function must be surjective (when restricting the domain and codomain to respectively the set of optimal B-solutions and optimal A-solutions)? Which, since we pick the sub-solution y maximising h(y), makes for an easy conclusion that our solution is optimal. It would still work without the surjective requirement, only now the strategy for proving optimality is more open. Am I missing anything here? – Megacycle

@Megacycle Looks good to me. I expanded my answer to incorporate your comment. – Kamseen

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.

Ironing

Thanks for the reply @amit. Maybe I'm not understanding your reply, but I'm not suggesting (at least I don't think so) that we only show our recursive step to give optimal solutions for some problems. What I fail to see is why we need to show that any optimal solution (produced by our algorithm or not) must contain within it optimal solutions to sub-problems. Why wouldn't it be enough to show that for any (sub-)problem there exists an optimal solution that can be decomposed as done by our algorithm, and thereby get that the solution produced by our algorithm must be at least as optimal? – Megacycle

I might be misunderstanding you, but from my understanding the claim (sub-)problem there exists an optimal solution that can be decomposed as done by our algorithm, and thereby get that the solution produced by our algorithm must be at least as optimal? is wrong. Given an instance of a smaller problem, an optimal solution to it does NOT guarantee that modifying it will lead to the optimal solution to the bigger problem. We only know that there is SOME subproblem that leads to the optimal solution. We don't know which one. – Ironing

I should perhaps add that the definition of optimal substructure I have in mind is the one used in CLRS, and not the other one found elsewhere, namely "a problem is said to have optimal substructure if an optimal solution can be constructed efficiently from optimal solutions of its subproblems." – Megacycle

Sure, and we should take care to pick the right sub-problem (and its optimal solution) when building our recursive solution. What I'm curious about is why the CLRS definition of optimal substructure requires us to show that all optimal solutions to a given problem are essentially built recursively; wouldn't it be okay to allow some optimal solutions to have another structure, as long as at least one optimal solution to each sub-problem have the recursive structure? – Megacycle