Greedy algorithms and optimal substructure

Question

On Wikipedia page it is said that greedy algorithms are ideal only for problems which have optimal substructure.

Questions:

1. What is optimal/non-optimal substructure?
2. What is local and global optimum?
3. How to prove that Greedy algorithm yields global optimum?

Glyceric

Dukeling, I came here to see the answers. Your answer doesn't help nor this -1. – Glyceric

@downvoters: please comment the reason for the downvote. – Eustis

@Jobin The downvotes were likely because the question shows (too) little research effort, but now it's a self-answer, so that doesn't really apply any more (but we can't exactly find the downvoters now, and the upvote cancelled them out). – Pantin

Answer 1

I have found the answers and glad to share:

1. What is optimal/non-optimal substructure? A problem is said to have optimal substructure if an optimal solution can be constructed efficiently from optimal solutions of its subproblems. This property is used to determine the usefulness of dynamic programming and greedy algorithms for a problem

2. What is local and global optimum? Local optimum of an optimization problem is a solution that is optimal (either maximal or minimal) within a neighboring set of candidate solutions. Global optimum - is the optimal solution among all possible solutions, not just those in a particular neighborhood of values.

3. How to prove that Greedy algorithm yields global optimum? Usually, global optimum can be proven by induction. Typically, a greedy algorithm is used to solve a problem with optimal substructure if it can be proved by induction that this is optimal at each step. Otherwise, providing the problem exhibits overlapping subproblems as well, dynamic programming is used.

To prove that an optimization problem can be solved using a greedy algorithm, we need to prove that the problem has the following:

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

Matroids can be used as well in some case used to mechanically prove that a particular problem can be solved with a greedy approach.

And finally, some good examples of greedy algorithms.

Glyceric

Link is broken!! – Precede

If we are guaranteed that a problem has optimal substructure ,what kind of approach do we choose to go first? A Greedy one and if a polynomial solution won't come up we go for a Dynamic approach or vice versa? First DP check the solution and if it's not polynomial we then choose a greedy approach? – Someday

@MosheD Then fix it! – Blythebm