Greedy Algorithms Flashcards
What are greedy algorithms?
A greedy algorithm always makes the choice that looks best at the moment.
That is, it makes a locally optimal choice in the hope that this choice will lead to a globally optimal choice.
What is the greedy-choice property?
We can assemble a globally optimal solution by making locally optimal (greedy) choices.
In other words, when we are considering which choice to make, we make the choice which looks best in the current problem, without considering results from subproblems.
What are the differences between greedy algorithm and dynamic programming?
In greedy algorithm we make whatever choice seems best at the moment and then solve the subproblem that remains.
The choice made by a greedy algorithm may depend on choices so far, but it can not depend on any future choices or on the solution to subproblems.
DP solves the subproblems before making the first choice.
