What is a Greedy Approach?

💰💰 Greedy algorithms

Greedy is an algorithmic paradigm where the solution is built piece by piece. The next piece that offers the most obvious and immediate benefit is chosen. The greedy approach always makes the choice that maximizes the profit and minimizes the cost at any given point. It means that a locally-optimal choice is made in the hope that it leads to a globally optimal solution.

A real life example

For example:

You just got a new piggy bank to have some savings for your college admission. The bank is small, and can only contain a fixed weight. Therefore, you have to be smart and choose the maximum value vs weight ratio for adding anything into it. You have a fixed number of coins and have to pick them one at a time until the capacity of the bank is reached.

This is also called the Fractional Knapsack Problem. The local optimal strategy is to choose the item that has maximum value vs weight ratio. This strategy also leads to an optimal global solution because we are allowed to take fractions of an item.

💡 How to make the optimal choice?
The greedy algorithm only has one shot to compute the optimal solution. It can never go back and reverse the decision. Hence, the algorithm makes greedy choices at each step to ensure that the objective function is $optimized$.

Shortest path finding problem

In order to understand the un-optimized solution issue, consider the following shortest path finding problem.

Look at the figure above. You have to travel the minimum distance from the starting point $Venice(S)$ to the ending point $Rome(E)$.

You are given the distance values respective to each path. Your goal is to minimize this (distance) value from $S -> E$

Following the greedy approach, you first pick the minimum choice available at the starting point. So, the path would look like:

$Venice -> Cinque\ Terre\ NP Cost = 10$

Next, we have two options available:

$Cinque\ Terre\ NP -> Rome Cost = 75$

$Cinque\ Terre\ NP -> Florence Cost = 27$

Following the greedy approach, we have to take the path with the least cost , i.e., $27$. Now, we have covered:

$Venice -> Cinque\ Terre\ NP -> Florence$ Cost = 10 + 27 = 37

At Florence, we have only one option to go forward: Naples to Sorrento to Amalfi to Pompeii and finally to Rome.

Hence,

$Venice ->CinqueTerreNP -> Florence -> Naples -> Sorrento -> Amalfi -> Pompeii -> Rome$ $Cost = 10 + 27 + 35 + 2 + 3 + 5 + 17 = 99$

Even though we can easily spot that, instead of taking that first smallest step costing $10$, if we go to $ Venice -> Florence$ costing $15$, the whole trip costs $77!$

Let me show you how!

$Venice -> Florence -> Naples -> Sorrento -> Amalfi -> Pompeii -> Rome$ Cost = 15 + 35 + 2 + 3 + 5 + 17 = 77$

---

Therefore, it can be concluded that sometimes the greedy algorithm fails to find the globally optimal solution because it does not consider all the data. However, there are many implementations, like Dijkstra’s and Kruskal’s algorithms, of this approach that we will look into further in this chapter.

Observations about the greedy approach

Greedy algorithms have some advantages and disadvantages:

Advantages:

• Easy to devise: It is easier to come up with a greedy approach (or even multiple greedy algorithms) for a single problem rather than computing solutions via other ways like binary search, dynamic, or functional programming.

• Compute the running time complexity: Analyzing the run time for greedy algorithms is generally simpler than other techniques like traversals of trees, graph algorithms, or divide and conquer. For the divide and conquer method, it is not clear whether the technique is fast or slow? This is because, at each recursion call, the size of the problem shrinks while the number of subproblems increases.

Disadvantages:

• Un-optimized solution: One of the major disadvantages of the greedy approach is that initially, you might take a smaller step that leads to one big step that costs the maximum. Therefore, the final solution can never be optimized! (This is explained later in the example.)

• Proof of correctness: For greedy algorithms, it is harder to understand the correctness issues of a solution. Even with the correct algorithm, it is hard to prove why it is correct? While proving the correctness of a greedy algorithm, it requires a good deal of effort and patience. Moreover, the methods like proof of correctness via contradiction are used for this purpose.