Optimal substructure and Greedy choice

Question

I was reading about the two properties of a greedy problem and I'm trying to understand the difference between the two below :-

• Optimal substructure property: an optimal global solution contains the optimal solutions of all its subproblems.
• Greedy choice property: a global optimal solution can be obtained by greedily selecting a locally optimal choice.

Aren't the two equivalent? The two seem like the same thing ; could you give me an example where optimal substructure is satisfied but greedy choice is not? And an example for when greedy choice is satisfied but optimal substructure is not?

Answer 1

They are not equivalent:

Let's assume that we want to find the minimum vertex cover in a tree where each node has a cost(a cost of the cover is the sum of all costs of nodes in this cover). Dynamic programming can be used here: f(v, taken) is the minimum cost of covering a subtree rooted in v in such way that v is in the cover and f(v, not taken) is the minimum cost of covering this subtree without taking v. Optimal substructure property holds true because we can solve subproblems optimally(that is, find an optimal solution for each subtree) and then combine them to find the global optimal solution. However, greedy choice property does not hold true here: picking a vertex with the smallest cost until all edges are covered does not always yield an optimal result.

It is possible that greedy choice property holds true but the optimal substructure property does not if it is not possible to define what a subproblem is. For example, Huffman code construction algorithm always merges two smallest subtrees(and yields an optimal solution), so it is a greedy algorithm, but it is not clear what a subproblem is, so it doesn't make much sense to talk about the first property at all.