- Choose how to make your decision (determine which approach is the simplest, most intuitive, smallest, and fastest)
- Start solving the problem by applying your decision rule
- Record the result of your decision (if needed) and determine the status of your problem
- Repeatedly apply the same approach at every step until reaching the problem conclusion
print ('Change: %s (using %i bills)'
% (change(30, [25, 15, 1])))
Change: [25, 1, 1, 1, 1, 1] (using 6 bills)
Clearly, the optimal solution is to return two 15 credit bills, but the algorithm, being shortsighted, started with the highest denomination available (25 credits) and then used five 1 credit bills to make up the residual 5 credits.
Some complex mathematical frameworks called matroids can help verify whether you can use a greedy solution to optimally solve a particular problem. If phrasing a problem using a matroid framework is possible, a greedy solution will provide an optimal result. Yet there are problems that have optimal greedy solutions that don't abide by the matroid framework. (You can read about matroid structures being sufficient, but not necessary for an optimal greedy solution.)
The greedy algorithms user should know that greedy algorithms do perform well but don't always provide the best possible results. When they do, it's because the problem consists of known examples or because the problem is compatible with matroid mathematical framework. Even when a greedy algorithm works best in one setting, changing the setting may break the toy and generate just good or acceptable solutions. In fact, the cases of just good or acceptable results are many, because greedy algorithms don't often outperform other solutions, as shown by- The make-change problem solutions show how a change in setting can cause a greedy algorithm to stop working.
- The scheduling problem illustrates how a greedy solution works perfectly with one worker, but don't expect it to work with more than one.
- The Dijkstra shortest-path algorithm works only with edges having positive weights. (Negative weights will cause the algorithm to loop around some nodes indefinitely.)
- Against a known optimal solution, when the greedy algorithm produces the optimal solution or you can change such a solution by exchanging its elements into an equivalent best solution (without any loss of performance or success). When a greedy solution matches the result of an optimal solution, you know that the greedy solution is equivalent and that it works best (this is the exchange proof).
- Against another algorithm when, as you see the greedy solution unfolding, you notice that the greedy solution stays ahead of the other algorithm; that is, the greedy solution always provides a better solution at every step than is provided by another algorithm.
Even considering that it's more the exception than a rule that a successful greedy approach will determine the top solution, greedy solutions often outperform other tentative solutions. You may not always get the top solution, but the solution will provide results that are good enough to act as a starting point (as a minimum), which is why you should start by trying greedy solutions first on new problems.