What is Greedy algorithm?
[[Image:Greedy algorithm 36 cents.svg|thumb|280px|right| Greedy algorithms determine the minimum number of coins to give while [[Change-making problem|making change]]. These are the steps a human would take to emulate a greedy algorithm to represent 36 cents using only coins with values {1, 5, 10, 20}. The coin of the highest value, less than the remaining change owed, is the local optimum. Note that in general, [[dynamic programming]] or [[linear programming]] is required to find the optimal solution. However, most currency systems, including the Euro (pictured) and US Dollar, are special cases where the greedy strategy also finds an optimal solution.]] A '''greedy algorithm''' is an [[algorithm]] used in solving optimization problems. Greedy algorithms select the best result at each [[iteration]]. The global optimum is obtained by repeatedly selecting the local optimum. ==Examples== *[[Kruskal's algorithm]] for finding the [[minimum spanning tree]] in a [[graph]]. *[[Prim's algorithm]] for finding the minimum spanning tree in a graph. *[[Dijkstra's algorithm]] for finding the shortest path in a graph with non-negative edge lengths. There are some problems where greedy algorithms do not produce the best possible [[solution]]. In such cases, they often produce the worst possible one. Again look at the coin-changing example above, and imagine that there are coins for 25 cent, 10 cent and 4 cent. Now imagine that the sum of 41 cent needs to be changed. A greedy algorithm would pick 25 cent, 10 cent, and 4 cent, for a total of 39 cent. The algorithm is then stuck, because the remaining 2 cent cannot be changed. One possible way of solving the is to use the 25 cent coin, and four coins of 4 cent. {{tech-stub}} [[Category:Greedy algorithms| ]]