Editing Greedy algorithm (section)

{{Short description|Sequence of locally optimal choices}}
[[Image: Greedy algorithm 36 cents.svg|thumb|280px|right| Greedy algorithms determine the minimum number of coins to give while making change. These are the steps most people 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. (In general, the [[change-making problem]] requires [[dynamic programming]] to find an optimal solution; however, most currency systems are special cases where the greedy strategy does find an optimal solution.)]]

A '''greedy algorithm''' is any [[algorithm]] that follows the problem-solving [[Heuristic (computer science)|heuristic]] of making the locally optimal choice at each stage.<ref name="NISTg">{{cite web|last=Black|first=Paul E.|title=greedy algorithm|url=http://xlinux.nist.gov/dads//HTML/greedyalgo.html|work=Dictionary of Algorithms and Data Structures|publisher=[[National Institute of Standards and Technology|U.S. National Institute of Standards and Technology]] (NIST) |access-date=17 August 2012|date=2 February 2005}}</ref> In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time.

For example, a greedy strategy for the [[travelling salesman problem]] (which is of high [[computational complexity]]) is the following heuristic: "At each step of the journey, visit the nearest unvisited city." This heuristic does not intend to find the best solution, but it terminates in a reasonable number of steps; finding an optimal solution to such a complex problem typically requires unreasonably many steps. 

In [[mathematical optimization]], greedy algorithms optimally solve [[Combinatorics|combinatorial]] problems having the properties of [[matroid]]s and give constant-factor approximations to optimization problems with the submodular structure.