Greedy Algorithms

A greedy algorithm is an approach for solving a problem by selecting the best option available at the moment. A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. It doesn’t worry whether the current best result will bring the overall optimal result.

The algorithm never reverses the earlier decision even if the choice is wrong. It works in a top-down approach. The algorithm makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution.

Generally, greedy algorithms do not provide globally optimized solutions.

MST construction using Greedy approach

Characteristics:

• There is an ordered list of resources(profit, cost, value, etc.)
• Maximum of all the resources(max profit, max value, etc.) are taken.

Advantages:

• Greedy approach is easy to implement.
• Typically have less time complexities.
• Greedy algorithms can be used for optimization purposes or finding close to optimization in case of NP Hard problems.

Disadvantages:

• The local optimal solution may not always be global optimal.

Applications:

• Finding optimal solutions: Fractional Knapsack, Job Sequencing, Huffman Coding, constructing MST.
• Finding close to the optimal solution for NP-Hard problems like TSP.

Approximate TSP solution:

Given a set of cities and the distance between every pair of cities, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point. Both brute force and DP solutions are infeasible, and in fact, there is no polynomial time solution available for this problem as the problem is a known NP-Hard problem.
But we can design an approximate algorithm for TSP that returns a tour whose cost is never more than twice the cost of an optimal tour. The idea is to use Minimum Spanning Tree (MST) which is constructed using Greedy approach.

Construction of MST

Algorithm:
1) Let 1 be the starting and ending point for salesman.
2) Construct MST from with 1 as root using Prim’s Algorithm.
3) List vertices visited by DFS of the constructed MST and add 1 at the end.

Fractional Knapsack:

We are given weights and values of n items, we need to put these items in a knapsack of capacity W to get the maximum total value in the knapsack and we can break items for maximizing the total value of knapsack.
The basic idea of the greedy approach is to calculate the ratio value/weight for each item and sort the item on basis of this ratio. Then take the item with the highest ratio and add them until we can’t add the next item as a whole and at the end add the next item as much as we can. Which will always be the optimal solution to this problem.

Algorithm:
for i = 1 to n 
   do x[i] = 0 
weight = 0 
for i = 1 to n 
   if weight + w[i] ≤ W then  
      x[i] = 1 
      weight = weight + w[i] 
   else 
      x[i] = (W - weight) / w[i] 
      weight = W 
      break 
return x

Conclusion:

Greedy algorithm refers to a class of algorithms that use a greedy approach to find the optimal solution to some optimization problem. A correct greedy algorithm is very fast and efficient as compared to other algorithms, such as dynamic programming. Although greedy algorithm do not always lead to the global optimal solution. All problems which can be solved using a greedy approach exhibit greedy choice and optimal substructure properties.