Talk:Greedy algorithm
From Wikipedia, the free encyclopedia
The page says that Kruskal's Algorithm is also a Greedy Algorithm. Tho actually this does not work locally, instead Kruskal always takes the smallest weight of all to add an edge to the set. It knows the whole set of edges and in opposite to Prim it takes the smallest weight - shouldnt we remove Kruskal from this page?
--- User:WhiteCrow 7/24/2005
- I would find Kruskal's algorithm a more natural example of what I understand to be a greedy algorithm than Prim's. In fact, the phrasing seems somewhat unlucky: I'd describe a greedy algorithm as "an algorithm that repeatedly extends a partial solution in the way that increases the objective function most" (in the case of a maximization problem). In Prim's algorithm we maintain the invariant that the partial solution is a tree; in Kruskal's algorithm we're already happy with a forest. —Preceding unsigned comment added by 131.155.68.93 (talk • contribs) 4 October 2005
-
- My PhD computer scientist wife read this over and says the article is basically OK. We looked at the algorithms book that I reference (a standard book on the subject) and it agrees with the article's content. About Kruskal's: the book also specifically characterizes Kruskal's as a greedy algorithm (p. 504). --Brianyoumans 09:42, 6 August 2006 (UTC)
Contents |
[edit] Example?
A little example (even pseudocode) would be convincing. Can someone add a typical greedy problem & solution to the article? —Preceding unsigned comment added by 86.34.42.206 (talk • contribs) 19 March 2006
- See the image on the page for a simple example. Also see the linked articles Kruskal's algorithm and Dijkstra's algorithm. The first one has a complete example, the second one some pseudocode. --ZeroOne (talk | @) 17:42, 10 November 2006 (UTC)
[edit] Making Change
I feel that the Making Change problem in the picture should be changed to another problem because it is not a true greedy algorithm, or at least moved into a subsection with an explanation.
The making change problem is not a real greedy algorithm, because given different denominations of coins such as {1,4,6} then the greedy algorithm will fail to find an optimal solution for example 9 will be given 6+1+1+1 when the optimal is 4+4+1.
So it fails the greedy-choice property.
81.103.164.48 20:09, 19 January 2007 (UTC)
But it is not a necessary condition for a greedy algorithm to produce an optimal solution. BarrBarrBarr 06:44, 24 March 2007 (UTC)
-
- Agree with Barr^3. But the text should make it clear that it may not produce an optimal solution, and can reference dynamic programming as a technique used for an algorithm to find an optimal solution. --Nethgirb 05:18, 10 August 2007 (UTC)
- Is there a formula or reference explaining for what coin sets the greedy algorithm does or doesn't always yield the optimal way to make change with the minimum number of coins? Newyorkbrad 03:14, 10 August 2007 (UTC)
- Yes there is. If a coin value is more than two times bigger than the one smaller than it, you cannot use greedy. So if coins is a sorted array of coin values, this works:
def canUseGreedy(coins)
n = coins.length
i = 1
while(i < n) do
if (2*coins[i]>coins[i-1]) #compare each coin with the previous one
return false
end
i = i+1
end
return true
end
Lars'); DROP TABLE Students;-- (talk) 00:05, 6 December 2007 (UTC)
- I've added a note saying the greedy strategy is not optimal in general, that the general solution needs dynamic programming, and added the appropriate link. Hairy Dude (talk) 17:39, 18 February 2008 (UTC)
-
- This program suggests that US coins do not have the greedy property (2*10 < 25), but my simple program indicates that to 100 they do:
coins = [1,5,10,25,100]
sols = [[]]
for i in range(1,101):
t = i
best = [] # perform greedy
for c in reversed(coins):
while t >= c:
t -= c
best.append(c)
for c in coins: # DP knapsack
if c > len(sols): break
trial = sols[i-c]+[c]
if len(trial) < len(best):
print "failure", best, trial # highlight solutions in which greedy is not optimal
best = trial
sols.append(best)
-
- Try it with coins = [1,4,6] to see that that is indeed a non-greedyable knapsack —Preceding unsigned comment added by 192.150.10.200 (talk) 23:16, 25 March 2008 (UTC)
-
-
- Ah, ok. When you said sorted I assumed in increasing order, when in fact you meant decreasing order. That makes more sense. —Preceding unsigned comment added by 192.150.10.200 (talk) 23:24, 25 March 2008 (UTC)
-
Is the comment about US coins being special (in that the greedy algorithms works only for them) correct? The majority of the world's countries have coin systems like this [1 2 5 10 20 50 100 200]. I believe this is a "greedable" coin system, and have run the code above to verify this. In fact, isn't the previously stated rule for "greedable" coin systems simply very wrong? —Preceding unsigned comment added by 91.125.119.202 (talk) 08:23, 20 May 2008 (UTC)
I believe the previous statement about greedability should read less than twice the amount of the previous coin, not more than. -Kade304 (talk) 16:27, 30 May 2008 (UTC)
[edit] Ordered list
Can anyone shed some light on the purpose of the ordered (numbered) list at the beginning of the article? --Thinboy00 talk/contribs @983, i.e. 22:35, 10 November 2007 (UTC)
- Actually, an anonymous user messed it up here and no one spotted it... I've fixed it now. —ZeroOne (talk / @) 12:25, 11 November 2007 (UTC)
[edit] Opposite
Can someone mention what the name is for the "opposite" or "antonym" of the greedy algorithm, if there is one?
- Well the most obvious "opposite" if there could be said to be such a thing would be an algorithm that selects a globally optimal solution, rather than a locally optimal one. In practice, though, non-greedy algorithms include a lot more than just globally optimal algorithms. Dcoetzee 18:02, 30 May 2008 (UTC)
