- Greedy is best suited for looking at the immediate situation rather than looking at future states
- Assumes that a local good selection makes for a global optimal solution
- Two basic properties of optimal Greedy algorithms
- Greedy choice property = the globally optimal solution can be obtained by making a locally optimal solution (and may depend on past choices but not future choices), and reducing the problem
- Optimal substructure = optimal solution to the problem contains optimal solutions to the subproblems
- However, in many situations, there is no guarantee that making locally optimal improvements in a locally optimal solution gives the optimal global solution
- Often useful in conjunction with heaps