CODEWITHSUNDEEP
algorithmoptimization
user277465
user277465

Reputation:

Optimal substructure and Greedy choice

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

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?

Upvotes: 4

Views: 6107

Answers (2)

zstoebs
zstoebs

Reputation: 21

For future readers who may not be familiar with vertex cover nor dynamic programming, the phrasing of those definitions does make it sound similar.

I think a useful way to rephrase greedy choice is that the optimal solution will always contain the first choice chosen by the greedy algorithm, although it doesn't necessarily have to be the first choice in the said optimal solution **--> this is why they are different because although something may be optimal and display the greedy choice property you haven't proven that at every step the current most optimal solution was made. Think Prim's MST on a weighted graph: you can start at any vertex but that means that the algorithm may choose different edges at each step for these two solutions but they always choose the edge from any given vertex with the lowest weight, thus they have the greedy choice property. But you haven't proven anything about the whole solution at each step is absolutely optimal, just that choose the greediest option.

That's why they're different, although greedy choice can lead to optimal substructure, it doesn't prove that it has optimal substructure. Common arguments to prove optimal substructure are the exchange argument and the stay-ahead argument which build off of the knowledge the algorithm displays the greedy choice property.

Upvotes: 2

kraskevich
kraskevich

Reputation: 18556

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.

Upvotes: 3

Related Questions