Greedy algorithm

What is greedy algorithm?

Greedy algorithms are algorithms that take the best, immediate, or local, solution while looking for an answer. They identify the globally (overall)  optimal solution for certain optimization problems but might identify less-than-optimal solutions for certain instances of other problems. It follows the problem-solving heuristic of making the locally optimal choice at every stage.

It is essentially a mathematical process that, by deciding which next step will provide the most obvious benefit, hunts for simple solutions (which are easy to implement) to complicated, multi-step problems.

They are known as greedy algorithms because even though finding an optimal solution for every smaller instance will give you an instant output, the algorithm does not take the larger problem into account. It never reconsiders any decisions after they are made. 

These greedy algorithms function by constructing a set of objects from the smallest possible constituent parts in a recursive manner. In recursion, the solution to a specific problem depends on the solutions to smaller instances of the same problem. 

One major benefit of employing a greedy algorithm is that solutions to smaller instances of the problem tend to be straightforward and rather easily understandable.

There are two conditions that define the greedy paradigm:

Every stepwise solution needs to structure a problem towards its best-accepted solution.

It is sufficient if the structuring of the problem could stop in a finite number of greedy steps.

‍

What are the components of greedy algorithms?

Greedy algorithms tend to be made up of five components. These components include:

• A candidate set from which a solution is created.
• A selection function, which picks the best candidate that will be added to the solution.
• A feasibility function. This is used to determine whether a candidate can be used to contribute to a solution.
• An objective function, which assigns a value to a solution, or to a partial solution.
• A solution function. This will indicate when we have discovered a complete solution.

What are the properties possessed by problems on which greedy algorithms work?

Greedy algorithms find optimal solutions for some mathematical problems but not for some others. Here are the properties that the problems for which they do work tend to have.

1. Greedy choice property

This involves making the choice that seems the most appropriate at the time and then solving the subproblems that surface later. The choice made by a greedy algorithm could depend on choices made up to that point, but it will not depend on future choices or on all the solutions to the subproblem.

The algorithm iteratively makes greedy choice after greedy choice, thus shrinking each given problem into a smaller one. Basically, as mentioned earlier, a greedy algorithm will never reconsider its choices.

This is the biggest way in which it is different from dynamic programming which happens to be exhaustive and will definitely find the solution. After each stage, dynamic programming makes decisions based on all the decisions that were taken in the previous stage and it might reconsider the previous stage's algorithmic path to the solution.

2. Optimal substructure

A problem has an optimal substructure in a case where an optimal solution to the problem contains optimal solutions to the sub-problems. This implies that it is possible to solve subproblems and build up the solutions to solve larger problems.

‍

‍

What are the characteristics of greedy algorithm?

The characteristics of greedy algorithm are:

• An ordered list of resources (like profit, cost, value, etc.) exists. They quantify constraints on a system.
• The greedy approach takes the maximum of all the resources (like the maximum profit, maximum cost, maximum value, etc.).

As an example, in the fractional knapsack problem, the maximum value or weight is taken first according to the capacity that is available. 

‍

Where can you use a greedy algorithm?

Greedy algorithms can be used to find optimal solutions in problems like Activity selection, Fractional Knapsack, Job Sequencing, and Huffman Coding. It can also be used to find ‘close to optimal’ solutions in N-P Hard problems like the Traveling Salesman Problem (TSP).

Here are some reasons why you would want to use the greedy approach:

• This approach has some tradeoffs associated with it which could make it suitable for optimization.
• The greedy approach can be used to find the most feasible solution immediately. For example, in the activity selection problem, if more activities can be carried out before finishing performing the current activity, these activities can be performed in a simultaneous fashion.
• It lets you divide a problem recursively based on a condition, without any need to combine all the solutions.

What are the advantages of greedy algorithms?

The most significant advantages of using greedy algorithms are:

• The implementation of greedy algorithms tends to be rather easy.
• Such algorithms generally have a smaller amount of time complexities.
• They can be used for the purpose of optimization or, in the case of NP-Hard problems, to find solutions that are close to being an optimal solution.

‍

What are the disadvantages of greedy algorithms?

The biggest drawback involved with making use of greedy algorithms is that it is very possible that the local optimal solution might not always be the global optimal solution.

‍

How can you prove that a greedy algorithm is optimal?

There are two ways to prove that a greedy algorithm is optimal. They are:

• ‘Greedy stays ahead’ arguments
• Exchange arguments
  

1. ‘Greedy stays ahead’ arguments

Using a ​​‘Greedy stays ahead’ argument is one of the simplest methods to prove that a greedy algorithm is correct. It shows that according to some measure, the greedy algorithm always is at least as far ahead as the optimal solution during each iteration of the algorithm. This fact can be used to prove that the greedy algorithm is optimal.

2. Exchange Arguments

This is a rather versatile technique. It essentially shows you that it is possible for you to iteratively transform any optimal solution into the solution produced by the greedy algorithm without making any change to the cost of the optimal solution, thus proving that the greedy solution is optimal.