Greedy algorithm

From PEGWiki
Jump to: navigation, search

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[edit]

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.

Other examples[edit]

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: