Greedy algorithms

In short: A greedy algorithm makes the decision that looks best at the moment in every step, without regretting it later.

In more detail: It is fast and simple but does not always lead to the best overall result. For some problems it is provably optimal, for others only a good approximation.

In Depth

• Optimal: coin change with euro coins (always the largest fitting coin), Huffman coding, Dijkstra, minimum spanning trees (Kruskal, Prim).
• Not optimal: coin change with coins 1, 3, 4 for 6: greedy takes 4+1+1 (3 coins), optimal would be 3+3 (2 coins).
• Comparison: Dynamic programming considers all subproblems and finds the optimal solution but needs more effort.
• Property: Locally best decisions must lead to the global solution (greedy-choice property).

See also: Dijkstra’s algorithm, Dynamic programming