Analysis Design Of Algorithm (ADA) | Greedy Strategy

📌Highlights: Hi Friends ! In this post we know about concept of greedy approach such as What is greedy approach ?, Why it is used ?, What is the benefit of this approach, What are the different algorithm under this approach?

We know the general meaning of greedy (lalchi) (desire to get more) . Here greedy is one of the approach that is used to solve the problems. There are variety of problems that need to solve in our daily life. So many decision are taken to solve the problem.

We know to solve any problem there are more than one solutions. But it is not necessary that all solutions are appropriate to solve the problem. We always optimum solution that is feasible for us. 

Let us understand what the greedy method says, this method is adopted to solving optimisation problem. A problem which require either minimum or maximum result is called optimisation problem.

For example,

Suppose you make a plan for any trip. But for this trip you have only two days and limited money.

Problem Statement is you make a plan for any trip.

Constraints are But for this trip you have only two days and limited money (less time & less money)

Selection Strategy, Under this strategy you will find all the possible way (solutions) to go for trip such as.

by walk | by bike | by car | by train | by flight and so on...

Now analysis which strategy satisfy the available constraints such as less time & less cost.

Now we take one by one.

👉 If we go by walk than definitely we will not reach on time ( not a good idea) 

👉 If we go by bike again the same problem.

👉 If we go by car trip become costly and risky may also time problem.

👉 If we go by train than definitely we will reach on time with less cost.

👉 If we go by flight than definitely we will reach on time with more cost.

So on the above analysis we find the moderate (neither min nor max) solution is go by train because reach on time with less cost. 

Now we see we have so many solutions to solve this problem but we have some constraints such as trip must complete with in time limit such as by train / flight .

If we choose these solution than that is known as feasible solution. The condition that satisfy the given problem is called feasible solution.

Now if we want to solve the problem in minimum cost than it we call as minimisation  problem.

By the above solution there should be minimum cost from one of them such as by train is minimum.

So we can say that the solution which is feasible and having minimum cost is called optimal solution and for any problem there must be only one solution not more than one.

That problem which generate either minimum result or maximum result is called optimisation problem.

So we can say that greedy method is used to solve optimisation problem.

Following strategy are used to solve optimisation problem:

👉 Greedy Method

👉 Dynamic Programming

👉 Branch and Bound Method.

Following application are used Greedy Method such as:

👉 Knapsack Problem

👉 Job Sequencing with deadline.

👉 Minimum spanning Tree.

👉 Optimal Merge Problem.

👉 Huffman Coding.

👉 Dijkstra's Algorithm (Single Shortest Path).

General Method of Greedy is:

algorithm Greedy (s, num)

{

    for j = 1 to n do

    {

        y = select (s);

        feasible (y) then

        sol =sol + y;

    }

}

📌Now Friends ! it is the end of this post, I hope you all understand the concept of Greedy Strategy.I am try to explain in very simple and general way so that any non technical person can understand. We will meet in next post till continue reading ...