Greedy Algorithms
- Tags
- comp-sci
Are algorithms which make greedy, locally optimal, choices for sub-problems in the hopes that this yields a globally optimal solution.
The greedy choice is generally a [see page 10, good choice] if:
- Cast the optimisation problem as one in which we make a choice and are left with one sub-problem to solve.
- Prove that there is always an optimal solution to the original problem that makes the greedy choice, so that the greedy choice is always safe.