Difference between revisions of "Greedy algorithm"
(Created page with "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 pr...") |
(remove false statement) |
||
| (One intermediate revision by one other user not shown) | |||
| Line 5: | Line 5: | ||
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. | 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== | ==Other examples== | ||
Latest revision as of 00:32, 14 January 2012
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:
- 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.
