Optimal substructure

An important principle of dynamic programming (DP) and greedy problems are that optimal solutions for a problem themselves contain optimal solutions to sub-problems.

Dynamic programming

Note: for ECE345 — Algorithms and Data Structures, proving optimal substructure is optional. Every other step of the proof is still required.

For DP, we primarily prove optimal substructure with either induction or contradiction. For the contradiction proof, here’s our general workflow:

• Show that the solution to the problem requires some choice. Suppose an optimal solution contains 2 choices (like choose or don’t choose for an 0/1 knapsack). Then, our problem can be broken into 2 sub-problems.
• Argue by contradiction that we now want to solve these subproblems optimally. Because if we didn’t, the original solution wouldn’t be optimal. A little confusing.

The induction proof is in my opinion much simpler, so it’s best suited for simpler DP problems. It follows the general workflow, and all it really does is prove that from the $k$th iteration (or previous iterations, for strong induction), we can construct an optimal solution.

Greedy algorithms

Note: for ECE345 — Algorithms and Data Structures, proving optimal substructure for greedy problems is mandatory.

For greedy problems, the optimal substructure proof is substantially easier than the proof of the greedy choice property. Like in DP, we solve the subproblem optimally for the original solution to be optimal, i.e., if we remove the first greedy choice such that $J\backslash \{j_1\}=j_2,j_3,\dots ,j_n$, then this must be an optimal solution to the subproblem.

We assume $J$ is an optimal solution where $j_1=g_1$ (for car building) or $g_1\in J$ (for scheduling). i.e., we assume $J=G$, where $G$ is the greedy solution. This is fine because we should’ve already proven this in the greedy choice property proof.

Then, suppose we define $J^{\prime }$ such that $J^{\prime }=J\backslash \{j_1\}$ as a solution to the subproblem. Then suppose that $J$ is optimal (fine) but $J^{\prime }$ is not optimal. We define $S=s_2,s_3,\dots ,s_n$ as an optimal solution to the subproblem such that $P(S)<P(J^{\prime })$.

Then, we construct $J^{\prime \prime }=\{j_1\}\cup S$ as a solution to the original problem. Then, we get:

$$P(J^{\prime \prime })=p_{j_1}+P(S)<p_{j_1}+P(J^{\prime })=P(J)$$

which is a consequence of how we defined $P(S)$. Then, $J^{\prime \prime }$ is a better solution than $J$, which is a contradiction. This is generally how the substructure proof goes.