Greedy Approach

GREEDY METHOD

What is greedy approach?

This approach is used to find the optimal solution from the set of obtained feasible solutions. We use objective function to find the optimal solutions. It find the solution in the ste-by-step manner. This will be obtained in a sequential greedy approach.

Key-words used in the greedy method

Objective function: it is a function which maximizes or minimizes the output.

Optimal solution:  it is a feasible solution which maximizes or minimizes the objective function.

Feasible solution: it is a solution which is obtained as the result of the objective function.

Pseudo representation of greedy algorithm:

Algorithm Greedy (a, n)

{

            Solution=ϕ    // Initialize solution

                        for i=1 to n do

                        {

                                    X: = Select (a);

                                    if Feasible (solution, x) then

                                                Solution =Union (solution, x)

                        }

    return solution;

}

 

Job scheduling using greedy approach:

In this problem we are given with the deadlines and the priority of each and every individual jobs, we have to find out which jobs are to be finished in the given consolidated time, so that the high profit jobs will completed in that stipulated time. We have to find this using the greedy approach.

Example:

 

Number of jobs will be 4

Priorities will be (p1, p2, p3, p4) = (100,10,15,27)

Deadlines will be (d1, d2, d3, d4) = (2, 1, 2, 1)

Maximum deadline is 2

SNO

FEASIBLE SOLUTION

PROCESSING SEQUENCE

VALUE

1

(1,2)

2,1

110

2

(1,3)

1,3 or 3, 1

115

3

(1,4)

4, 1

127

4

(2,3)

2, 3

25

5

(3,4)

4,3

42

6

(1)

1

100

7

(2)

2

10

8

(3)

3

15

9

(4)

4

27

The job with the less deadline must be finished first, and then the job with the highest, this can be seen in the 1st case, second job is with 1 unit of dead line, so it will we executed before 1.

When compared the value column, the highest value will be 3rd row, which consists of 1 and 4, the sequence would be 4,1 because 4th job having the less dead line than the 1st .

Solving problem of knapsack with greedy approach

In this we will be given a knapsack which has some capacity to hold the goods having some weights. We will be given with the weight and the price of every item, based on that we have to fill the knapsack with the optimal commodities. In between we will get some feasible solutions, out of them we have to choose the optimal solution.

Example:

n= 3,

weight of knapsack(m)=20

(p1,p2,p3) = (25,24,15)

(w1,w2,w3) = (18,15,10)

Note down the items in the decreasing order of their profits.

Selection set will be w1, w2, and w3.

ITRM

PROFIT

WEIGHT

REMAINING WEIGHT

1

25

18

20-18=2

2

24

15

Remaining is 2, so cannot be put into bag

So, optimal solution is only placing item1 in the knapsack.

Huff-man coding

It is used for the compression of code, in this we will be given with the string, out of which we have to find out the frequencies of every letter.

Example:

O P E N S E N S E

Mark o on left and 1 on right

Write the code by travelling in top down approach.

By applying the Huffman coding principles, take the least two frequencies first,

take the next least frequency N or S.

 

Check for the frequency which is greater than 4, if found go with adding in the left side, else split the tree.

Repeat the process same for the next two frequencies.

Done with all the nodes, so combine the two trees,  

Now make the table with the modified code value,  

ALPHABET

CODE

FREQUENCY

TOTAL BITS

O

110

1

1*3

P

111

1

1*3

E

01

3

3*2

N

10

2

2*2

S

00

2

2*2

By this the length is reduced by 7 units.

MINIMUM SPANNING TREE

The tree is a connected graph with no cycles is formed in it. if G(V, E) be an undirected connected graph. A sub graph t = (V,EI ) of G is a spanning tree of G iff  t is a tree. The spanning tree consists of all the vertices in the graph.

The given graph consists of so many spanning trees, but the graph which has the least cost is considered to be the minimum spanning tree.

Algorithms used to find the minimum spanning tree

  • Prims
  • Kruskal

Prims

Steps involved in finding the minimum spanning tree:

  1. Start the procedure with the selection the edge which has the minimum weight.
  2. Select the next edge which consists of two vertices among which one is already included in the tree and the other is not.
  3. Repeat the process until the tree contains n-1 edges.

Time complexity of prim’s algorithm is O(n2).

Example:

Kruskal algorithm

Steps involved in finding the minimum spanning tree:

  1. Start the procedure with the selection the edge which has the minimum weight.
  2. Select the next minimum edge
  3. Repeat the process until the tree contains n-1 edges.

Time complexity of prim’s algorithm is O(ElogE).

Example:

Contributor's Info

Created: Edited:
0Comment
What is Greedy algorithm?|How can we decide which option is optimal? | How to create a Greedy algorithm?

                                                          CONTENTS

List of topics that we cover in the article:

  • Introduction
  • What is Greedy algorithm?
  • How can we decide which option is optimal?
  • How to create a Greedy algorithm?
  • Implementation
  • Time complexity
  • Where to use Greedy algorithm
  • Examples
  • Conclusion

 

