Greedy algorithm is an algorithm technique which always takes the best immediate, or local, solution while finding an answer.It is a mathematical process that looks for simple, easy-to-implement solutions to complex, multi-step problems by deciding which next step will provide the most obvious benefit ( perhaps why it is called greedy). so greedy is a strategy to solve the complex problem or you can say optimization problem in simple and quicker way. This strategy has following to characteristics

1. Greedy-choice property: A global optimum can be arrived at by selecting a local optimum.
2. Optimal substructure: An optimal solution to the problem contains an optimal solution to sub problems.

Limitation:     It may not be the best solution and sometimes may even be the worst possible.

According to wikipedia “a greedy algorithm is an algorithm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum”. here problem solving heuristic means  a technique designed for solving problems more quickly when classic methods are too slow, or for finding an approximate solution when classic methods fail to find any exact solution and local optimal means nearest best solution. global optimum means finding optimal solution of complex problem.

Below is the list of famous greedy algorithms

  • Prism’s algorithm
  • Kruskal algorithm
  • Reverse-Delete algorithm
  • Dijkstra’s algorithm
  • Huffman coding

EXAMPLE PROBLEM : ACTIVITY SELECTION PROBLEM (Activity selection problem is an example of greedy algorithm)

An activity-selection is the problem of scheduling a resource among several competing activity.Given M activities with their start and finish times,we have to find the maximum number of activities that can be performed by a single person,assuming that a person can only work on a single activity at a time.

GREEDY ALGO STEPS

a) Sort the activities according to their finishing time
b) Select the first activity from the sorted array and print it.
c) Do following for remaining activities in the sorted array.
d) If the start time of this activity is greater than the finish time of previously selected activity then select this activity and print it.

Consider the following 6 activities.
s_time[] = {1, 3, 0, 5, 3, 5, 6, 8, 8, 2}; // start time
f_time[] = {4, 5, 6, 7, 9, 9, 10, 11, 12, 18}; // finish time ,

The below c code gives The maximum set of activities that can be executed  by a single person according to set of activities with start time and finish time.

#include<stdio.h>

void Activities(int s_time[], int f_time[], int n)
{
int i, j;
printf ("Selected Activities are:");
i = 1; printf("A%d ", i);
for (j = 1; j < n; j++) { if (s_time[j] >= f_time[i]) {
printf ("A%d ", j+1); i = j;
}
}
}

int main() {
int s_time[] = {1, 3, 0, 5, 3, 5, 6, 8, 8, 2};
int f_time[] = {4, 5, 6, 7, 9, 9, 10, 11, 12, 18};
int n = sizeof(s_time)/sizeof(s_time[0]);
Activities(s, f, n);
return 0;
}

References:
Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein



Related Contents to follow