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

Taught in

References