/    /  DAA- The general method of Greedy

The general method of Greedy

 

Greedy Method:

Following are a few points about the greedy method.

  • The first note point is that we have to find the best method/option out of many present ways.
  • In this method, we will be deciding the output by focusing on the first stage. We don’t think about the future.
  • The greedy method may or may not give the best output.

A greedy Algorithm solves problems by making the choice that seems to be the best at that particular moment. There are many optimization problems that can be determined using a greedy algorithm. A greedy algorithm may provide a solution that is close to optimal to some issues that might have no efficient solution. A greedy algorithm works if a problem has the following two properties:

  1. Greedy Choice Property: By creating a locally optimal solution we can reach a globally optimal solution. In other words, by making “greedy” choices we can obtain an optimal solution.
  2. Optimal substructure: Optimal solutions will always contain optimal subsolutions. In other words, we say that the answers to subproblems of an optimal solution are optimal.

 

Examples:

Following are a few examples of Greedy algorithms

  • Machine scheduling
  • Fractional Knapsack Problem
  • Minimum Spanning Tree
  • Huffman Code
  • Job Sequencing
  • Activity Selection Problem

 

Components of Greedy Algorithm

Greedy algorithms consist of the following five components −

  • A candidate set − A solution is created with the help of a candidate set.
  • A selection function − It is used to choose the best candidate that is to be added to the solution.
  • A feasibility function − A feasibility function is useful in determining whether a candidate can be used to contribute to the solution or not.
  • An objective function − This is used to assign a value to a solution or a partial solution.
  • A solution function − A solution function is used to indicate whether a complete solution has been reached or not.

 

Areas of Application

The greedy approach is used to solve many problems. Out of all the problems, here we have a few of them as follows:

  • One of the applications could be finding the shortest path between two vertices using Dijkstra’s algorithm.
  • Another is finding the minimal spanning tree in a graph using Prim’s /Kruskal’s algorithm

 

Greedy Algorithm:

getOptimal(Item, array[], int num)
 Initialize empty result as, result = {}  
 While (All items are not considered)

  // In order to select an item we make a greedy here.
  j = SelectAnItem() 

  // If j is feasible, add j to the result
  if (feasible(j))
    result = result U j
return result

 

Why should we choose a greedy algorithm?

The greedy approach has a few characteristics that might make it suitable for optimization. One reason to choose a greedy algorithm is to achieve the most feasible solution immediately. If we take the activity selection problem as a reference that is explained below. We can observe that if more activities can be done before finishing the current activity, then these activities can be performed within the same time.

Another reason to choose this algorithm is to divide a problem recursively based on a condition. This ensures that there is no need to combine all the solutions. While considering the activity selection problem, we achieve the “recursive division” step by scanning a list of items only once and considering certain activities.

Greedy choice property: Greedy Choice property tells us that we can obtain a globally optimal solution by obtaining a solution that is either a locally optimal solution or a Greedy solution. The choice made by a Greedy algorithm may depend on the earlier choices but will never depend on the future. A Greedy choice is made one after another and this helps to reduce the given problem to a smaller one.

Optimal substructure: A problem is said to exhibit an optimal substructure if and only if an optimal solution to the problem also contains the optimal solutions to the subproblems. That means we can solve subproblems and build up the solutions which could help us to solve larger problems.

NOTE:  Making locally optimal choices might not work always. Hence, from this point, it is understandable that Greedy algorithms might not always give the best solutions.

 

Characteristics of Greedy approach 

  1. The greedy approach consists of an ordered list of resources(profit, cost, value, etc.) 
  2. The greedy approach takes the maximum of all the resources(max profit, max value, etc.) 
  3. For example, in the case of the fractional knapsack problem, the maximum value/weight is taken first based on the available capacity. 

 

Applications of Greedy Algorithms 

  1. To find an optimal solution (Activity selection, Fractional Knapsack, Job Sequencing, Huffman Coding). 
  2. To find close to the optimal solution for NP-Hard problems like TSP. 

 

Advantages and Disadvantages of Greedy Approach 

Following are the various advantages and disadvantages of the greedy approach.

Advantages 

  • It is easy to implement.
  • Has fewer time complexities.
  • Can be used for the purpose of optimization or finding close to optimization in the case of NP-Hard problems.

Disadvantages 

  • One disadvantage of this algorithm is that the local optimal solution may not always be globally optimal.