DSA 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 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. Choosing a greedy algorithm is a design choice, just like Dynamic Programming is another algorithm design choice. Two properties must be true for a problem for a greedy algorithm to work:

Means that the optimal solution to a problem, is a collection of optimal solutions to sub-problems. So solving smaller parts of the problem locally (by making greedy choices) contributes to the overall solution. Most of the 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

Dijkstra's algorithm.

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.

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

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.

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.

and

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.

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.

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.

Every item has a weight and value. Your knapsack has a weight limit. Choose which items you want to bring with you in the knapsack. You can either take an item or not, you cannot take half of an item for example.

Maximize the total value of the items in the knapsack.

5 kg $300

4 kg $500

7 kg $600 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.

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.