Greedy Algorithm
Definition
A greedy algorithm is an optimization technique that makes choices for local optimizations to achieve a global optimization.
It operates on the principle of “taking the best option now” without considering the long-term consequences.
Examples
- Fractional Knapsack: Optimizes the value of items that can be fractionally included in a knapsack with limited capacity.
- Dijkstra’s algorithm: Finds the shortest path from a source vertex to all other vertices in a weighted graph.
- Kruskal’s algorithm: Finds the minimum spanning tree of a weighted graph.
- Huffman coding: Compresses data by assigning shorter codes to more frequent symbols.