There are many methods that mathematicians and scientists use when they need to solve complex problems. One of the most versatile and simple to understand is the so-called greedy algorithm. Although it is not always able to find an optimal answer, it is frequently used because it is very fast. In this article we explain what it consists of, what advantages it has, and how to use it.
To solve a problem, a series of steps must be followed. These steps must be clearly defined, whether they are executed by a computer or by a human. The correct definition of these steps guarantees that if the system is applied twice to a given problem, the solution will be the same. This true recipe is called an algorithm, which is nothing more than a sequence of ordered and finite steps that allow us to solve a specific problem in minimal time. The word "algorithm" comes from the Latin "dixit algorithmus", and this in turn from the name of a Persian mathematician called Muhammad ibn Musa al-Jwarizmi.
The greedy algorithm
There are problems that, despite having an extremely simple approach, lack a solution that could be considered trivial. Imagine, for example, a traveling salesman who must cover 25 cities distributed throughout the interior of Spain: how should he do it to complete his work covering the least number of kilometers possible? The problem is surely of interest to a large number of companies, can be clearly defined in a few words, but its solution would require a computer several years of work. This is because the number of possible routes is 25! (25 factorial, that is, 1 x 2 x 3 x 4 x 5 x ... x 24 x 25), which means there are 15,511,210,043,330,985,984,000,000 routes to test and discard before knowing which one is optimal. Analyzing one billion routes per second, it would take 491,857,244 years to discover the optimal route for our traveler. This makes us realize the importance of a fast algorithm, even when it is not always capable of finding the best possible result.
The so-called greedy algorithm follows a simple but effective strategy. It simply involves choosing the optimal option at each local step, hoping to reach an optimal global solution. In the example of our traveling salesman, each step could be as simple as, being in city A, going to the nearest city we have not yet visited. Once there, repeat the procedure over and over until we have completed the route. We will surely not obtain an optimal result, but a fairly good path can be found in negligible time.
This type of algorithm, sometimes called greedy, voracious, or gluttonous, is the one that presents the least difficulties to researchers who must design and verify the operation of different strategies. The name "greedy" is because, at each step, the algorithm chooses the best "piece" it can "eat" without worrying about the steps remaining until it finds the solution. An algorithm of this type never reverses an already made decision: once incorporated, a “candidate to the solution” (going from city A to B, for example) will be part of the solution. And each rejected candidate is definitively eliminated.
Once it is clear that greedy algorithms proceed by steps, we can see in detail how their structure is. It starts with a set of candidates that is empty, that is, there is no solution. Then, at each step, it tries to add to the set the best candidate among the solutions not yet chosen, through a “selection function”. After each incorporation, it checks whether the resulting set of candidates is a solution to the problem.
Its generic scheme is the following: function greedy(C: set): set { C is the set of all candidates } S := empty { S is the set in which the solution is built } while not solution(S) and C <> empty do x := element of C that maximizes select(x) C := C {x} if completable(S U {x}) then S := S U {x} if solution(S) then return S else return no solution
To understand exactly how it works, we can apply it to another simple problem: suppose we have a group made up of four types of banknotes: ten 5s, five 10s, three 20s, and two 50s. We have to make a payment of 100 euros with the fewest possible bills. Which bills should we choose? The obvious solution is to use two fifty-euro bills, but how would a computer reach that solution? Very simple: using the greedy algorithm.
When posing that problem, the “candidate” (c) would be a finite set of banknotes, the “solution” (S) the set of banknotes sought and whose sum is the amount to be paid, “completable” is the sum of bills chosen at a given moment and that does not exceed the amount to be paid, and the “selection function” is nothing other than the one in charge of selecting the highest value bill available in the set of not yet selected candidates.
In the first step, one of the highest value bills available (one of 50) would be chosen. After verifying that the solution was not reached, one of the highest value bills available (the remaining 50) would again be taken and it would be verified that we have reached the solution. Simple to implement, right?
For more information, see the greedy algorithm on Wikipedia.
