Menu
On Wikipedia page it is said that greedy algorithms are ideal only for problems which have optimal substructure.
Questions:
609
An optimization problem has optimal substructure if and only if an optimal solution to the problem contains within it optimal solutions to subproblems. Correct greedy algorithms require that the problem has the optimal substructure property.
Greedy-choice property: A global optimum can be arrived at by selecting a local optimum. 2. Optimal substructure: An optimal solution to the problem contains an optimal solution to subproblems. The second property may make greedy. algorithms look like dynamic programming.
A given problem is said to have Optimal Substructure Property if the optimal solution of the given problem can be obtained by using the optimal solution to its subproblems instead of trying every possible way to solve the subproblems.
I have found the answers and glad to share:
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
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.
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.
138
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
