A greedy algorithm is any algorithm that follows the problem solving metaheuristic of making the locally optimal choice at each stage^{[1]} with the hope of finding the global optimum.
For example, applying the greedy strategy to the traveling salesman problem yields the following algorithm: "At each stage visit the unvisited city nearest to the current city".
Contents
Specifics
In general, greedy algorithms have five pillars:
Greedy algorithms produce good solutions on some mathematical problems, but not on others. Most problems for which they work well have two properties:
Cases of failure
For many other problems, greedy algorithms fail to produce the optimal solution, and may even produce the unique worst possible solution. One example is the traveling salesman problem mentioned above: for each number of cities there is an assignment of distances between the cities for which the nearest neighbor heuristic produces the unique worst possible tour.^{[3]}
Imagine the coin example with only 25cent, 10cent, and 4cent coins. The greedy algorithm would not be able to make change for 41 cents, since after committing to use one 25cent coin and one 10cent coin it would be impossible to use 4cent coins for the balance of 6 cent. Whereas a person or a more sophisticated algorithm could make change for 41 cents change with one 25cent coin and four 4cent coins.
Types
Greedy algorithms can be characterized as being 'short sighted', and as 'nonrecoverable'. They are ideal only for problems which have 'optimal substructure'. Despite this, greedy algorithms are best suited for simple problems (e.g. giving change). It is important, however, to note that the greedy algorithm can be used as a selection algorithm to prioritize options within a search, or branch and bound algorithm. There are a few variations to the greedy algorithm:
 Pure greedy algorithms
 Orthogonal greedy algorithms
 Relaxed greedy algorithms
Applications
Greedy algorithms mostly (but not always) fail to find the globally optimal solution, because they usually do not operate exhaustively on all the data. They can make commitments to certain choices too early which prevent them from finding the best overall solution later. For example, all known greedy coloring algorithms for the graph coloring problem and all other NPcomplete problems do not consistently find optimum solutions. Nevertheless, they are useful because they are quick to think up and often give good approximations to the optimum.
Full article ▸
