Greedy Algorithms

Here, We will discuss about Greedy algorithm, their element and Characteristics, advantages and disadvantages, and their applications.

What is Greedy Algorithm?

A Greedy Algorithm is a simple, intuitive algorithm that is used in optimization problem. It is designed to achieve optimum solution for a given problem.

This algorithm builds up a solution by choosing the option that looks the best at every step.

Greedy algorithm does not always give the best solutions. It works in a top-down approach.

Grredy Algorithm Steps

1. To begin with, the solution set (containing solution) is empty.
2. At each step, an item is added into the solution set.
3. If the solution set is feasible, the current item is kept.
4. Else, the item is rejected and never considered again.

Elements of Greedy Algorithms

The two basic properties of optimal Greedy Algorithms are:

1. Greedy Choice Property: This property says that optimal solution can be obtained by making a locally optimal solution. The choice made by Greedy algorithm may depend on earlier choices but not on the future.
2. Optimal Substructure: A problem show optimal substructure if an optimal solution to the problem contains optimal solution to the subproblems.

Characteristics of Greedy Algorithms

1. Used to solve optimization problem.
2. Straightforward method to solve a problem.
3. Easy to implement.
4. Always makes the choice that looks best at the moment

Advantages of Greedy Algorithms

1. Easy to understand and code.
2. It can perform better than other algorithms.
3. Analyzing the run time for greedy algorithm much easier than other techniques.

Disadvantages of Greedy Algorithms

1. Does not always give the best solutions.
2. Work much harder to understand correctness issues.

Applications of Greedy Algorithms

1. Sorting: Selection sort, Topological sort
2. Priority Queues: Heap sort
3. Huffman coding compression algorithm
4. Prism’s and Kruskal’s algorithms
5. Shortest path in Weighted Graph
6. Coin change problem
7. Fractional Knapsack problem
8. Job Scheduling algorithm

Related:

Want to Contribute:-

If you like “To The Innovation” and want to contribute, you can mail your articles to 📧 contribute@totheinnovation.com. See your articles on the main page and help other coders.😎