What is greedy algorithm ?

Author: neptune | 08th-Jun-2022 | views: 413

In the programming world, there is no such technique that solves all computation problems. We need to apply various kinds of techniques for various problems. Some commonly used techniques are-

1. Divide and conquer

2. Randomized algorithms

3. Greedy algorithms 

4. Dynamic programming

Note: Greedy is a technique, not an algorithm.

Here we are going to understand what, where, how, and when we can use the technique i.e Greedy algorithm.

What is a Greedy algorithm?

A Greedy Algorithm always makes the choice that looks best at the moment. We make the locally optimal choice in the hope that it will lead us to the global optimal solution.

Where can we use the Greedy algorithm?

The Greedy method is quite powerful and works well for a wide range of problems. We can use the Greedy algorithm whenever we have to either maximize or minimize the problem.

We use Greedy method in the following algorithms:
1. Minimum-spanning-tree algorithm

2. Dijkstra Algorithm

3. Huffman Data-compression

Basic Structure of a Greedy algorithm.

Optimal_greedy_fun(Item, arr[], int n)

  1) Initialize empty result : result = ()  

  2) While (Iterate for all values)

      // Make your greedy choice to select item.

      i = SelectAnItem() 

      // If i is feasible, add i to the result

      if (feasible(i))

        result = result U i 

      // finally return result 

  3) return result

How do you decide which choice is optimal?

There are mostly two kinds of problems in optimization maximization or minimization. Assume that you have an objective function that needs to be optimized (either maximized or minimized) at a given point. 

A Greedy algorithm makes greedy choices at each level of computation to ensure that the objective function is optimized. It has only one chance to compute the optimal solution, it never gets back to the previous decision.

Advantages and disadvantages of Greedy algorithm:

1. When we solve an optimization problem first we came up with a Greedy solution.

2. Compare to other algorithms run time analysis of greedy is easier than others like divide and Conquer.

3. The disadvantage of Greedy is that it is very hard to prove that your solution and algorithm are correct.

Note: Most greedy algorithms are not optimized and correct.

Application of Greedy algorithm.

The greedy method is quite powerful and works well for various ranges of problems. Many algorithms can be viewed as applications of the Greedy algorithms, a few of them are:

1. Minimum Spanning Tree.

2. Dijkstra’s algorithm for finding the shortest paths from a single source.

3. Huffman codes (for Data compression).

Thanks for reading!!!

anonymous | May 11, 2022, 12:09 a.m.

Well explained 👍

anonymous | June 28, 2021, 10:54 a.m.

Nice 👍

Related Blogs
History of 'Algorithm' Origin
Author: neptune | 09th-May-2022 | views: 158
#Algorithms #Motivation
'Algorithm' is a word that actually dates back 900 years. The word comes from the name of a Persian mathematical genius “Muhammad ibn Musa al-Khwarizmi”, who came up with the Hindu-Arabic number...
View More