84:
74:
53:
256:
179:
158:
22:
1119:: a hill climbing algorithm would start with a randomized visitation order and then swap the order of nodes until it cannot optimize the solution anymore. A greedy algorithm, however, would start from a single node and add new nodes into the solution one by one until all nodes have been visited, at which point it terminates.
1096:, but not always), while the "greedy approach" usually relates to problems that boil down to graph traversal. The latter can be formulated as a function, but it's hard to describe continuous functions in terms of a graph, so hill climbing is probably the more general term. If there is more to it, I am also curious.
878:
Am I the only one bothered by the fact that the example image attempts to describe a real world situation by specifying the currency, but provides inaccurate coin values (Except for
Australia specifically). If it is a real world example, then specificity, accuracy, and relevance are pretty important.
516:
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
901:
I agree with this, when I came to this article I was confused for a while and had to investigate further to clarify that the example was using coins of those values rather than
American values. I was not sure that the 20 represented a single coin, rather than two 10 cent coins. I think it would be
885:
This should be specified and the exception of
American vs. Australian Currency should be clarified. If the currency itself is irrelevant, leaving the value of the objects as the only important element, then the real world example of money may be a poor example and could be replaced. I'm certain that
545:
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
822:
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 . I believe this is a "greedable" coin system, and have run the code above to verify this. In fact, isn't the previously stated
1222:
I noticed that in the "Cases of failure" section, an example of coins is given where a greedy algorithm will fail to find the example quantity of 41 cents. However, immediately following that, the "Types" section says "greedy algorithms are best suited for simple problems (e.g. giving change)."
504:
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
1226:
A possible edit would be "(e.g. giving change in most currencies)" or something similar. I'm not sure where the example is based as I've never come across a 4-cent coin (I'm writing from the UK). Another idea would be to change the example of failure to a different problem. Any thoughts?
1195:
makes it look like our article is a copyvio — it has essentially the same text as one of our paragraphs. On second glance, though, judging from the date of publication of the book, the dates at which the text in question was added to our article, and the history of our article showing the text
879:
Not to offend the folks from Down Under, but if this were specified then providing the example to a primarily
American website made using the American English dialect in regards to Australian Currency when that same currency verbiage is in use in both places... is rather irrelevant.
277:
998:
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.
659:
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.
1114:
The difference is that a hill climbing algorithm starts with a complete (but random) solution whereas a greedy algorithm starts without a solution, adding partial solutions until it reaches a complete solution. Compare an example about the
858:
Is there a different example that could be used, one that is simpler (because people, like me, may not understand what quarters, dimes, pennies and nickels are and how they work). Sorry, I can't think of a simple example just yet
902:
sufficient for the example to state what coin values were being used so there is no ambiguity. Switching to
American values would also work, but would take a lot more effort. I will go ahead and make the former edit.
1191:
I just reverted the addition of a citation to "Computational mind: a complex dynamics perspective" (Vladimir G. Ivancevic, Tijana T. Ivancevic, Springer, 2007). At first glance, the page in question of the book
1076:
algorithms. I can't tell the difference - is one more general than the other? If so, it seems like the relevant page should explain that. This comment is also posted on the discussion page there. Thanks.
760:
len(sols): break trial = sols+ if len(trial) < len(best): print "failure", best, trial # highlight solutions in which greedy is not optimal best = trial sols.append(best)
1053:
Greedy regexps are only sort of related to greedy algorithms - the match is always expanded as much as possible before applying the next term of the regexp, but greedy and nongreedy regexps describe
1122:
I don't think I can be as bold as to say you are comparing apples and oranges but there is a difference. And if anything, in my opinion 'greedy algorithm' is the more general term. If you read the
1259:
There are many many more applications of the greedy algorithm than the applications section lets on. I added a template asking to expand and improve that section. For example, the introduction to
1296:
An IP user with no other history (but evident knowledge of syntax) stripped out many links from the top section. Now maybe there were too many, but now I think there are too few. Opinions? —
301:
656:
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.
140:
517:
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.
441:
1223:
This seems to be a contradiction - with one section saying the algorithm is suited to finding optimal change and the preceding section illustrating a failure case with giving change.
701:
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?
358:
296:
1334:
1008:"ungreedy" is sometimes used for algorigtms that take the most conservative choice at each step rather than the one that increases the solution value the most, such as in
219:
710:
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:
229:
1126:
article you'll see a few variants listed. The 'simple hill climbing' version would be an example of a greedy algorithm whereas the 'Stochastic hill climbing' wouldn't.
1339:
734:
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.
1196:
growing organically rather than being added all at once, I think the more likely hypothesis is that
Ivancevic and Ivancevic copied from us. Therefore, per
195:
1329:
1324:
403:
130:
377:
242:
186:
163:
106:
882:
NOTE: Yes I looked up the history of the 20 remaining 20 cent silver coins minted in the 19th century which are not currently in circulation.
1319:
466:
1092:
If there is a distinction, I've mostly heard "hill climbing" in the context of traversing the solution space of a function (typically with
830:
803:
774:
728:
717:
coins) #compare each coin with the previous one return false end i = i+1 end return true end
1038:
752:
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:
533:
349:
611:
330:
97:
58:
844:
I believe the previous statement about greedability should read less than twice the amount of the previous coin, not more than. -
1243:
1175:
758:
coins = sols = ] for i in range(1,101): t = i best = # perform greedy for c in reversed(coins): while t : -->
595:
A little example (even pseudocode) would be convincing. Can someone add a typical greedy problem & solution to the article?
947:
927:
796:
Ah, ok. When you said sorted I assumed in increasing order, when in fact you meant decreasing order. That makes more sense.
422:
724:
743:
563:
Kruskal's algorithm is definitely greedy. When it adds an edge to the forest, it will never have to remove it from there. --
1281:
720:
387:
268:
33:
1116:
397:
311:
686:
Agree with Barr^3. But the text should make it clear that it may not produce an optimal solution, and can reference
1031:
Does greedy regex follow these rules, matter for this sort of topic? If it matters, I'm thinking about pcre regex.
432:
194:
related articles on Knowledge. If you would like to participate, please visit the project page, where you can join
1141:
978:
640:
575:
459:
716:
def canUseGreedy(coins) n = coins.length i = 1 while(i < n) do if (2*coins: -->
1205:
994:
Can someone mention what the name is for the "opposite" or "antonym" of the greedy algorithm, if there is one?
807:
778:
834:
921:
Can anyone shed some light on the purpose of the ordered (numbered) list at the beginning of the article? --
529:
1042:
864:
607:
1057:
languages and solve different problems; it's not a local heuristic for estimating a solution to a problem.
1239:
891:
666:
625:
525:
368:
39:
849:
603:
83:
621:
1269:
1235:
1231:
1171:
1167:
1163:
1034:
951:
931:
826:
799:
770:
739:
599:
521:
509:
21:
1201:
887:
759:= c: t -= c best.append(c) for c in coins: # DP knapsack if c : -->
687:
1273:
845:
105:
on Knowledge. If you would like to participate, please visit the project page, where you can join
1197:
1082:
1009:
907:
860:
89:
73:
52:
1301:
1277:
1135:
1101:
1016:
972:
675:
634:
569:
547:
287:
1193:
1093:
702:
339:
191:
674:
But it is not a necessary condition for a greedy algorithm to produce an optimal solution.
735:
942:
922:
413:
255:
1263:
contains a number of applications of greedy just to submodular function maximization.
278:
Requested articles/Applied arts and sciences/Computer science, computing, and Internet
1313:
1123:
1078:
1073:
1058:
1000:
903:
691:
1297:
1130:
1097:
1012:
967:
629:
564:
102:
79:
620:
See the image on the page for a simple example. Also see the linked articles
320:
767:
Try it with coins = to see that that is indeed a non-greedyable knapsack
178:
157:
1305:
1285:
1247:
1209:
1179:
1146:
1105:
1086:
1061:
1046:
1020:
1003:
983:
955:
935:
911:
895:
868:
853:
838:
811:
782:
705:
694:
678:
669:
645:
628:. The first one has a complete example, the second one some pseudocode. --
580:
550:
1159:
I saw this phrase in an article. Could someone document what it means?
690:
as a technique used for an algorithm to find an optimal solution. --
1260:
886:
weight, length, or area make more generic real-world examples.
396:
Find pictures for the biographies of computer scientists (see
15:
963:
823:
rule for "greedable" coin systems simply very wrong?
190:, a collaborative effort to improve the coverage of
101:, a collaborative effort to improve the coverage of
1187:Computational mind: a complex dynamics perspective
302:Computer science articles needing expert attention
1219:New to editing Knowledge, so please go gently...
442:WikiProject Computer science/Unreferenced BLPs
966:and no one spotted it... I've fixed it now. —
8:
359:Computer science articles without infoboxes
297:Computer science articles needing attention
1267:
263:Here are some tasks awaiting attention:
237:
152:
47:
1335:High-importance Computer science articles
962:Actually, an anonymous user messed it up
663:So it fails the greedy-choice property.
154:
49:
19:
1155:"forwardly greedy selection algorithm"
204:Knowledge:WikiProject Computer science
1340:WikiProject Computer science articles
207:Template:WikiProject Computer science
7:
184:This article is within the scope of
95:This article is within the scope of
38:It is of interest to the following
1266:No such thing as logical or not.
941:It looks like an anatomy list. --
378:Timeline of computing 2020–present
14:
1330:C-Class Computer science articles
1325:Mid-priority mathematics articles
404:Computing articles needing images
115:Knowledge:WikiProject Mathematics
1200:, we can't use it as a source. —
874:Relevancy of the Example Picture
254:
177:
156:
118:Template:WikiProject Mathematics
82:
72:
51:
20:
224:This article has been rated as
135:This article has been rated as
1286:07:38, 23 September 2018 (UTC)
1106:17:44, 26 September 2009 (UTC)
1087:19:06, 10 September 2009 (UTC)
721:Lars'); DROP TABLE Students;--
1:
1210:19:41, 13 November 2011 (UTC)
1147:21:42, 2 September 2010 (UTC)
1021:05:13, 7 September 2008 (UTC)
984:12:25, 11 November 2007 (UTC)
956:22:38, 10 November 2007 (UTC)
936:22:35, 10 November 2007 (UTC)
912:21:43, 29 December 2010 (UTC)
744:17:39, 18 February 2008 (UTC)
646:17:42, 10 November 2006 (UTC)
581:12:02, 30 November 2006 (UTC)
458:Tag all relevant articles in
198:and see a list of open tasks.
109:and see a list of open tasks.
1320:C-Class mathematics articles
1072:There is also an article on
1062:03:57, 9 November 2008 (UTC)
896:17:32, 29 October 2010 (UTC)
869:07:39, 8 November 2008 (UTC)
729:00:05, 6 December 2007 (UTC)
670:20:09, 19 January 2007 (UTC)
467:WikiProject Computer science
243:WikiProject Computer science
187:WikiProject Computer science
1306:05:47, 3 October 2019 (UTC)
706:03:14, 10 August 2007 (UTC)
695:05:18, 10 August 2007 (UTC)
398:List of computer scientists
1356:
1248:10:07, 17 April 2012 (UTC)
1180:19:53, 23 April 2010 (UTC)
812:23:24, 25 March 2008 (UTC)
783:23:16, 25 March 2008 (UTC)
679:06:44, 24 March 2007 (UTC)
551:09:42, 6 August 2006 (UTC)
230:project's importance scale
1047:21:06, 18 July 2008 (UTC)
460:Category:Computer science
236:
223:
210:Computer science articles
172:
134:
67:
46:
1068:Greedy vs. Hill Climbing
1004:18:02, 30 May 2008 (UTC)
854:16:27, 30 May 2008 (UTC)
839:08:23, 20 May 2008 (UTC)
505:Kruskal from this page?
462:and sub-categories with
141:project's priority scale
1215:Apparent contradiction?
98:WikiProject Mathematics
423:Computer science stubs
28:This article is rated
1255:Clean up applications
626:Dijkstra's algorithm
241:Things you can help
121:mathematics articles
1010:Regular expressions
688:dynamic programming
622:Kruskal's algorithm
90:Mathematics portal
34:content assessment
1288:
1272:comment added by
1251:
1234:comment added by
1183:
1166:comment added by
1144:
1138:
1049:
1037:comment added by
981:
975:
841:
829:comment added by
814:
802:comment added by
785:
773:comment added by
643:
637:
616:
602:comment added by
578:
572:
538:
524:comment added by
497:
496:
493:
492:
489:
488:
485:
484:
481:
480:
151:
150:
147:
146:
1347:
1250:
1228:
1182:
1160:
1140:
1134:
1094:gradient descent
1032:
977:
971:
824:
797:
768:
639:
633:
615:
596:
574:
568:
537:
536:) 4 October 2005
518:
471:
465:
340:Computer science
269:Article requests
258:
251:
250:
238:
212:
211:
208:
205:
202:
201:Computer science
192:Computer science
181:
174:
173:
168:
164:Computer science
160:
153:
123:
122:
119:
116:
113:
92:
87:
86:
76:
69:
68:
63:
55:
48:
31:
25:
24:
16:
1355:
1354:
1350:
1349:
1348:
1346:
1345:
1344:
1310:
1309:
1294:
1257:
1229:
1217:
1189:
1161:
1157:
1070:
1029:
992:
950:
930:
919:
876:
762:
718:
654:
614:) 19 March 2006
597:
593:
519:
502:
477:
474:
469:
463:
451:Project-related
446:
427:
408:
382:
363:
344:
325:
306:
282:
226:High-importance
209:
206:
203:
200:
199:
167:High‑importance
166:
120:
117:
114:
111:
110:
88:
81:
61:
32:on Knowledge's
29:
12:
11:
5:
1353:
1351:
1343:
1342:
1337:
1332:
1327:
1322:
1312:
1311:
1293:
1290:
1256:
1253:
1216:
1213:
1202:David Eppstein
1188:
1185:
1156:
1153:
1152:
1151:
1150:
1149:
1127:
1120:
1109:
1108:
1069:
1066:
1065:
1064:
1028:
1025:
1024:
1023:
1006:
991:
988:
987:
986:
959:
958:
946:
926:
918:
915:
900:
875:
872:
831:91.125.119.202
820:
819:
818:
817:
816:
815:
804:192.150.10.200
789:
788:
787:
786:
775:192.150.10.200
757:
756:
755:
754:
753:
747:
746:
715:
714:
713:
712:
711:
699:
698:
697:
653:
650:
649:
648:
592:
589:
588:
587:
586:
585:
584:
583:
556:
555:
554:
553:
540:
539:
510:User:WhiteCrow
501:
498:
495:
494:
491:
490:
487:
486:
483:
482:
479:
478:
476:
475:
473:
472:
455:
447:
445:
444:
438:
428:
426:
425:
419:
409:
407:
406:
401:
393:
383:
381:
380:
374:
364:
362:
361:
355:
345:
343:
342:
336:
326:
324:
323:
317:
307:
305:
304:
299:
293:
283:
281:
280:
274:
262:
260:
259:
247:
246:
234:
233:
222:
216:
215:
213:
196:the discussion
182:
170:
169:
161:
149:
148:
145:
144:
133:
127:
126:
124:
107:the discussion
94:
93:
77:
65:
64:
56:
44:
43:
37:
26:
13:
10:
9:
6:
4:
3:
2:
1352:
1341:
1338:
1336:
1333:
1331:
1328:
1326:
1323:
1321:
1318:
1317:
1315:
1308:
1307:
1303:
1299:
1291:
1289:
1287:
1283:
1279:
1275:
1271:
1264:
1262:
1254:
1252:
1249:
1245:
1241:
1237:
1233:
1224:
1220:
1214:
1212:
1211:
1207:
1203:
1199:
1194:
1186:
1184:
1181:
1177:
1173:
1169:
1165:
1154:
1148:
1143:
1137:
1132:
1128:
1125:
1124:hill climbing
1121:
1118:
1113:
1112:
1111:
1110:
1107:
1103:
1099:
1095:
1091:
1090:
1089:
1088:
1084:
1080:
1075:
1074:Hill climbing
1067:
1063:
1060:
1056:
1052:
1051:
1050:
1048:
1044:
1040:
1039:81.155.84.169
1036:
1026:
1022:
1018:
1014:
1011:
1007:
1005:
1002:
997:
996:
995:
989:
985:
980:
974:
969:
965:
961:
960:
957:
953:
949:
944:
940:
939:
938:
937:
933:
929:
924:
916:
914:
913:
909:
905:
898:
897:
893:
889:
883:
880:
873:
871:
870:
866:
862:
861:AndrewHarvey4
856:
855:
851:
847:
842:
840:
836:
832:
828:
813:
809:
805:
801:
795:
794:
793:
792:
791:
790:
784:
780:
776:
772:
766:
765:
764:
763:
751:
750:
749:
748:
745:
741:
737:
733:
732:
731:
730:
726:
722:
709:
708:
707:
704:
700:
696:
693:
689:
685:
684:
683:
682:
681:
680:
677:
672:
671:
668:
667:81.103.164.48
664:
661:
657:
652:Making Change
651:
647:
642:
636:
631:
627:
623:
619:
618:
617:
613:
609:
605:
601:
590:
582:
577:
571:
566:
562:
561:
560:
559:
558:
557:
552:
549:
546:(p. 504). --
544:
543:
542:
541:
535:
531:
527:
526:131.155.68.93
523:
515:
514:
513:
511:
506:
499:
468:
461:
457:
456:
454:
452:
448:
443:
440:
439:
437:
435:
434:
429:
424:
421:
420:
418:
416:
415:
410:
405:
402:
399:
395:
394:
392:
390:
389:
384:
379:
376:
375:
373:
371:
370:
365:
360:
357:
356:
354:
352:
351:
346:
341:
338:
337:
335:
333:
332:
327:
322:
319:
318:
316:
314:
313:
308:
303:
300:
298:
295:
294:
292:
290:
289:
284:
279:
276:
275:
273:
271:
270:
265:
264:
261:
257:
253:
252:
249:
248:
244:
240:
239:
235:
231:
227:
221:
218:
217:
214:
197:
193:
189:
188:
183:
180:
176:
175:
171:
165:
162:
159:
155:
142:
138:
132:
129:
128:
125:
108:
104:
100:
99:
91:
85:
80:
78:
75:
71:
70:
66:
60:
57:
54:
50:
45:
41:
35:
27:
23:
18:
17:
1295:
1292:underlinking
1268:— Preceding
1265:
1258:
1230:— Preceding
1225:
1221:
1218:
1190:
1158:
1071:
1054:
1030:
993:
920:
917:Ordered list
899:
884:
881:
877:
857:
843:
821:
719:
676:BarrBarrBarr
673:
665:
662:
658:
655:
604:86.34.42.206
594:
548:Brianyoumans
507:
503:
450:
449:
433:Unreferenced
431:
430:
412:
411:
386:
385:
367:
366:
348:
347:
329:
328:
310:
309:
286:
285:
267:
266:
225:
185:
137:Mid-priority
136:
96:
62:Mid‑priority
40:WikiProjects
1198:WP:CIRCULAR
1162:—Preceding
1033:—Preceding
825:—Preceding
798:—Preceding
769:—Preceding
703:Newyorkbrad
598:—Preceding
520:—Preceding
112:Mathematics
103:mathematics
59:Mathematics
1314:Categories
1261:this paper
1236:Snapey1979
1168:Skysong263
736:Hairy Dude
512:7/24/2005
1055:different
943:Thinboy00
923:Thinboy00
321:Computing
1282:contribs
1270:unsigned
1244:contribs
1232:unsigned
1176:contribs
1164:unsigned
1079:Jdvelasc
1059:Dcoetzee
1035:unsigned
1001:Dcoetzee
990:Opposite
948:contribs
928:contribs
904:Omgoleus
888:Cabbruzz
827:unsigned
800:unsigned
771:unsigned
692:Nethgirb
612:contribs
600:unsigned
591:Example?
534:contribs
522:unsigned
500:Untitled
369:Maintain
312:Copyedit
1298:Tamfang
1274:Lyhendq
1131:ZeroOne
1098:Maghnus
1013:BCoates
968:ZeroOne
954:, i.e.
934:, i.e.
859:though.
846:Kade304
630:ZeroOne
565:ZeroOne
350:Infobox
288:Cleanup
228:on the
139:on the
30:C-class
331:Expand
36:scale.
1027:regex
414:Stubs
388:Photo
245:with:
1302:talk
1278:talk
1240:talk
1206:talk
1172:talk
1136:talk
1102:talk
1083:talk
1043:talk
1017:talk
973:talk
964:here
952:@985
932:@983
908:talk
892:talk
865:talk
850:talk
835:talk
808:talk
779:talk
740:talk
725:talk
635:talk
624:and
608:talk
570:talk
530:talk
508:---
220:High
1117:TSP
131:Mid
1316::
1304:)
1284:)
1280:•
1246:)
1242:•
1208:)
1178:)
1174:•
1145:)
1139:/
1104:)
1085:)
1077:--
1045:)
1019:)
982:)
976:/
910:)
894:)
867:)
852:)
837:)
810:)
781:)
742:)
727:)
644:)
638:|
610:•
579:)
573:|
532:•
470:}}
464:{{
1300:(
1276:(
1238:(
1204:(
1170:(
1142:@
1133:(
1129:—
1100:(
1081:(
1041:(
1015:(
979:@
970:(
945:/
925:/
906:(
890:(
863:(
848:(
833:(
806:(
777:(
738:(
723:(
641:@
632:(
606:(
576:@
567:(
528:(
453::
436::
417::
400:)
391::
372::
353::
334::
315::
291::
272::
232:.
143:.
42::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
