Greedy Algorithms

Introduction

A greedy algorithm is an algorithm which makes locally-optimal choice such that this choice will lead to a globally-optimal solution. It is usually used in optimization problems.Since the algorithm always goes for the local best choice to produce the global best result therefore it may not produce the best results for all the problems.

Now the question is when and where should we use this greedy algorithm? If an optimal solution to the problem can be found by choosing the best choice at each step without reconsidering the previous steps once chosen, the problem can be solved using a greedy approach. If the optimal overall solution to the problem corresponds to the optimal solution to its sub-problems, then the problem can be solved using a greedy approach

This algorithm may not produce the best result for all the problems. It’s because it always goes for the local best choice to produce the global best result.

However, we can determine if the algorithm can be used with any problem if the problem has the following properties:

1. Greedy Choice Property

If an optimal solution to the problem can be found by choosing the best choice at each step without reconsidering the previous steps once chosen, the problem can be solved using a greedy approach. This property is called greedy choice property.

2. Optimal Substructure

If the optimal overall solution to the problem corresponds to the optimal solution to its sub-problems, then the problem can be solved using a greedy approach. This property is called optimal substructure.

Advantages of Greedy Approach

Some advantages of greedy algorithms are that

● The algorithm is easier to describe.

● This algorithm can perform better than other algorithms (but, not in all cases).

● This can be used for optimization purposes or finding close to optimization in case of NP Hard problems

● The greedy method is considered to be cheaper than most of the other algorithmic paradigms.

Drawback of Greedy Approach

As mentioned earlier, the greedy algorithm doesn’t always produce the optimal solution. This is the major disadvantage of the algorithm

For example, suppose we want to find the longest path in the graph below from root to leaf. Let’s use the greedy algorithm here.

Greedy Approach

1. Let’s start with the root node 20. The weight of the right child is 3 and the weight of the left child is 2.

2. Our problem is to find the largest path. And, the optimal solution at the moment is 3. So, the greedy algorithm will choose 3.

3. Finally the weight of an only child of 3 is 1. This gives us our final result 20 + 3 + 1 = 24.

However, it is not the optimal solution.

Optimal Approach

There is another path that carries more weight (20 + 2 + 10 = 32) as shown in the image below.

Therefore, greedy algorithms do not always give an optimal/feasible solution.

Different Types of Greedy Algorithms

1. Job Sequencing Problem

2. Huffman Coding

3. Fractional Knapsack

4. Travelling salesman problem(TSP)

Few applications of greedy algorithms are activity selection problem, fractional knapsack, job sequencing problem, Huffman coding.

Job Sequencing Problem

Let us take the job sequencing problem which states that given an array of jobs where every job has a deadline and associated profit if the job is finished before the deadline, we have to maximize the total profit if only one job can be scheduled at a time. It is also given that every job takes a single unit of time, so the minimum possible deadline for any job is 1. We solve this problem by

● sorting all the jobs based on their deadlines.

● Iterate from the end and calculate the available slots between every two consecutive deadlines. Include the profit, deadline, and job ID of ith job in the max heap.

● While the slots are available and there are jobs left in the max heap, include the job ID with maximum profit and deadline in the result.

● Sort the result array based on their deadlines.

Pseudo Code:

for i = 1 to n do
   Set k = min(dmax, DEADLINE(i)) //where DEADLINE(i) denotes  deadline of ith job
   while k >= 1 do
      if timeslot[k] is EMPTY then
         timeslot[k] = job(i)
         break
      endif
         Set k = k — 1
   endwhile
endfor

Huffman Coding

Another example where a greedy algorithm is used is in Huffman

Coding.Huffman coding is a lossless data compression algorithm. The idea is to assign variable-length codes to input characters, lengths of the assigned codes are based on the frequencies of corresponding characters. The most frequent character gets the smallest code and the least frequent character gets the largest code. Here the steps to solve this is

1. Build a Huffman Tree from input characters.

