greedy algorithm
An algorithm that builds a solution step by step, always taking the choice that looks best right now and never revisiting it.
In more detail
Greedy algorithms are fast and simple, and they are correct only when the problem has the greedy-choice property. Dijkstra's, Prim's and Kruskal's algorithms, interval scheduling and Huffman coding are correct greedy algorithms. Coin change with arbitrary coins is the classic case where greed gives a wrong answer.
Related terms
- 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.
- 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.
- dynamic programming — A technique that solves a problem by breaking it into overlapping subproblems, solving each only once and storing the answers for reuse.
- interval scheduling — The problem of choosing as many non-overlapping time intervals as possible, such as meetings in one room.
Taught in
- Dijkstra: Shortest Paths With A Priority Queue — Algorithms & Data Structures for Working Engineers
- Minimum Spanning Trees: Kruskal And Prim — Algorithms & Data Structures for Working Engineers
- Greedy Algorithms: When Local Is Global — Algorithms & Data Structures for Working Engineers
- Recognising The Pattern — Algorithms & Data Structures for Working Engineers