Greedy Algorithm in Data Structure

The Greedy algorithm solves optimization problems by making locally optimal choices, potentially leading to a globally optimal solution. This article covers the approach, related terms, and discusses its applications, including finding optimal solutions and approximating solutions for NP-Hard problems like the Traveling Salesman Problem.

Takeaways

Applications of Greedy Algorithm

• Finding an optimal solution (Activity selection, Fractional Knapsack, Job Sequencing, Huffman Coding).
• Finding close to the optimal solution for NP-Hard problems like TSP.

What is Greedy Algorithm?

To maximize the amount you take, you’ll obviously start with the $20 pile. If you’re able to finish that pile in under one minute, then you’ll move to the $10 pile (and not the $5 pile). If you’re extremely fast here too, then finally you’ll go for the $5 pile.

This is an example of the greedy approach. To maximize the amount of money you take, you start with the most desirable solution at that point of time. You don’t worry about whether this choice will hurt your profit in the coming future.

A greedy algorithm refers to any algorithm employed to solve an optimization problem where the algorithm proceeds by making a locally optimal choice (that is a greedy choice) in the hope that it will result in a globally optimal solution.

In the above example, our greedy choice was taking the currency notes with the highest denomination.

Characteristics of Greedy Algorithm

1. Greedy algorithms make the best choice at each step without reconsideration.
2. Decisions made are final and cannot be changed.
3. They may not always find the best solution and can sometimes yield suboptimal results.
4. Despite this, they are fast compared to other methods like dynamic programming.
5. Greedy algorithms are intuitive but challenging to prove their correctness mathematically.
6. In some cases, they can provide near-optimal solutions when an exact solution is impractical.

Why To Use Greedy Algorithm?

1. In many cases greedy algorithm is the most intuitive approach to solve a given optimization problem, that is, it is often the first-guessed solution and is easy to formulate.
2. Correct greedy algorithms are often more powerful and fast as compared to other approaches such as dynamic programming. This is because the greedy approach has to consider only one locally optimal choice while moving ahead with the solution, while dynamic programming must check all possible cases.
3. Greedy algorithms work for a wide range of problems, many of which have real-life applications in fields such as designing networking protocols and scheduling multiple events.

Architecture Of Greedy Algorithm

The basic architecture of the implementation of any greedy algorithm is as follows:

Input to Algorithm:
Function = F, Set of Inputs = C

Output:
Solution Set Which Maximizes or Minimizes Function

Steps:

1. Start with an empty solution set, S.
2. While there are still choices in the candidate set (C):
    - Choose an item from C.
    - If the chosen item is feasible:
        - Add it to the solution set S.
    - Remove the chosen item from C.
3. Return the solution set S. 

Here:

1. Select() function makes a greedy choice from the input set C
2. isFeasable() function checks whether the choice made by Select() function leads to an optimal value of F

Properties of Greedy Algorithm

There is no defined mathematical way to check the correctness of a given greedy algorithm. But it has been observed that many optimization problems that can be solved using some greedy algorithm satisfy 2 properties as given below:

1. Greedy choice property
2. Optimal substructure property

To understand these 2 properties in a better way, we will make use of an example problem.

The Indian Coin Change Problem

If we want to make a change for $X$ rupees, and we have an infinite supply of each of the denominations in Indian currency, that is, ${1, 2, 5, 10, 20, 50, 100, 500, 1000}$ valued coins, what is the minimum number of coins needed to make the change?

Greedy Choice Property

• A problem is said to exhibit greedy choice property if the globally optimal solution can be reached by making locally optimal (greedy) choices. These choices are not dependent on our future choices, and can not be altered after they have been made.
• It is equivalent to showing that there is an optimal solution to the problem that is obtained by only greedy choices.

It can be seen using brute force solutions that the optimal solution for some $X$, say 76, is made up of greedy choices only as follows:

$\ce{76 ->[-50] 26->[-20] 6->[-5] 1->[-1]0}$

So the solution set comprising of the minimum number of coins required for exchange is ${1,5,20,50}$.
As we can see, it consists of all the greedy choices, that is, choosing the coin of the largest denomination that is equal to or less than the value of the amount left.

Optimal Substructure

A problem is said to exhibit optimal substructure property if the global optimal solution to the said problem can be constructed by combining the greedy choice made with optimal solutions to the subproblem of the original problem.

Schematic Diagram of Optimal Substructure

Let’s break the above problem (for $X = 76$) into 2 parts:

1. The greedy choice: Choosing the largest possible coin denomination $\le$ 76, that is the coin with value 50.
2. The Subproblem: Applying our greedy algorithm on $Y = X-50 = 26$. As was seen above, the solution set for the subproblem is ${20, 5, 1}$.
3. Combining Solutions: Combining the greedy choice with the solution set of the subproblem, we get

${50}\cup{20, 5, 1} = {50, 20, 5, 1}$

Advantages Of Greedy Algorithm

1. All greedy algorithms are very intuitive and can be guessed easily.
2. Greedy algorithms are generally easy to understand as well as implement.
3. If correct, greedy algorithms find the optimal solution much faster as well more efficiently than its alternatives, such as dynamic programming.

Disadvantages Of Greedy Algorithm

1. Though very intuitive, it is very hard to prove mathematically the correctness of a greedy algorithm to solve the given problem at hand.
2. A greedy approach to solve optimization problems may not always be correct, may even lead to the worst possible solution (as in the case of the Travelling Salesman Problem).

Ready to conquer complex algorithms? Our Dynamic Programming Course is your ticket to success. Enroll today and elevate your coding proficiency!

Conclusion

• Greedy algorithm refers to a class of algorithms that use a greedy approach to find the optimal solution to some optimization problem.
• In any greedy algorithm, the current choice is made such that it is the best choice at that moment, without worrying about the future consequences of the said choice. Once made, this choice is never altered.
• Though intuitive, it is very hard to prove the correctness of the algorithm.
• Greedy algorithm does not always lead to the global optimal solution.
• A correct greedy algorithm is very fast and efficient as compared to other algorithms, such as dynamic programming.
• All problems which can be solved using a greedy approach exhibit greedy choice and optimal substructure properties.