2. Traverse the Huffman Tree and assign codes to characters.

We build the Huffman tree

1. Create a leaf node for each unique character and build a min heap of all leaf nodes (Min Heap is used as a priority queue. The value of the frequency field is used to compare two nodes in the min heap. Initially, the least frequent character is at root)

2. Extract two nodes with the minimum frequency from the min heap.

3. Create a new internal node with a frequency equal to the sum of the two nodes frequencies. Make the first extracted node as its left child and the other extracted node as its right child. Add this node to the min heap.

4. Repeat steps#2 and #3 until the heap contains only one node. The remaining node is the root node and the tree is complete.

Pseudo Code:

Procedure Huffman(C): // C is the set of n characters and related information
n = C.size
Q = priority_queue()
for i = 1 to n
   n = node(C[i])
   Q.push(n)
end for
while Q.size() is not equal to 1
   Z = new node()
   Z.left = x = Q.pop
   Z.right = y = Q.pop
   Z.frequency = x.frequency + y.frequency
   Q.push(Z)
end while
Return Q

Fractional Knapsack

In the fractional knapsack problem given are 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.Unlike 0–1 knapsack here 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.

Pseudo Code:

Algorithm: Greedy-Fractional-Knapsack (w[1..n], p[1..n], W)
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

Traveling Salesman Problem

In the traveling salesman problem we are trying to find out the path/route with the minimum cost such that our aim of visiting all cities once and returning back to the source city is achieved. As a form of input we are given a 2-D matrix tsp[][] which contains the graph.We solve this problem using the following steps

1. Create two primary data holders:

○ A list that holds the indices of the cities in terms of the input matrix of distances between cities.

○ Result array which will have all cities that can be displayed out to the console in any manner.

2. Perform traversal on the given adjacency matrix tsp[][] for all the city and if the cost of reaching any city from the current city is less than current cost the update the cost.

3. Generate the minimum path cycle using the above step and return their minimum cost.

Pseudo Code:

Algorithm: Traveling-Salesman-Problem
C ({1}, 1) = 0
for s = 2 to n do
   for all subsets S Є {1, 2, 3, … , n} of size s and containing 1
   C (S, 1) = ∞
   for all j Є S and j ≠ 1
       C (S, j) = min {C (S — {j}, i) + d(i, j) for i Є S and i ≠ j}
Return minj C ({1, 2, 3, …, n}, j) + d(j, i)

Greedy Method Applications

1. The greedy method is used to find the shortest distance between two vertices with the help of Dijkstra’s algorithm.

2. The greedy method is highly used in the scheduling process in the CPU and to use the CPU to its maximum extent. The purpose of the greedy method here is to find an optimal solution to maximize CPU utilization.

3. The greedy method is also used in the non-preemptive algorithm such as the shortest job first algorithm. This algorithm prioritizes the process with the lowest burst time.

4. The traveling salesman problem is another application of the greedy method, the objective here is to find the shortest path possible.

5. Few algorithms like the bin packing problem, Egyptian fraction, and minimum spanning trees could be solved best using the greedy method.

Conclusion

The greedy method is one of the most important techniques for designing algorithms. This is primarily because it has many real-world applications and it applies to a wide variety of problems. Sometimes we can solve a problem using a greedy approach but it is hard to come up with the right strategy. And demonstrating the correctness of greedy algorithms (for exact or approximated solutions) can be very difficult.

References:

1. https://www.analyticssteps.com/blogs/introduction-greedy-method-and-its-applications

2. https://www.hackerearth.com/practice/algorithms/greedy/basics-of-greedy-algorithms/tutorial/

3.https://www.tutorialspoint.com/data_structures_algorithms/greedy_algorithms.html

4. https://www.geeksforgeeks.org/job-sequencing-problem/

5. https://www.geeksforgeeks.org/huffman-coding-greedy-algo-3/

TY-ET-A

Atharva Mali (30)

Laukik Avhad (31)

Avinash Gedam (32)

Manas Baviskar (40)