3. Greedy Method - Introduction

hi next religious greedy met heard this is one of the strategy for solving problems just like a divide and conquer and other strategies greedy method is also one of the approach for solving a problem or a design which you can adopt for solving similar problem the problems which fits into this one you can solve all of them let us understand what this method says what is this method about this method is used for solving optimization problem what are optimization problems are problems which demands or which requires either minimum result or maximum result so for this let us know few terms I will explain it through an example suppose there is a problem B and that problem is I want to travel from one location a to location B I have to cover this journey that is my problem for any problem and making one example it can be any problem similar type now for this problem there may be more than one solutions let us say I can travel this by walk solution 1 or I can take a bike solution 2 I can take a car solution 3 I can go by train solution for and I can go by flight solution 5 and there may be more solutions it can give me more solutions so my problem is to travel from location a to location B and there are many solution you go like this or take this take this and go there but there is a constraint in a problem I say that I have to cover this journey within 2 an ass this is a condition constrain so suppose I cannot cover it if I go by walk or by car and so I can cover it only if I go by train or flight now for a problem there are many solutions but these solutions which are satisfying the can given in the problem then these type of solution becomes feasible solutions does the meaning of feasible solution a solution which is satisfying the condition given in the problem is feasible solution though for a given problem there may be many solutions this is physical solution satisfying the constraint commonly we use the term is it feasible or not feasible in the sense what satisfying our constraints or not limitations or not next if I say that I want to cover this journey in minimum cost minimum cost I want to spend as much as less possible then this becomes a minimization problem so now as the problem demands our result should be minimum then it is a minimization problem right then out of these two solutions one of the solution may be taking minimum cost suppose by train if I go this is minimum cost then this is called as optimal solution a solution which is already feasible and also giving me minimum cost that is best results that is best for the minimum is best for me then that solution is called as optimal solution and definitely for any problem there can be only one optimal solution there cannot be multiple optimal solutions that means there can be only one minimum cost minimum can be only one there can be more than one solution there can be more than one feasible solution but there will be definitely only one optimal solution this problem requires minimum result some other problems may require maximum result so if a problem requires either minimum or maximum then we call that type of problem an [Music] optimization problem optimization problem is one which requires either minimum result or maximum result so let us briefly look at the term so once again feasible solution means a solution which is satisfying some constraint optimal solution means which is achieving the objective of a problem satisfying the objective of a problem that is either minimum result or maximum result a problem which requires a minimum or maximum result is a optimization problem so greedy method is used for solving optimization problems these are the strategies used for solving optimization problems these three methods are for solving optimization problem the approach is different and every problem whichever requires optimal results some may be suitable here some may be suitable here this strategy can apply on it or some this strategy can be applied or some for some problems all three strategies can be applied on them so we will learn all these strategies through problems one by one now we are going to cover this grading method we will start with grading method you will understand what grading method says what is the approach so next I will tell you about greedy method what is this approach here is the general method of greedy I have written an algorithm now see greedy method says that a problem should be solved in stages in each stage we will consider one input from a given problem and if that input is feasible then we will include it in the solution so by including all those feasible in inputs we will get an optimal solution so in stages we will each time we'll pick up our input and we consider it and we fished it's feasible we will include it and like this if we follow this procedure we will get the optimal solution so here a general method is given if a problem is given and that problem is having an input of some size and n s the size and it is having some data some values input values now it will go through all those input values from 1 to n and each time it will select something from a and call it as X if that X is feasible that is one input one by one it will pick up the input and that input if it is feasible it will include in the solution if it is feasible it is included in solution so this comes under if this is the general method not I will explain you through example the approach of grading method is that suppose if you have to buy our best car best guy best car in the sense in terms of features you want a best car optimal optimal okay the cost will be maximum definitely so what do you want optimal optimal in the sense what in terms of features now how do you choose a best car how do you choose the best car so one method is you should look at all the brands and all the models of cars available in the world or at least in your city then you can say that I have checked all the cars so then I have selected a best car this is one approach for solving a problem and the problem is to buy a car this is one method this will be very much time consuming you have to check each and every brand and every model see the cost may not be a thing sometimes or less car may be better than cost so checking with the features and you are deciding that this is the best car so what actually what is the method we follow we first of all sort out the brands and we say that we don't want in this this we want let us say you are selecting a brand that is Toyota or Hinda right ok you are saying that these are the best brands for you and in these brands then again you will select the top models right so you had you are not looking at the lower models so again you have sought out then again you say that in this top model the latest release car or the well-known car well tested car you are picking up that then you are saying that is the best one is it really the best one out of all the cars in the market for you it is the best one so what is the approach you adopted you have adopted a greedy approach so you have your own method of selection and based on that selection method you got some result and you are saying that this is the best result that's how it is clearly and definitely when you do this you will become a best car so you don't have to waste time in checking all the cards in the available in the city available in the market so that's it so without checking all of them you say that you select few and save this is the best car no doubt that's the best car but the approach you adopted is greedy and give you one more example suppose you are running a company and you want to hire some people so when you have given an ad some thousand people came to you for the interview now you will conduct some Sai type of tests like you first you can take written test and then you have a technical test or group discussion like that you will have various phases of test and you will filter the people and finally we will select one person and you say that this is the best person out of those thousand is he really a best person yes according to your procedures it's the best person what was your selection procedure based on the selection procedure he is the best person and yes you have got the optimal solution so the approach is greedy many student complain that I was better than him and he was selected they think like that but really the person who got selected is the best one definitely so the approach that you are adopting now I'll tell you if you are selecting one person out of thousand then for all you should give a chance for return that's for all you should give it a chance for group discussion for all using you should give a chance for technical interview and HR interview then become the best one this will be very time-consuming and costly process we don't do that we simply filter the people and select the best one this approach is called as a greedy approach so we have our own methods of selection and we follow blindly we follow those method because those are the known methods when you follow known methods of solving a problem and you quickly solve it that approach is called as greedy so I have given you enough idea about the grading method now you will come across through the problems one by one I will pick up and I will solve them so in the while discussing the problem also I will show you what the approach greedy is following so that if you type find any similar type of problem you can follow the same approach and solve it that's it the introduction for grading method

Channel: Abdul Bari

Views: 1,054,816

Keywords: algorithm, algorithms, greedy method, greedy approach, introduction, what is greedy method, abdul bari, bari, gate

Id: ARvQcqJ_-NY

Length: 12min 2sec (722 seconds)

Published: Tue Feb 06 2018