{"id":297,"date":"2011-06-15T21:01:39","date_gmt":"2011-06-15T20:01:39","guid":{"rendered":"http:\/\/www.aymericlamboley.fr\/blog\/?p=297"},"modified":"2011-06-15T21:05:48","modified_gmt":"2011-06-15T20:05:48","slug":"greedy-algorithm","status":"publish","type":"post","link":"http:\/\/www.aymericlamboley.fr\/blog\/greedy-algorithm\/","title":{"rendered":"Greedy algorithm"},"content":{"rendered":"

According to Wikipedia<\/a>, a greedy algorithm is any algorithm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding the global optimum. In general, greedy algorithms are used for optimization problems.<\/p>\n

An example of a Greedy algorithm is a charging machine. Assume that it give you your change with \u20ac currency, you will have coin of : 200, 100, 50, 20, 10, 5, 2, 1. Your change will be really easy to calculate with a greedy algorithm :<\/p>\n

var moneySystem:Array = [200, 100, 50, 20, 10, 5, 2, 1];\r\nvar giveBack:uint = 263;\r\nvar solution:Array = [];\r\n\r\ntrace(greedyMethod(moneySystem, giveBack, solution));\r\n\r\nfunction greedyMethod($moneySystem:Array, $giveBack:uint, $solution:Array):Array {\r\n\r\n\tif ($giveBack == 0) {\r\n\t\treturn $solution;\r\n\t}\r\n\r\n\twhile ($giveBack >= $moneySystem[0]) {\r\n\t\t$giveBack -= $moneySystem[0];\r\n\t\t$solution.push($moneySystem[0]);\r\n\t}\r\n\t\r\n\t$moneySystem.shift();\r\n\t\r\n\treturn greedyMethod($moneySystem, $giveBack, $solution);\r\n}<\/pre>\n
For 263, the algorithm will output : 200,50,10,2,1. It is the best solution. Thanks to the \u20ac currency, greedy algorithm will always give the best results.
\nHowever if we have an other money with only 4, 3, 1 coins and the change is 6 the greedy algorithm outputs 4, 1, 1 instead of 3, 3. That’s a fail !<\/p>\n
Another typical example is the knapsack problem : given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
\nAccording that our values are sorted in decreasing order we have :<\/p>\n
var objects:Array = [[\"A\", 12, 10], [\"B\", 10, 7], [\"C\", 8, 5], [\"D\", 7, 4], \r\n\t\t [\"E\", 7, 4],  [\"F\", 6, 4], [\"G\", 5, 2], [\"H\", 4, 2],\r\n\t\t [\"I\", 4, 1], [\"J\", 3, 2], [\"K\", 3, 2], [\"L\", 3, 1],\r\n\t\t [\"M\", 2, 2], [\"N\", 1, 1]];\r\nvar totalWeight:uint = 25;\r\n\r\ntrace(knapSack(totalWeight, objects));\r\n\r\nfunction knapSack($totalWeight:uint, $objects:Array):Array {\r\n\t\r\n\tvar currentWeight:uint = 0;\r\n\tvar subSet:Array = [];\r\n\t\r\n\tfor (var counter:uint;counter< $objects.length; ++counter) {\r\n\t\t\r\n\t\tif (currentWeight + $objects[counter][2] <= $totalWeight) {\r\n\t\t\tcurrentWeight += $objects[counter][2];\r\n\t\t\tsubSet.push($objects[counter]);\r\n\t\t}\r\n\t}\r\n\t\r\n    return subSet;\r\n}<\/pre>\n
The output is [A,12,10],[B,10,7],[C,8,5],[G,5,2],[I,4,1]. It's ok, but we aren't sure that it is the best result. The problem with a greedy algorith : it will always try to select the first parameter even if it is not the better.
\nFor instance, our max weight is 40, our objects are [\"A\", 30, 39], [\"B\", 12, 10], [\"C\", 12, 10], [\"D\", 12, 10], [\"E\", 12, 10],[\"F\", 4, 1]. The greedy algorithm choose A and F for a value of 34 whereas B, C, D, E is obviously the best value : 48. That's an other example where it fails.<\/p>\n
So to conclude greedy algorithms depends of datas if they are balanced or not. More data are balanced, more it will be powerful. For a perfect result, you can use dynamic programming method<\/a>. It is more complex and requires more resources. So it's up to us to find the best solution for our problem.<\/p>\n","protected":false},"excerpt":{"rendered":"
According to Wikipedia, a greedy algorithm is any algorithm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding the global optimum. In general, greedy algorithms are used for optimization problems. An example of a Greedy algorithm is a charging machine. Assume that it give … Continue reading Greedy algorithm<\/span> →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0},"categories":[6],"tags":[61,60,62],"_links":{"self":[{"href":"http:\/\/www.aymericlamboley.fr\/blog\/wp-json\/wp\/v2\/posts\/297"}],"collection":[{"href":"http:\/\/www.aymericlamboley.fr\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.aymericlamboley.fr\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.aymericlamboley.fr\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.aymericlamboley.fr\/blog\/wp-json\/wp\/v2\/comments?post=297"}],"version-history":[{"count":3,"href":"http:\/\/www.aymericlamboley.fr\/blog\/wp-json\/wp\/v2\/posts\/297\/revisions"}],"predecessor-version":[{"id":300,"href":"http:\/\/www.aymericlamboley.fr\/blog\/wp-json\/wp\/v2\/posts\/297\/revisions\/300"}],"wp:attachment":[{"href":"http:\/\/www.aymericlamboley.fr\/blog\/wp-json\/wp\/v2\/media?parent=297"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.aymericlamboley.fr\/blog\/wp-json\/wp\/v2\/categories?post=297"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.aymericlamboley.fr\/blog\/wp-json\/wp\/v2\/tags?post=297"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}