Greedy algorithm - Revision history

Brian: remove false statement

2012-01-14T00:32:45Z

remove false statement

AurickQ: /* Change problem */

2012-01-14T00:31:21Z

‎Change problem

Brian: 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..."

2011-05-30T02:14:28Z

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..."

New page

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 path]]s 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.

[[Category:Algorithms]]
[[Category:Greedy algorithms]]

← Older revision		Revision as of 00:32, 14 January 2012
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.
−
−	In general, the change problem is greedily solvable if the set of denominations has the property that each denomination is strictly greater than the sum of all smaller denominations, which is the case with the set {1, 5, 10, 25} but not {2, 3, 4}.

	==Other examples==		==Other examples==

@@ Line 6: / Line 6: @@
 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}.
+In general, the change problem is greedily solvable if the set of denominations has the property that each denomination is strictly greater than the sum of all smaller denominations, which is the case with the set {1, 5, 10, 25} but not {2, 3, 4}.
 ==Other examples==