Greedy Algorithms

Greedy algorithms follow a simple pattern: Choose the best of all immediate choices, that gives you the most immediate benefit, and you'll find the bst answer eventually. This will bring you to a local maximum; if the local maximum is the overall maximum, you win!

Formulation a problem that lets you do so, however, may not always be obvious. Frame the question in a way that lets you pick a "best" option, and you're good to go.

Process:

• Determine the optimal substructure
• Develop a recursive solution
• Show that if we make the greedy chocie, only one subproblem remains.
• Prove that it's always safe to make the greedy choice
• Develop a recursive greedy algorithm
• Convert to iterative

Streamline Steps

• Cast the optimization problem as one in which we make a choice are left with one subproblem to solve.
• Prove that there is always an optimal solution that makes the greedy choice, so that the greedy choice is safe
• Show that greedy choice and optimal solution to subproblem combined gives us optimal solution to the problem Can we tell if a greedy algorithm will solve a particular optimization problem?
• No, generally
• But, should include greedy-choice property AND optimal substructure