Greedy algorithms

In our everyday life, we always want to optimize something. For example, we may want to perform a job in a minimum amount of time, earn the maximum profit from the smallest effort, find the shortest path between two destinations, buy the best car on the market, and so on. This list will never end. Such problems, where we want the best output, are called optimization problems. There are many algorithm techniques to find the optimal solution, and the greedy algorithm is one. This algorithm design paradigm is one of the simplest yet elegant methods for solving optimization problems.

Greedily seeking a job

Suppose you are currently unemployed and looking for a job. You have gone to interviews with $5$ companies, and $2$ of them have selected you. Now, at the salary negotiation stage, the first company offers you $50,000$ USD per year. Since you don't have any job now, you will accept the offer. After a few days, the second company calls for negotiation and offers you $60,000$ USD with some extra benefits. No doubt that you will drop the previous job offer and grab this one.

The same thing happens with the greedy algorithm. It always picks the best option for the current situation, without thinking about what might happen in the future. However, please remember that this is not a specific algorithm, but a way to solve optimization problems. The greedy algorithm may not always find the best solution, but it never goes back and changes what it has already decided. So, the technique is very simple: pick the best currently available option and move on to the next step.

Greedily changing money

For the rest of the topic, let's assume that your job was as a cashier at a bank. Your task is to receive money from the customer and change money if necessary. Let's also assume you have an unlimited supply of $1, 5, 10, 50,$ and $100$-dollar notes. So, if you have to change $10$ dollars, you can do it in several ways: a $10$-dollar note, two $5$-dollar notes, ten $1$-dollar notes, etc. However, you want to perform the change in such a way that you require the minimum number of notes. This means that to change $10$ dollars, one $10$-dollar note is the optimal solution.

It would be cool to develop an algorithm that will efficiently tell you the effective way of changing money. To begin with, sort your notes in descending order: $\{100, 50, 20, 10, 5, 1\}$. Let's suppose you have to change $145$ dollars. How can you change this amount with a minimum number of notes? You can solve the problem easily by being greedy and choosing the bigger notes first. First, you take a $100$-dollar note and check if it exceeds your change amount. Since it doesn't exceed it, you take this $100$-dollar note. Now, you have to change $(145-100) = 45$ dollars.

You can see that both $100$- and $50$-dollar notes are greater than your remaining change amount of $45$. So, you choose the next greater note in line: a $20$-dollar note. You still need to change $(45-20) = 25$ dollars. You choose another $20$-dollar note, since the change amount is still higher than that. And, at last, you need a $5$-dollar note to complete the change. Please take a look at the table below:

Below is the pseudocode for the dollar change program. You can implement it on your computer and handle the money change problem efficiently.

function greedy_change(amount):
  notes = {100, 50, 20, 10, 5, 1}
  num_of_notes = 6
  solution = {}
  
  for (i = 0; i < num_of_notes, i++):
    while(amount >= notes[i]):
      // append(x, y) appends the element x to the array y
      append(notes[i], solution)
      amount = amount - notes[i]
  return solution

Drawbacks of being Greedy

Let's get back to the first hypothetical scenario introduced in this topic. Have you made the right decision for your career by choosing the second job? Based on the above situation, the answer is yes. However, in the long run, this may not be true. Although the first company initially pays less, it may raise employees' salaries more often than the second. Hence, the greedy algorithm may not always provide the best solution overall.

Now let's think about the money change problem once more. This time, assume you have the following notes: $\{15, 10, 1\}$, and someone asks you to change $20$ dollars using the minimum amount of notes. If you ask the greedy algorithm to solve this, it will return you one $15$-dollar and five $1$-dollar notes. This way, you would require six notes in total if you follow the greedy approach. However, this is not the optimal solution based on the notes provided. Two $10$-dollar notes would have been the optimal solution in this case.

Identifying Greedy problems

The question that comes naturally is: when does it make sense to use the greedy algorithm?

The answer is, the greedy algorithm will work if your problem has these two properties: Greedy choice property and Optimal substructure property.

• Greedy choice property: according to this characteristic, you can use a locally optimal solution to create a globally optimal solution.

Let's think about the first money change problem. Here, your goal was to change money using the minimum number of notes. Thus, the greedy property was to choose the largest notes as many times as possible, and as a result, you got this solution: $\{100, 20, 20, 5\}$. At each step, finding the local solution, you stuck to the only greedy property: choosing the largest notes as many times as possible. And in this case, this property indeed provided the globally optimal solution. Therefore, this problem had a greedy choice property. However, the second money change problem of changing $20$ dollars using $15$, $10$, and $1$-dollar notes didn't have that greedy choice property. That's what you can conclude from the fact that choosing the largest notes first didn't provide the globally optimal solution.

• Optimal substructure property:
  Suppose a problem $P$ has the optimal solution $S_P$. Now assume $A$ is a subproblem of $P$ and its optimal solution is $S_A$. You can say that problem $P$ has the optimal substructure if the solution $S_A$ is a subset of the solution $S_P$. This is true for every possible subproblem of $P$.

Let's see how to verify this property for the money change problem. The problem $P$ was to change $145$ dollars using the minimum number of notes, and you got the solution $S_P$: $\{100, 20, 20, 5\}$. Let's create a specific subproblem by removing $100$ dollars from the scenario. So, now the subproblem $A$ is to change $45$ dollars. If you solve this problem using the greedy method, you will get the subsolution $S_A$ to be $\{20, 20, 5\}$. Indeed, this is a subset of $S_P$. You can check that this would also hold if you removed $20$ or $5$ dollars, or both.

However, this doesn't guarantee your problem's optimal substructure property. You have to verify this for every possible subsolution, and this is a very tricky task that is usually performed using the mathematical induction technique. However, this goes beyond the scope of this topic. Sometimes, one doesn't go through the trouble of verifying optimal substructure, but rather checks the greedy algorithm using different inputs. If the algorithm passes the trial tests, you can be confident that your algorithm is correct. However, this doesn't strictly guarantee the correctness of the algorithm.

Conclusion

Below is the summary of the steps you have to follow to solve a problem using a greedy algorithm:

• Define your optimal solution;

• Check if the problem has these two properties: Greedy choice property and Optimal substructure property;

• Iterate over all subproblems and create the optimal solution.

You can solve a large number of optimization problems using the greedy algorithm. Some examples are Prim's algorithm, Kruskal's algorithm, Dijkstra's algorithm, and others. You will explore them later. The greedy solutions are simple and fast, since every new step deals only with the present situation to solve the problem, without considering what will happen in the future.