greedy-choice property
The property of a problem that a globally best solution can always be reached by making the locally best choice at each step.
In more detail
When it holds, a greedy algorithm is correct and usually fast. It holds for interval scheduling and Huffman coding but not for coin change with arbitrary coins. The usual way to prove it is an exchange argument.
Related terms
- greedy algorithm — An algorithm that builds a solution step by step, always taking the choice that looks best right now and never revisiting it.
- exchange argument — A proof technique for greedy algorithms: show that any optimal solution can be changed, one swap at a time, to include the greedy choice without getting worse.
- optimal substructure — The property that an optimal solution to a problem is built from optimal solutions to its subproblems.
Taught in
- Greedy Algorithms: When Local Is Global — Algorithms & Data Structures for Working Engineers
- Recognising The Pattern — Algorithms & Data Structures for Working Engineers