Greedy Algorithm

A greedy algorithm is a problem-solving approach that makes the locally optimal choice at each step, without reconsidering earlier decisions, in the hope of reaching a good overall solution. It produces a genuinely optimal result for some problems, including the activity selection problem, Huffman coding, and the minimum spanning tree algorithms of Prim and Kruskal, where researchers use exchange arguments to prove that no better solution is reachable. For many other problems a greedy approach yields only an approximation: the fractional knapsack problem admits an optimal greedy solution, but the greedy version of the 0-1 knapsack problem is only guaranteed to reach at least half the value of the true optimum. Greedy strategies also underlie the shortest-path algorithm devised by Edsger Dijkstra, decision tree learning methods such as ID3, and common routing algorithms, making the technique one of the most widely used general strategies in algorithm design despite its lack of a universal optimality guarantee. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/