Hello friends, welcome to Gate Smashers In this video we are going to discuss
introduction to greedy algorithms or what you can call greedy techniques which is a very important topic in algorithm So guys, like the video quickly, subscribe
the channel if you haven't done it yet and please press the bell button so that
you get all the latest notifications So let's start what is actually a greedy
technique or what are greedy algorithms Algorithms which follow local optimal choice at each stage with intent of finding the global optimum What does it mean to say? We go towards the best choice at every stage locally Like we see with a simple example Let's say this is my source I have multiple paths from this source And these paths take me to some destination Let's say this is my destination D This is my source and that is my destination Now if we talk here, as soon as I started from the source I am at this stage It is saying that it follows the local optimal choice What does local optimal choice mean? At this stage, let's say the cost to go here is 10 The cost to go here is 20 The cost to go here is let's say 5 So what does it want to do in the greedy algorithm? Greedy algorithm at this stage, the minimum cost Cost wise means if we talk The cost to go here is 5, 20 and 10 So what does it want to do? First of all, it wants to follow this choice What is the reason for that? It follows the best or the optimal locally first And on the basis of that, it says With intent of finding the global optimum Means it wants on the basis that I can find global optimum result Or what I can do with global maximum result And here if we talk In this we talk about solution space,
feasible solutions or optimal solution I actually want to tell the greedy algorithm from a real life example Like if we talk As a student we have multiple career options Like we have an option that let's say if I have chosen non-medical So I have non-medical option that I can go to engineering line Or if I have chosen medical option then I can go to medical line Or I have banking sector option SSE etc.
We can go for government jobs Or we can choose our business entrepreneurship Means I have multiple career options You can call this a solution space Means all these options are a solution space But out of this solution space We first find out feasible solution What is the meaning of feasible solution? Based on some selection criteria Means we on the basis of selection criteria Out of all the feasible, out of all the solution space I will find out the feasible condition I will find out the feasible solution To find out feasible solution means Let's say if I have done arts in 11th and 12th Then obviously I can't go to engineering field Means out of all the solution space One field will come out from there So what is my selection criteria? Based on some selection criteria You have to find out feasible solution So let's say if I have arts then on my selection criteria Engineering came out from here Medical came out from here Now what are the feasible solutions I have? I can go to banking line I can go to banking line after taking IBPS exam I can go to SSE I can go to government teacher or
government assistant professor jobs I can do business I can open coaching centers These are the career choices I have now Out of all the feasible solutions Now what we have to find out from that? Optimal solution Now what does optimal solution mean? Because greedy algorithms are totally based on what? Optimal solution And what we have to do in optimal solution? We focus here on minimum cost What does minimum cost mean? Let's say if we talk from this example I have multiple feasible solutions One is 10, one is 20 and one is 5 But which is the minimum cost among these? The minimum cost is 5 So what I will do is choose the path with minimum cost Because this is my optimal path The minimum cost of such real life example that we were discussing Means where my course fees are less I will try to choose that path Where my coaching is a little cheaper I will try to choose that path And the second thing we can do here is Maximize the profit What does maximize the profit mean? That obviously I will try to choose that career path Where I have maximum profit Means where I get the highest pay scale Or where the location can be You have different criteria That on which criteria you want to find maximum value So here I will try to maximize my profit Because what is the name of the algorithm? Greedy So what is greedy? That you are greedy regarding profit So whatever solution you give Whatever problem you have In that problem you will go towards the same solution Which will give you maximum profit Like if there is time for offers So what do we do during the time of offers? We will try to go to the same shop or mall We will go to the same shop Where I am getting maximum offers Or the highest offer I am getting Regardless of how the cloth is Means whatever we are buying Let's say if we buy clothes then how is the cloth? How is the stuff? It may be that in the future I may not get the best solution But locally at that stage It is giving me the best solution This is the main point of Greedy That you try to find the best solution locally So if you are finding the cost Then you will go towards the minimum cost If you are finding the profit Then you will try to maximize the profit If you are talking about risk Then you will try to go towards the minimum risk Means you will try to choose that part Where the risk is less Means like if we talk about investment So we try to invest there Where my risk is less So this is the main point of Greedy That at that stage At the stage where you are standing At that stage it tries to find the best result So if your problem is related to cost Then we will find the minimum cost It is related to profit So we will find the maximum profit It is related to risk So we will try to find the minimum risk Regardless of what my find What is my global solution here It may be that there are many problems Which I have written here Like there is a problem with Napsack Job sequencing Minimum cost spanning tree Optimal merge pattern Huffman coding Digestra algorithm That is called a singer-sourcer test path So all these problems Are in the Greedy solution They come in the Greedy algorithm So basically we are doing this in them Either I am finding the minimum cost Or I am finding the maximum profit Or I am trying to minimize the risk But we focus on this At the stage where we are standing At that stage we find the best result Globally your result is coming best or not This does not give any guarantee So this is a basic introduction About Greedy technique So in the next videos We will discuss these problems one by one Thank You.