Hello friends welcome to Gate Smashers In today's video we are going to discuss Breadth search technique in artificial intelligence End in this video we are going to discuss all the key points and important points regarding it Which will be helpful for your competitive exams Even if you are studying artificial intelligence in university or college level exam Then these all points will be very much helpful to you So we will start from the very first important point Uninformed search technique BFS comes in uninformed search technique You can call it as blind technique also Or you can call this as brute force method also What is the meaning of uninformed over here There is no domain specific knowledge In comparison to this what do we have? We have heuristic technique What happens in heuristic technique We take an estimate value That if I want to go on goal state From any particular state Then how much cost will it incur But over here we do not any prior knowledge Like heuristic What we do in heuristic Let's say if I went from A to B And from B I want to go to goal state Then over here the cost to go from A to B And what is the cost to go from goal state to B I know this thing in advance only Which we call informed search But uninformed search means That how we have to go from A to B That we know That what will be the cost from A to B But now is B taking me to goal state It is not taking me how much is the cost How much cost is not there There is no information regarding that So we called it uninformed search or blind search The meaning of blind search is I don't know when i'll get goal state But I know that someday I will get the goal state So that is why we call this as uninformed search technique The second important point over here is FIFO Which means first in first out And which data structure does it use Queue So by default queue works on FIFO On the basis of this graph over here i've taken a tree You can take tree also you can take graph also So if we apply BFS on this So how we have to work over here So as we have written over here we will be using queue data structure So first of all you should know in queue That we always insert elements in queue from tail And we remove elements from head That means First In and that only will be First Out So if we talk first of all which element will come over here A So we added A over here, it used at a lot of places, fringe First node We use a lot of keywords over here You remember with a simple method Because only 2 types of questions will come Either you will be given a graph Or you will be given a tree On that it can be asked that is this a proper BFS or not Or theory points related to this Which we have written over here It can be asked about that So if over here we talk about A If we remove A from the queue So what is the meaning of removing We removed A from queue So a is taking us ahead at how many places From A where all we can go? First we have added those elements over here So which are the elements? B, C and D You can write this in any order It is not necessary that you write B,C and D only You can write C,D and B in any way But if you will follow one pattern Then you will come to know You can also use some other BFS search Any other pattern also can be formed But will come to know about one technique over here So we removed A from the queue And after that we saw as taking us at how many places B,C and D So we added them in the queue Now what we did is we removed B from the queue And B is taking us at how many places That we inserted Show B is taking us at E&F This is by default queue only If you want you can make this like queue But as I told Insertion is always to be done from behind And we remove the value from head Which is the rule of first in first out So now we removed C from here So where is C taking us C can take us to G and H So we inserted G and H from tail So in this way we just have to keep on going Then we removed D from here The meaning of removing D is We already have elements E, F, G and H in the queue But the meaning of removing D is Where is D taking us It is taking us on I So what we have written over here We have inserted I from the tail So over here what knowledge do we get We are getting the knowledge Shallowest node The meaning of shallowest node is If we talk about DFS in comparison to this Depth first search How does depth first search work It goes in One Direction And goes in deep It goes till complete depth But BFS does not do like this BFS goes level by level You can also call this as level order This is also called level search technique Why? First of all we went on this level Now we are on this level So we have completed this whole level See first we removed B Then C And now D So when D level is removed This whole level is completed Now we came on the next level That means instead of going in deep It completes the shallowest node the nearest node In this will move ahead level wise level So this knowledge is the most important key point In BFS And this is only asked the most So you have to remember only this important point over here So now we removed D Which is the next element E So now we remove E, now what is formed over here F, G, H, I And where is E taking us? It is taking us at J and K We inserted J and K from tail That's it Now we will remove F Then G, H, I, J, K And where is F taking us It is not taking us anywhere That means it does not have any children ahead of F So we keep it as it is Then we remove G from here So what is formed H, I, J, K is already in the queue And where is G taking us It is taking us to L So we inserted L from the tail Again we are on which level We are going on this level After completing the whole level It will go on next level Then if we remove H from here I, J, K, L And what do we have over here after L Which we have cut That is H Where is H taking us It is not taking us anywhere So let it be written as it is Then we remove I from here Then J, K, L And where is I taking us? At M Then what is the next that we will write M Now see next Which level is finished? This whole level is completed This was depth 0 Depth 1 complete, depth 2 complete Now we will go on next dept We will go on next level So next level means we have to remove J K, L, M And where is J taking us? Nowhere So next we will remove K So we removed K Then L and M is left over here And where is K taking us? It is taking us at N So what we did, we inserted it Then we removed L from here M and N Where is L taking us? It is not taking us anywhere We don't have to anything else We remove M from here Then what is left? N is left Is M taking us anywhere? M is not taking anywhere Then what is the last element left with us? N is left So it moves in this way And it moves level by level only That means its order instead of going in deep It moves like this level by level So if you want to search any element Then will this give answer? Will this definitely search an element? Yes Why? Because we are not leaving any element behind in this What we do in DFS, we move in one direction We are going in one depth Other elements in upper depth are kept as it is The one which I wanted to search that is in the above level But we are going in one depth We might get stuck in any loop And if the search space Is infinite Then we will never be able to search the element But instead of DFS we talk about BFS Breadth First Search It is completing all the levels one by one in this way Then definitely it will give answer That is why we tell this over here Complete What is the meaning of complete This will definitely give an answer It is not incomplete That means if you search any element Even if you are searching G So to search G you will go in this way only As you got G element Let's say over here you had found G element So when you were going on then over here you had found G element So before cutting G element you check That is G element goal state? Goal state means Is this the element that we are searching Yes it is that element So what happens We take its parent node pointer Then who is the parent of G? C And who is parent of C? A So in this way ACG We define the path This is when we want to search any particular element But if we want to see all of them then we run breadth first search in this way Then we have optimal What is the meaning of optimal We have breadth first search Does this give optimal result? Does this give shortest result? Yes, it will always give you shortest result And all the nodes, all the edges that we have If the cost of edges will be same Let's say we take cost of all as 1 1 Then definitely same cost that means That means it will give shortest cost Andin case if you are giving its cost different also Then also this will give shortest path only So it always gives optimal result only And the last point we have time complexity Many time questions come on time complexity What is the time complexity of a particular algorithm So we write it's complexity O(V+E) That is V is the number of nodes E is the number of edges But generally we write this complexity in data structure Because we use this algorithm in data structure or algorithm subject also But we talk about Artificial intelligence In artificial intelligence we write its complexity O(b^d) O(b^d) Where b is the branch factor Over here factor means How many array we have That means there are how many children of A How many maximum children are there of any particular node So over here We can also have n-array tree also N-array tree means One particular node It is not necessary it is a binary tree There can be only 2 children It can be turnary also It can be quad also There can be many children of one particular node So over here how much ever children will be there We have take its value as branch factor or we can call it as b And what is D over here Depth Depth means Over here if we talk then what is the depth 0 Over here what is the depth? 1 How much is the depth? 2 Over here we have depth 3 Over here we have depth 4 That means if we are going from root node to n Then how much is the depth? 1,2,3,4 So see what depth will we get? 4 So in this way we consider the depth If you are searching any element Let's say even if you are searching G also Searching G means If we talk on each particular node 3 elements We have 3 children We have value of b as 3 And see what is depth We have depth as 2 Then see 3^2 means 9 When we are searching this element, G Then we will not need more then 9 search And obviously you can also check manually 3 search will be done over here 3 can be over here If we consider that there will not be more then 3 children Then 3 and 3 is 6 And 3 is 9 That means we will get result in 9 search That's why it power O(b^d) We denote it like this, that is the time complexity So these all are important points related to Breadth First Search Then all these points, if you are preparing for any competitive exam Or even if you are preparing for college or university level exam also Then the questions will not come more than this All these points are more than enough Thank you
