Difference between revisions of "Greedy algorithm"

Revision as of 02:14, 30 May 2011

A greedy algorithm solves an optimization problem in a series of steps by making a locally optimal choice at each step. For some problems, a greedy algorithm may produce a global optimum for all instances; we say that such problems may be solved greedily. For other problems, greedy algorithms will produce the correct answer only for some instances. When a greedy algorithm exists for a problem, it is generally the method of choice, because of its efficiency. Contrast this with dynamic programming, which accounts for all possible choices at each step, whether optimal or not, in order to ensure that a global optimum will be found, but requires more time and memory to consider all the locally non-optimal choices than a greedy algorithm does.

Change problem

A popular case study is a type of knapsack problem known as the change-making problem. In this problem, we are given the denominations of coins available and a certain amount of money for which we wish to make change in the fewest coins possible. For example, if there exist coins in the denominations of 1, 5, 10, and 25 cents (as in Canada), then we can make change for 47 cents using one 25 cent coin, two 10 cent coins, and two 1 cent coins. This uses five coins, which is the fewest possible.

For small input sizes, dynamic programming is the technique of choice, but if the set of denominations is fixed, the problem might be greedily solvable. The greedy algorithm is as follows: choose the largest denomination less than or equal to the amount we wish to change, and use a coin of that denomination; subtract its value from the amount we wish to change and repeat as many times as necessary. For example, starting with 47 cents, we first use a 25 cent coin, leaving 22 cents. Then we can no longer use a 25 cent coin but we can use a 10 cent coin, leaving 12 cents. Again we use a 10 cent coin, leaving 2 cents. Now 10 cent coins and 5 cent coins are too big, so we finish using two 1 cent coins. As this example suggests, the Canadian system of currency is amenable to the greedy solution method. However, if the set of coins had values of 2, 3, and 4 cents, then the greedy algorithm would fail altogether in making change for 5 cents, as we would first use a 4 cent coin then be left with only 1 cent, for which making change is impossible.

In general, the change problem is greedily solvable if the set of denominations has the property that each denomination is at least as large as the sum of all smaller denominations, which is the case with the set {1, 5, 10, 25} but not {2, 3, 4}.

Other examples

Main page: Category:Greedy algorithms

The basic idea of greediness may be combined with other data structures and algorithmic innovations to solve a variety of problems. The following algorithms can be considered greedy:

• Dijkstra's algorithm builds a shortest paths tree by repeatedly selecting the closest vertex adjacent to the partially built tree. This works only when edge weights are nonnegative; if negative edge weights are allowed, the dynamic Bellman–Ford algorithm must be used instead.
• Prim's algorithm builds a minimum spanning tree by repeatedly selecting the least costly edge that may be added to the partially built tree.
• Kruskal's algorithm builds a minimum spanning tree by repeatedly selecting the least costly edge in the graph such that its addition to the current set of edges will not introduce a cycle.
• Huffman coding, useful in data compression, is accomplished using a classic greedy algorithm.