What is a Greedy Algorithm?

Any algorithm that follows the problem-solving meta heuristic of selecting the locally optimal option at each stage in the hopes of discovering the global optimum is known as a greedy algorithm. 

General Method:

Often we are looking at optimization problems whose performance is exponential.

• We are given a set of restrictions and an optimization function when solving an optimization issue.
  • Possible solutions are those that satisfy the limitations.
  • An optimal solution is a feasible solution for which the optimization function has the best possible value.

• Lunch for the cheapest price: It works by purchasing the cheapest meat, fruit, or vegetable possible.
• By a greedy method we attempt to construct an optimal solution in stages.
  • At each level, we make the selection that appears to be the best at the time (based on some criterion).
  • Because a decision made at one step cannot be reversed at a later level, each decision must be feasible.

Greedy Algorithms have 5 pillars in general:

1. A set of candidates from which a solution is derived.
2. A function that selects the best candidate for inclusion in the solution.
3. A feasibility function that determines whether or not a candidate can contribute to a solution.
4. An objective function is a function that assigns a value to a solution or partial solution.
5. A solution function that will let us know when we’ve found a complete solution.

Greedy Algorithms offer both benefits and drawbacks:

• It is quite simple to devise a greedy algorithm (or even numerous greedy algorithms) for a given task.
• It will be considerably easier to analyze the run time of greedy algorithms than it will be for other techniques (like Divide and conquer). It’s unclear whether the Divide and conquer strategy is speedy or sluggish. This is because the size of the problem shrinks as the number of subproblems grows at each level of recursion.
• The tricky thing is that understanding accuracy issues for greedy algorithms is substantially more complex. Even if the algorithm is correct, proving why it is correct is difficult. Proving the correctness of a greedy algorithm is more of an art than a science. It necessitates a great deal of imagination.

Interested in learning about similar topics? Here are a few hand-picked blogs for you!

• What is single source shortest path?
• Define ACID property?
• What is binary search tree?
• Explain semaphore?
• What is deadlock?