Greedy Algorithms

Introduction:

The Greedy algorithm is an easy, intuitive strategy or approach that is used for solving Optimization problems. It is an algorithmic paradigm that builds up an answer step by step, continuously selecting the next step that provides the most obvious and immediate benefit and is also the best fit for the given problem. A Greedy solution yields a locally optimal solution that relatively yields a globally optimal solution in a rational amount of time. The Greedy algorithm has only one shot to work out the optimal solution in order that it never goes back and reverses the decision made.

Optimization Problems:

Optimization problems are a type of problem for finding the best solution from all feasible solutions. It is a type of problem that demands or requires either minimum result or maximum result. For a given problem, there can be only one optimal solution out of the numerous feasible solutions. There are different approaches followed to solve the Optimization problems. Some of them are mentioned below:

1. Greedy Algorithm
2. Dynamic Programing
3. Branch and Bound

Structure of a Greedy Algorithm

Greedy algorithm says that the problem needs to be solved in stages. In each stage, we will consider one input given in the problem and if that input is feasible, we’ll include it in the solution. So by including all such feasible inputs in the solution and following the procedure, we’ll get an optimal solution.

In the animation below, the set of data is all of the numbers in the graph, and the rule was to select the largest number available at each level of the graph. The solution that the algorithm provides is the sum of all of those choices.

With a goal of reaching the largest sum, at each step, the greedy algorithm will choose what appears to be the optimal immediate choice, so it will choose 12 instead of 3 at the second step and will not reach the best solution, which contains 99. (Gif courtesy: brilliant.org)

Creating A Greedy Algorithm:

In the following pseudo-code, a problem is given with input size 5 and a few input values. Now, the function will go throughout the length of input values and every time it’ll select one input from ‘a’ and call it ‘x’. If x is feasible, then it’ll include it in the solution. This is the general method of solving problems using the Greedy approach.

Pseudo code:

n = 5

a = a1, a2, a3, a4, a5

Algo Greedy(a, n)

{

for i = 1 to n do

{

x = select(a);

if feasible(x) then

solution += x;

}

}

In general, the greedy approach has 5 components:

1. A candidate set, from which a solution is formed.
2. A selection function, which chooses the candidate to be appended to the solution.
3. A feasibility function, that checks if a candidate can be a part of the solution.
4. An objective function, which adds the chosen value to a solution.
5. A solution function, which indicates the complete solution that we have found.

Greedy algorithms produce good solutions to some mathematical or programming problems, but not to others. Most of the problems for which they work will have mainly these two properties:

Greedy choice property

We can make any choice that seems best at the instant and then solve the arising subproblems later. The choice made by a greedy algorithm may rely upon choices made so far in the past, but not on future choices or all the solutions to the subproblem. It iteratively makes one greedy choice after another, reducing each given problem into a smaller one. In clear words, a greedy algorithm never reconsiders its choices. This is the main difference between dynamic programming and greedy algorithm. Dynamic programming is very thorough and is certain to find the solution. After every stage, dynamic programming makes decisions based on all the decisions made in the previous stages and may even reconsider the previous stage’s algorithmic path to find a solution.

Optimal substructure

A problem has an optimal substructure if an optimal solution to the entire problem is comprised of the optimal solutions to the numerous sub-problems.

Advantages of Greedy Algorithms:

1. It is rather easy to come up with a solution using the greedy algorithm (or even multiple greedy algorithms) for the given problem.
2. Analyzing the run time for greedy algorithms will generally be much easier than that for other techniques, like Divide and conquer. For the Divide and conquer technique, it is not clear whether the technique is fast or slow. This is because at each level of recursion the size of input gets smaller and the number of sub-problems increases.

Limitations of Greedy Algorithms:

1. The disadvantageous part is that for greedy algorithms you have to work much harder to understand correctness issues. Even with the correct algorithm, it is hard to prove why it is correct.
2. Sometimes, for many other problems, greedy algorithms fail to produce the optimal solution, and may even produce the unique worst possible solution because they do not take into consideration all the future data. The choice made by a greedy algorithm may depend on choices it has made so far in the past, but it is not aware of future choices it could make.

Types/Variations of Greedy Algorithm:

Greedy Approaches are ideal only for problems that have ‘optimal substructure’. They are often described as being ‘short sighted’ or even ‘irrecoverable’. In spite of these facts, for many simple problems, one of the best-suited strategies is greedy algorithms. There are also a few variations to the greedy algorithm as listed below:

• Pure greedy algorithms
• Orthogonal greedy algorithms
• Relaxed greedy algorithms

Applications of Greedy Algorithm:

The greedy approach is sort of powerful and works well for a good range of problems. Many algorithms or techniques can be viewed as applications of Greedy algorithms, such as:

1. Minimum Spanning Tree or MST (Using Kruskal’s algorithm and Prim’s Algorithm)
2. Dijkstra’s Algorithm for finding the shortest path from a single source using graph
3. Huffman Coding (data compression codes)

Thank You for investing your time!

Resources:

wikipedia.com

brilliant.org