Hello friends, welcome to Gate Smashers In this video we are going to discuss Generate and test algorithm And in this video we are going to discuss all the important points about generate and test Which for competitive exams Or for your college or university level exams also they will be very beneficial So guys quickly like the video Subscribe the channel If you have still not done and please press the bell button So that you can get all the latest notifications So we will start with generate and test method The first important point is It is a heuristic technique It comes in informed search technique And over here I would like to tell an important point That all the methods that come under heuristic Best first search is there Or hill climbing is there A* algorithm is there From all the method the most simplest method is generate and test Second important point is It uses DFS That is depth first search With back tracking And if over here we talk about generate and test We use this method only in normal life It works in 2 modules One module is generate And one module is test What is the meaning of generate We are generating possible solutions I have a generate function What is it doing Generate a possible solution This is a continuous process Continues means we are generating solutions continuously We are doing it, we keep on doing it And which is the second module over here Over here the second module is test What is it doing All the solutions that are getting generated It is picking boost solutions and doing the test End of the solution passes That means if we have achieved the goal state Then we will accept that solution And if it is not equivalent to goal state That means we are not able to achieve the goal state Then what we will do is we will drop all those solutions We use this method only normally Like if we talk about competitive exams So when we solve questions in competitive exams Are we solve mathematics questions Then generally what we do is we try to generate the solutions While generating the solutions We find out our right answer As I got a right solution We will stop Otherwise what we do We keep on generating new solutions So over here we are working in these 3 steps only Generate a possible solution Keep on generating That means keep on increasing your state space Keep on generating number of states Test to see if this is a actual solution We are matching our each solution with the goal state If it is matching then good Otherwise what we will, do we will generate again If a solution is found obviously good Then you can quit Otherwise go to step one That means keep on generating new solutions This is the basic concept Of generate and test Over here next comes properties of good generator The generator that we are using The method to generate solutions That will actually follow these 3 properties Then obviously it will be good Why? The first one is complete Complete means It will definitely give me a solution All the possible states It covers all the possible state Then only I will get an optimal solution over there Second is non redundant That means if we will again and again generate redundant values or redundant solution Obviously my time will be wasted over there We have already generated one solution In future we again generated that state only Then obviously my number of states will be exponential So what will happen due to that Time complexity will also start becoming exponential So we try to reduce the redundant states That's why it should be non redundant 3rd is informed As I had already told you earlier That it comes under the heuristic technique We keep knowledge of our local domain So that we can find out the solutions quickly So let's take a simple example Let's say I have pin of 3 digit What is the meaning of 3 number Each number is made up of 2 digits In this way Let's say this That means 00 Let's say 00 00 In this way I have 3 numbers Now each 3 number consist of 2 digits Each numbers of 2 digits Now if over here we talk Then if I want to find out what is the possible answer Then how we can find out the possible answer One is brute force method 00 00 01 Then 02 03 In this way we will keep on increasing the numbers So in this case how many number of possible solutions will I get Number of possible solutions will come, how many possible solutions are here? 100 0 to 99 Over here also 100 Over here also 100 That means 100^3 Which you can tell us there are 1,000,000 possible solutions over here If we do not use any informed search technique That's why it is exponential time complexity It will increase exponentially This we have taken a simple example over here Now let's say over here in each one minute In every minute I am applying 5 numbers I am generating 5 possible solutions In every minute Then obviously in one hour I can generate how many solutions? In one hour I will generate 5*60=300 solutions or number I will be able to generate But how much total I have to generate I have to do 1 million So if we talk about brute force method Or about linear search Generally in linear search our complexity is n/2 What is the average case complexity n/2 That means on an average I will have to generate 5 lakh solutions over here So to generate this many solutions To generate these states Even if you will work for 24 hours According to this method Then also you will require 10 weeks You will have to consume 10 weeks over here But if we use informed search technique over here That means if we use heuristic What is the meaning of heuristic Somewhere we have the knowledge about the problem We have knowledge related to the problem We have knowledge of domain So if we use the knowledge of domain over here Suppose I have the knowledge that all the numbers over here These numbers are prime numbers That means between 0 to 99 All the 3 numbers are prime only So in that case how many total possible solutions will be there 25 How many prime numbers are there between 0 to 99? 25 Over here also possible 25 Over here also possible 25 That means 25 ^3 Which is approximate more than 15,000 You consider at approximate So if you are using the same method over here If you are generating 5 in one minute If you are generating 5 solutions in one minute And if you will work for 24 hours continuously Then in this case Only within 2 days In less than 2 days You will find out your answer Which you were using 10 weeks over here in uninformed So what do we call this basically That if you find out a good heuristic over here Then obviously my time complexity will reduce from exponential time But if we talk about the worst case Then obviously my time complexity in worst case Or even if we talk about space complexity Then it will be my exponential time complexity But the more heuristic The more your generator will perform better It will be better The probability of getting a quick solution increases So this is all about generate and test method Thank you