A greedy algorithm is an algorithm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum. In many problems, a greedy strategy does not in general produce an optimal solution, but nonetheless a greedy heuristic may yield locally optimal solutions that approximate a global optimal solution in a reasonable time.
For example, a greedy strategy for the traveling salesman problem (which is of a high computational complexity) is the following heuristic: "At each stage visit an unvisited city nearest to the current city". This heuristic need not find a best solution but terminates in a reasonable number of steps; finding an optimal solution typically requires unreasonably many steps. In mathematical optimization, greedy algorithms solve combinatorial problems having the properties of matroids.
Read more about Greedy Algorithm: Specifics, Types, Applications, Examples
Famous quotes containing the word greedy:
“The modern picture of The Artist began to form: The poor, but free spirit, plebeian but aspiring only to be classless, to cut himself forever free from the bonds of the greedy bourgeoisie, to be whatever the fat burghers feared most, to cross the line wherever they drew it, to look at the world in a way they couldn’t see, to be high, live low, stay young forever—in short, to be the bohemian.”
—Tom Wolfe (b. 1931)