Topics In Demand
Notification
New

No notification found.

What is a Greedy Algorithm in Data Structures?
What is a Greedy Algorithm in Data Structures?

November 9, 2022

321

0

A Greedy algorithm is a method of problem-solving that chooses the best choice based on the circumstances at hand. This approach ignores the notion that the best solution could not ultimately be what is best. The algorithm never goes back and corrects inaccurate decisions. 

 

The runtime complexity is very reasonable with a greedy solution. However, the issue statement must meet both of the following two requirements before you can employ a greedy solution: Greedy Selection of Property A global (overall) optimal solution can be reached by selecting the best alternative at each stage.

 

Optimum Substructure: A problem has an optimal substructure if an optimal solution to the whole problem includes optimal solutions to each subproblem.

How to Write a Greedy Algorithm?

You can create a greedy solution for the given issue statement by following the instructions provided below:

 

Find the ideal substructure or subproblem in the given problem as the first step.

 

Step 1:  Select the solution elements (e.g., largest sum, shortest path).

Step 2: Create an iterative process for analyzing each subproblem and determining the best solution.

 

Let's tackle a real-world issue and devise a greedy fix for it.

 

  1. Method to Develop a Solution: The presented issue is simple and greedy. With the current Time and number Of Things in mind, we must choose the items from array A that will complete a task in the shortest period for each iteration. We must finish the tasks on the list below to find a solution.
  2. The array A should be sorted ascending.
  3. Choose a timestamp one at a time.
  4. Add the timestamp value to the current time after obtaining the timestamp.
  5. Add one more thing to the number Of Things.
  6. Up until the current Time value reaches T, repeat steps 2 through 4.

 

For detailed explanations, visit the DSA training and become an expert in DSA concepts. 

 

Example of a Greedy Algorithm

 

Find the most efficient way, using a greedy approach, to get from the starting place to the destination city.

 

Greedy Solution: We must preserve a graph structure to solve this issue. The solution to this problem will involve creating a tree structure for that graph structure. Following are the steps to generate this solution:

 

  1. Beginning with the source vertex
  2. Choose one vertex at a time that is the furthest away from the source vertex in terms of edge weight.
  3. If the connecting edge does not form a cycle, add the chosen vertex to the tree structure.
  4. Until the destination vertex, keep adding nearby fringe vertices to the tree.

 

Limitations of Greedy Algorithm

The following items represent a greedy algorithm's drawbacks:

 

The greedy algorithm does not offer the best solution for every problem since it bases its decisions on the information available at each iteration without considering the bigger picture.

 

It is difficult for a greedy algorithm to assess its correctness. Even when the answer is correct, it can be difficult to explain why it is true.

 

Applications of Greedy Algorithm

 

Here are a few uses for the greedy algorithm:

 

  • Used in Minimum Spanning Tree Construction: Prim's and Kruskal's greedy algorithms are used to build minimum spanning trees.
  • Utilized in Huffman Encoding: A Huffman tree is constructed using a greedy technique to create a lossless compressed file from a given picture, spreadsheet, or video.
  • Utilized to Address Optimization Issues: Classic optimization issues that can be solved using a greedy algorithmic paradigm include the Graph - Map Coloring, Graph - Vertex Cover, Knapsack Problem, Job Scheduling Problem, and Activity Selection Problem.

 

Characteristics of a Greedy Method

 

The greedy method is an easy and direct approach to solving optimization issues. In order to 

achieving the global optimum entails selecting the option that is locally optimal at each stage. Making the locally optimal decision at each stage in the greedy method's search for the global optimum is how it works. The objective function might be minimized or maximized at each phase to achieve this. The key benefit of the greedy method is that it is rather simple to use and comprehend. The use of this strategy does have some drawbacks, though. 

 

First of all, the greedy approach does not always result in the best answer. The knapsack problem is one of the most well-known applications of the greedy approach. In this problem, a group of things with a weight and a value are provided. Our goal is to find the subset of objects that increases value while reducing weight. The greedy approach would take the thing with the highest value at each phase. However, this isn't the wisest approach. 

 

Consider the following group of things, for instance:

 

Item 1: Value = 6, Weight = 2.

Item 2: Value = 3, Weight = 2.

Item 3: Value = 5, Weight = 4

 

Item 1 and Item 3 would be taken by the greedy approach, giving us a value of 11. Nevertheless, the best course of action would be to combine Items 2 and 3, giving a total value of 8. 

Therefore, the greedy approach does not necessarily lead to the ideal outcome.

There are numerous such instances of the greedy approach. The Huffman coding algorithm, which is used to compress data, is likely the most well-known. This approach provides us with a set of symbols with varying weights. At each phase, the greedy technique would simply select the symbol with the lowest weight. But this isn't the wisest course of action. 

 

Take the following set of symbols, for instance:

 

Weight = 2; Code = 00; Symbol 1.

Weight = 3, Code = 010 in Symbol 2.

Weight = 4, Code = 011 in Symbol 3.

 

Components of a Greedy Algorithm

 

Any greedy algorithm needs to have the following four elements:

many potential solutions (typically represented as a graph)

a system for rating applicants based on certain characteristics

a method of choosing from a group of candidates the best one based on ranking

 

Pseudo Code of Greedy Algorithms

The following is an illustration of pseudo-code for a greedy algorithm:

Function GreedyAlgorithm(problem) / currentState equals the problem's starting point while goalState!= currentState CurrentState = next state; pick Next State (currentState); return currentState;

 

Disadvantages of Using Greedy Algorithms

The biggest drawback of utilizing a greedy algorithm is that it might not identify the best answer to a query. In other words, it might not result in the optimal result. Furthermore, greedy algorithms can be extremely sensitive to changes in input data; even a minor modification can result in a completely different outcome. Finally, greedy algorithms might be challenging to use and comprehend.

 

Conclusion

 

In this blog on greedy algorithms, you learned what a greedy programming paradigm is and the characteristics and procedures for creating a greedy solution in DSA.

 

 


That the contents of third-party articles/blogs published here on the website, and the interpretation of all information in the article/blogs such as data, maps, numbers, opinions etc. displayed in the article/blogs and views or the opinions expressed within the content are solely of the author's; and do not reflect the opinions and beliefs of NASSCOM or its affiliates in any manner. NASSCOM does not take any liability w.r.t. content in any manner and will not be liable in any manner whatsoever for any kind of liability arising out of any act, error or omission. The contents of third-party article/blogs published, are provided solely as convenience; and the presence of these articles/blogs should not, under any circumstances, be considered as an endorsement of the contents by NASSCOM in any manner; and if you chose to access these articles/blogs , you do so at your own risk.


© Copyright nasscom. All Rights Reserved.