Greedy Algorithm

What is the Greedy algorithm?

In the greedy algorithm approach, decisions are made from the given solution domain. As being greedy, the closest solution that seems to provide an optimum solution will be chosen. Greedy algorithms try to find a localized optimum solution, which may eventually lead to globally optimized solutions.

In the Greedy Algorithm, a set of resources are recursively divided based on the maximum, immediate availability of that resource at any given stage of execution.

By using the greedy algorithm, there are two stages:

1. Scanning the list of items.
2. Optimization.

Two conditions define the greedy paradigm.

• Each stepwise solution must structure a problem towards its best-accepted solution.
• It is sufficient if the structuring of the problem can halt in a finite number of greedy steps.

History of the Greedy algorithm:

• Greedy algorithms were conceptualized for many graph walk algorithms in the 1950s.
• Edger Djikstra conceptualized the algorithm to generate minimal spanning trees. He aimed to shorten the span of routes within the Dutch capital, Amsterdam.
• In the same decade, Prim and Kruskal achieved optimization strategies that were based on minimizing path costs along weighed routes.
• In the ’70s, American researchers, Cormen, Rivest, and Stein proposed a recursive substructuring of greedy solutions in their classical introduction to algorithms book.
• The Greedy search paradigm was registered as a different type of optimization strategy in the NIST records in 2005.
• To date, protocols that run the web, such as the open-shortest-path-first (OSPF) and many other network packet switching protocols use the greedy strategy to minimize time spent on a network.

Characteristics of the Greedy Approach

The important characteristics of a Greedy method algorithm are:

• There is an ordered list of resources, with costs or value attributions. These quantify constraints on a system.
• You will take the maximum quantity of resources in the time a constraint applies.
• For example, in an activity scheduling problem, the resource costs are in hours, and the activities need to be performed in serial order.

Why use the Greedy Approach?

Here are the reasons for using the greedy approach:

• The greedy approach has a few tradeoffs, which may make it suitable for optimization.
• One prominent reason is to achieve the most feasible solution immediately. In the activity selection problem (Explained below), if more activities can be done before finishing the current activity, these activities can be performed within the same time.
• Another reason is to divide a problem recursively based on a condition, with no need to combine all the solutions.
• In the activity selection problem, the “recursive division” step is achieved by scanning a list of items only once and considering certain activities.

Examples:

1. machine scheduling
2. Fractional Knapsack Problem
3. Minimum Spanning Tree
4. Huffman Code
5. Job Sequencing
6. Activity Selection Problem

The architecture of the Greedy approach:

• Scan the list of activity costs, starting with index 0 as the considered Index.
• When more activities can be finished by the time, the considered activity finishes, start searching for one or more remaining activities.
• If there are no more remaining activities, the current remaining activity becomes the next considered activity. Repeat step 1 and step 2, with the new considered activity. If there are no remaining activities left, go to step 4.
• Return the union of considered indices. These are the activity indices that will be used to maximize throughput.

Architecture

Greedy algorithm with an example:

Being a very busy person, you have exactly T time to do some interesting things and you want to do maximum such things.

You are given an array A of integers, where each element indicates the time a thing takes for completion. You want to calculate the maximum number of things that you can do in the limited time that you have.

This is a simple Greedy-algorithm problem. In each iteration, you have to greedily select the things which will take the minimum amount of time to complete while maintaining two variables currentTime and numberOfThings. To complete the calculation, you must:

1. Sort array A in non-decreasing order.
2. Select each to-do item one-by-one.
3. Add the time that it will take to complete that to-do item into currentTime.
4. Add one to numberOfThings.

Repeat this as long as the currentTime is less than or equal to T.

Let A = {5, 3, 4, 2, 1} and T = 6

After sorting, A = {1, 2, 3, 4, 5}

After the 1st iteration:

• currentTime = 1
• numberOfThings = 1

After the 2nd iteration:

• currentTime is 1 + 2 = 3
• numberOfThings = 2

After the 3rd iteration:

• currentTime is 3 + 3 = 6
• numberOfThings = 3

After the 4th iteration, currentTime is 6 + 4 = 10, which is greater than T. Therefore, the answer is 3.

Implementation

#include <iostream>

#include <algorithm>

using namespace std;

const int MAX = 105;

int A[MAX];

int main()

{

int T, N, numberOfThings = 0, currentTime = 0;

cin >> N >> T;

for(int i = 0;i < N;++i)

cin >> A[i];

sort(A, A + N);

for(int i = 0;i < N;++i)

{

currentTime += A[i];

if(currentTime > T)

break;

numberOfThings++;

}

cout << numberOfThings << endl;

return 0;

}

Greedy algorithm Advantages:

• Always taking the best available choice is usually easy. It usually requires sorting the choices.
• Repeatedly taking the next available best choice is usually linear work. But don’t forget the cost of sorting the choices.
• Much cheaper than an exhaustive search. Much cheaper than most other algorithms.

Disadvantages of Greedy Algorithms:

It is not suitable for Greedy problems where a solution is required for every subproblem like sorting.

In such Greedy algorithm practice problems, the Greedy method can be wrong; in the worst case even lead to a non-optimal solution.

Therefore the disadvantage of greedy algorithms is using not knowing what lies ahead of the current greedy state.

Below is a depiction of the disadvantage of the Greedy method:

In the greedy scan shown here as a tree (higher value higher greed), an algorithm state at value: 40, is likely to take 29 as the next value. Further, its quest ends at 12. This amounts to a value of 41.
However, if the algorithm took a sub-optimal path or adopted a conquering strategy. then 25 would be followed by 40, and the overall cost improvement would be 65, which is valued 24 points higher as a suboptimal decision.

Summary

• Greedy algorithms can be a fast, simple replacement for exhaustive search algorithms.
• Greedy algorithms require optimal local choices.
• If locally optimal choices lead to a global optimum and the subproblems are optimal, then greed works. And some other times too.