GREEDY ALGORITHMS

  • Introduction:

          Different problems can be solved by different techniques. A programmer uses different kind of techniques based on the problem. Mainly programmers use the following techniques:

  • Divide and Conquer
  • Greedy algorithms
  • Dynamic programming
  • What is greedy algorithm?

          The main goal of greedy algorithm is to gain optimal solution for the problem. We choose a solution which is very closest that provide optimal solution. Greedy algorithm always tries to find the local optimal solution leads to global optimal solution.

For example, if you consider the concept of Counting coins

This problem is to count the value by choosing least possible coins

Suppose let’s think coins we have 1, 2, 3, 5, 10 and we must count 21 the procedure will be like:

  • pick one 10 coin, the remaining count is 11
  • Then select 5 coin, the remaining count is 6
  • And, then select one 3 coin, the remaining count is 3
  • Then select one 2 coin, the remaining count is 1
  • Finally, select one 1 coin, it will solve the problem.

Now it may look everything is good and the problem is solved but if we changed the problem statement we may not get the optimal solution. Suppose we have coins of 1, 2, 7, 10 now to make count of 20 is very easy and it gives optimal solution but when you give count of 16 it is not possible.

  • How can we decide which option is optimal?

          Let’s think that you have a problem function that needs to be optimized.       To make the problem optimal the greedy algorithm creates choices.         The most important factor is the greedy algorithm will never goes back    and changes the decision.

 

  • How to create a greedy algorithm?
  • Many of us are interested to do many things but we don’t have enough time to do. In this case perform greedy algorithm. In this algorithm we must select the things which take minimum time to complete the calculation by maintaining two variables a and b.
  • In this you will be given array A of integers where the elements indicate time for completion.

We must do the following:

  • Sort the array in ascending order.
  • Perform each item one by one.
  • Now add the time that will complete the thing into a
  • Add one to b.

 Repeat this until a is less than or equal to T

A={1,6,4,8,2} and T=6.

After sorting A={1, 2, 4, 6, 8}

  • Example:

 

Let’s take an example how the greedy algorithm makes the locally optimal choices and ending with non-optimal solution.

The main aim is to find the largest sum from root node to leaf node

  • Start from the root node 3
  • Now, there are two chances 4 and 7 we want largest sum so select 7 and then select again the largest element 11
  • Sum is 3+7+11=21
  • Check any other possibility which gives largest sum : select 3 4 and 20 sum is 3+4+20=27
  • Actual answer is 27
  • By this we can conclude that locally optimal choices doesn’t give us a globally optimal value.
  • Implementation:

# include<stdio.h>

Void greedyAlgorithm(int c);

int main(void)

{

int channgeOwed;

printf(“how much change is owed”);

scanf(“%d”, changeowed);

greedyAlgorithm(changeowed);

system("pause");

}

Void greedyAlgorithm(int c)

{

int num1=0, num2=0, num3=0, num4=0, count=0;

while(c>=25)

{

num1++;

c = c-25;

}

while(c>=10)

{

num2++;

c = c-10;

}

while(c>=5)

{

num3++;

c = c-5;

}

while(c>=1)

{

num4++;

c = c-1;

}

​printf("%d",num1);

​printf("%d",num2);

​printf("%d",num3);

​printf("%d",num4);

}

  • Algorithm:

Algorithm(p, t, n)

{

For i from 1 to N;

s[i]=(p[i]/t[i].i)

sort(s)

C=0

F=0

For I from i to N:

C= C+T[s[i].second]

F= F+p[s[i].second]*c

Return F

}

  • Time complexity:

Time complexity for the above 2 for loops takes O(N) and one sorting function takes O(N*logN). Therefore all over the time complexity is O(2*N+N*logN)=O(N*logN)

 

  • Where to use greedy algorithm:

Greedy algorithm will work when the problem contains the following:

  • The problem will contain the optimal solution and the sub problems will also have the optimal solution.
  • It is having greedy properties.
  • It is hard to prove the correctness.
  • Examples:

Greedy algorithm is the most powerful algorithm and works efficiently for all type of problems. There are some examples for greedy algorithm

  • Dijkstra’s algorithm
  • Minimum spanning Tree
  • Prims minimal spanning tree algorithm
  • Kruskal’s minimum spanning tree algorithm
  • Knapsack problem
  • Travelling salesman problem
  • Disadvantage:

In greedy algorithm it is very hard to prove the correctness. Though it is the correct very difficult to prove why it is correct.

 

  • Conclusion:

Greedy algorithm always search for the optimal solution for problem generally greedy algorithms will not have globally optimized solutions. In greedy algorithm it is very easy to find the solution analysing the runtime for greedy algorithm is very much easy compared to other techniques like divide and conquer.

Contributor's Info

Created:
0Comment