DSA Greedy Algorithms

Greedy Algorithms

A greedy algorithm decides what to do in each step, only based on the current situation, without a thought of how the total problem looks like.

In other words, a greedy algorithm makes the locally optimal choice in each step, hoping to find the global optimum solution in the end.

In Dijkstra's algorithm for example, the next vertex to be visited is always the next unvisited vertex with the currently shortest distance from the source, as seen from the current group of visited vertices.

So Dijkstra's algorithm is greedy because the choice of which vertex to visit next is only based on the currently available information, without considering the overall problem or how this choice might affect future decisions or the shortest paths in the end.

The main problems in this tutorial, like sorting an array, or finding the shortest paths in a graph, have these properties, and those problems can therefore be solved by greedy algorithms like selection sort or Dijkstra's algorithm.

But problems like "The Traveling Salesman", or the "0/1 Knapsack Problem", do not have these properties, and so a greedy algorithm can not be used to solve them. These problems are discussed further down.

Also, even if a problem can be solved by a greedy algorithm, the problem can also be solved by non-greedy algorithms as well.

Algorithms That Are Not Greedy

Below are algorithms that are not greedy, meaning they do not only rely on doing locally optimal choices in each step:

• Merge Sort: Splits the array in halves over and over again, and then merges the array parts together again in a way that results in a sorted array. These operations are not a series of locally optimal choices like greedy algorithms are.
• Quick Sort: The choice of pivot element, the arranging of elements around the pivot element, and the recursive calls to do the same with the left and right side of the pivot element — those actions do not rely on making greedy choices.
• BFS and DFS Traversal: These algorithms traverse a graph without making a choice locally in each step on how to continue with the traversal, and so they are not greedy algorithms.
• Finding the nth Fibonacci number using memoization: This algorithm belongs to a way of solving problems called Dynamic Programming, which solves overlapping sub-problems, and then pieces them back together. Memoization is used in each step to optimize the overall algorithm, which means that at each step, this algorithm does not only consider what is the locally optimal solution, but it also takes into account that a result computed in this step, might be used in later steps.

The 0/1 Knapsack Problem

The 0/1 Knapsack Problem cannot be solved by a greedy algorithm because it does not fulfill the greedy choice property, and the optimal substructure property, as mentioned earlier.

The 0/1 Knapsack Problem states that you have a backpack with a weight limit, and you are in a room full of treasures, each treasure with a value and a weight.

To solve the 0/1 Knapsack Problem you must figure out which treasures to pack to maximize the total value of the treasures you take, and at the same time keeping below the backpack's weight limit.

The "0/1" means that you can either take an item with you, or not take it with you. So you are not allowed to take just a part of something.

This problem cannot be solved by a greedy algorithm, because choosing the item with the highest value, the lowest weight, or the highest value to weight ratio, in each step (local optimal solution, greedy), does not guarantee the optimal solution (global optimum).

Let's say your backpack's limit is 10 kg, and you have these three treasures in front of you:

Making the greedy choice by taking the most valuable thing first, the horse figure with value $600, means that you can not bring any of the other things without breaking the weight limit.

So by trying to solve this problem in a greedy way you end up with a metal horse with value $600.

But the best solution in this case is taking the shield and the pot, maximizing the total value in the backpack to be $800, while still being under the weight limit.

What about always taking the treasure with the lowest weight? Or always taking the treasure with the highest value to weight ratio?

While following those principles would actually lead us to the best solution in this specific case, we could not guarantee that those principles would work if the values and weights in this example were changed.

This means that The 0/1 Knapsack Problem cannot be solved with a greedy algorithm.

The Traveling Salesman

The Traveling Salesman Problem is a famous problem that also cannot be solved by a greedy algorithm, because it does not fulfill the greedy choice property, and the optimal substructure property, as mentioned earlier.

The Traveling Salesman Problem states that you are a salesperson with a number of cities or towns you must visit to sell your things.

The rules: You must visit every city, but only once, and end up in the same city as you started in.

The goal: Find the shortest possible route.

Using a greedy algorithm here, you would always go to the next unvisited city that is closest to the city you are currently in. But this would in most cases not lead you to the optimal solution with the shortest total path.

The simulation below shows how it looks like when a greedy algorithm tries to solve The Traveling Salesman Problem.

Running the simulation, it might not always be obvious that the algorithm is flawed, but you might notice how sometimes the lines are crossing, creating a longer total distance, when that is clearly not necessary.

While running a greedy approach to The Traveling Salesman Problem sometimes gives us a pretty good approximation to the shortest possible route, a greedy algorithm will not be able to solve The Traveling Salesman Problem in general.

The Traveling Salesman Problem does not fulfill the properties needed so that it can be solved by a greedy algorithm.