What are Greedy Algorithms?

Greedy Algorithms are simple and intuitive algorithms which work on the logic that if you optimize locally, you will eventually lead to a global optimum solution. It is an algorithm that always makes an optimal choice (greedy choice) at every single step in the solution.

This greedy choice by definition would depend on the type of the problem which would make it want to select the largest number, or smallest number, or take a shortest path, or take a step which gives maximum gold, etc.

So, at every step you are making this greedy choice in the algorithm. You continue this approach until you can make no further choices.

Where to use Greedy Algorithms?

The best time to use a greedy algorithm is when the problem exhibits the following two properties:

Greedy Choice Property
Choosing the best option at each step (local optimum) of the algorithm can make you arrive at a global optimum solution. Once a choice is made, it cannot be changed or modified in future.

Optimal Substructure
You can define optimal substructure by validating that an optimal solution to the overall problem contains optimal solution to all the sub-problems.

Where to not use Greedy Algorithm approach?

If a problem does not satisfy either the Greedy Choice property or the Optimal Substructure property, then Greedy Algorithm should not be used.

Other thing to keep in mind is that Greedy Algorithm will not always come with a correct solution, but you will definitely get an optimal solution. In some situations, an optimal solution is good enough and a correct solution is not needed. Greedy Algorithms outshine in such use cases.

Components of Greedy Algorithm

Following are the main components of a greedy algorithm:

• Objective Function
  • Function used to assign a value to the solution or partial solution.
• Candidate Set
  • Set of items from which the selection has to be made at each step.
• Selection Function
  • Function used to select the best choice (local optima).
• Feasibility Function
  • Function used to determine whether a candidate can be used to contribute to the solution.

Steps to achieve Greedy Algorithm

Step 1: Find the best subproblem that can be solved which can lead to global optima.

Step 2: Determine what the solution will include,

Step 3: Iterate over all the sub-problems with the local optima until you can no longer iterate.

Step 4: You have achieved at global optima.

General Structure of Solution based on Greedy Algorithm

Here is a general structure of the solution achieved for greedy algorithm using a python pseudo code:

def greedyAlgorithm(candidateSet):
    for choice in candidateSet:
        choice = SelectionFunction(candidateSet)
        feasibility = FeasibilityFunction(choice) 
        if feasibility:
            solution = solution + choice
    return solution

Uses of Greedy Algorithm

There are many uses of Greedy Algorithm. It is also used as a base algorithm for many other algorithms. Greedy algorithm is used in:

• Prim-Jarnik’s and Kruskal’s Minimal Spanning Tree (MST) algorithms
• Djikstra’s Shortest Path algorithm
• Huffman Coding
• Open-Shortest-Path-First routing protocol

Advantages and Disadvantages of Greedy Algorithm

Advantages

• Easy to come up with and find a solution for a problem.
• Analysis of run time is much easier and straightforward compared to other algorithms like Divide and Conquer.

Disadvantages

• It is hard to prove that the algorithm is correct.
• Greedy Algorithm can be slower compared to dynamic programming.

Types of Problems that can be solved with Greedy Algorithm

There are several types of problems that can be solved using greedy algorithms. In this section, we will discuss them all.

Activity Selection Problem

Given a set of activities, find the maximum number of activities that can be performed within the time constraints. Assume that only a single activity can be performed at a given time.

Job Sequencing Problem with Deadlines

Given a set of activities and profit earned by performing each activity, find the activities that can be performed in a given time to earn maximum profit. Assume that only one activity can be performed at a given time.

Graph Coloring Problem

Fine the minimum number of colors that need to be used to color graph’s adjacent vertices.

Shortest Superstring Problem

For a given list of strings, find the shortest string that contains each string in the list as substring. Assume that no string is a substring of other.

Dynamic Programming vs Greedy Algorithm

Greedy Algorithm is generally faster and less resource intensive than Dynamic Programming. This is because greedy algorithm will always find the local optima and move ahead to solve the problem whereas in Dynamic Programming, the problem is divided into several sub-problems and each of those sub-problems are solved to arrive at the most optimal solution.

How to prove that Greedy Algorithm is correct?

Proving the correctness of greedy algorithm is more of art than science. The correctness of Greedy Algorithm can be proven using the method of contradiction.

Since in greedy algorithm, the algorithm makes a choice at each step and it is essential that the choice that is made is always correct, we can approach the proof assuming that the outcome solution is not correct.

Now, if the solution that is given by greedy algorithms is same as the correct solution, then we have nothing to prove. However, if that is not the case then at some point while trying to optimize for local maxima, we made a mistake and picked an overall less optimal solution. Hence, by proof of contradiction we can say that greedy algorithms always give correct solution.

Example Greedy Algorithm Problems

• Shortest Path Problem
• Minimum Spanning Tree Problem in a Graph
• Huffman Encoding Problem
• K Centers Problem
• The classroom scheduling problem
• The knapsack problem
• The set-covering problem