So, before this we have seen in breadth first search that when we have to implement breadth first search then Q like data structures can be used for that and through them it can be implemented Another approach which we are using in blind search algorithms is depth first search approach The procedure of working of depth first search approach is the following is that it starts searching depth wise. Like in breadth first search, we talked about first level is solved, first level is traversed, then tree traverses next level and so on. When we talk about depth first search, the node we expand, we go to its child node, go to the bottom, and then move upward. And because of this sometimes the depth first search algorithm is also called backtracking search. Or backtracking search can be easily implemented on top of it. If we talk about implementation perspective, then to implement depth first search, stack data structure can be used. The stack data structure works using the LIFO procedure which means last and first out. The element which is kept in the stack at the end can be traversed or visited by the stack first. If we talk about working mechanism of Depth for Search As we discussed in previous slides So here you can see node 1 is our starting node And from node 1 we will visit node 2 There are two child nodes in node 2 Node 3 and 13 So the one which opened before node 2 We will go into 3 After that, instead of visiting 13, we will expand node 3 further and visit 4 from the 4 and 12 nodes in its downward direction. From next 4, we will go to node 5 and then to 6 node. When we have reached node 6, then there is no child node of this node. So we will go back to previous node which is node 5. Note 5 has no other node, so we will go to previous node, Note 4. We have visited Note 5 in Note 4, now Note 7 is present in Note 4 child. So, 7 will be visited. After visiting 7, Note 8 will be visited. Note 8 will be visited and Note 9 will be visited. Now there is no other note in the child of 9. So we will go back to 8. If there is no other note in the child of 8, then we will go to 7. Note 10 is present in the child of 7. We will visit 10 and then we will visit Note 11. Now again, if there is no other note in the child of 11, then we will go back to Note 10. Note 10 has no other sibling so we will go back to note 7 Note 7 has no other sibling so we will go back to note 4 And from there we will visit another child of note 3 Then we will go back to note 2 and visit 13 Now 13 to 14 and then 15 and 16 so onwards Now we will do traversing in depth first search are searching for nodes. So, same example we will try to implement through depth first search and see which nodes are expanded and after that how much time we can reach to the goal node. Similarly, we will visit S node first. S is our parent node. So there is no cost of visiting parent node. When we start searching, we can assume that our starting point is S. When we visit S, we will have three nodes open. Nodes A, B and C. So, first of all, we will visit A from A, B and C. When we visit A, then D, E and G will open up. The first depth of A is D. From DE and G, we will visit D. Here you can see that B and C were already present, but Since D is present at the top of the stack, we will expand the latest item that has been inserted first. So you saw when we were talking about breadth first search, we used to append all the new nodes on the end. And here we are adding all the new nodes. start, the beginning is being appended there. So basically the data structure behind them is being implemented you can say the difference of those data structures or the algorithms we are using the behavior of those algorithms is such that for them we have to use these particular data structures while implementing them. So now we will visit D We have not opened any new node by visiting D. Next node is E. Next we will visit E. After visiting E, the next node is G. Because no new node has opened after E. So we will visit G. And G is our goal state. So if we look at this, we have just expanded 5 nodes and by expanding 5 nodes we have reached the goal state. So in future the path we will select, the agent through which the agent can visit next time, that would be SAG. This is the same path which we searched through breadth first search. Majorly in breadth first search and depth first search, the node or path which was searched through which agent reached goal state, there was no difference in this particular case. So we can reach the goal note through A and G and the actual cost of this will be 18. Here you can also note one more thing. that breadth for search selected SAG path and depth for search selected SAG path whereas in comparison we have another path available which is SCG and if we reach above G through SCG then the cost to pay is 13 which is optimal one So we have only 3 paths to go to SAG, if we go through A, then its cost is 18, if we go through B, then its cost is 21, if we go through C, then its cost is 13. So, the most optimal one is 13 out of 18, 21 and 13, but we can see that Depth First Search and before that, Breath First Search also did not find the optimal path. and in comparison to that we found a less optimal path so the path we have selected is SAG and its cost is 18 but if we see how much we have paid for traversing so the cost of going from S to A was 3 and the cost of going from A to D was 3 which becomes 6 A to E cost 7 which becomes 13 and A to G cost 15 which becomes 28. So total 28 cost paid and we visited 5 nodes and reached solution. So depth for search is appropriate search when we have space restrictions. We have space, computational space, storage capacity is restricted. And if there are many solutions perhaps with long paths particularly for the case where nearly all paths lead to a solution or the order in which the neighbors of a node are added to the stack. can be tuned so that solution are found on the first try. So if we have such a situation where more than one solution exists, or we have space restrictions where we cannot store much data, Or we have a scenario where depth wise the goal cost can be tuned to the initial depth in which the goal state is existing. So in this scenario, depth of search can be used. In general, if we do not have any information available about the environment or our problem, then any search can be used in that case. But obviously there are some problems with depth first search For instance it is possible to get caught in infinite paths As we saw in breadth first search loops can be implemented For instance we went from S to A and from A we opened D node So let's suppose if there is a path available to go from D to S D goes to S, S goes to A, A to D and this is a cyclic path. So if there are any loops or looping structures in our tree or graph that we are going to implement, then depth of search can be a problem. If the solution is available on a deeper level, multiple nodes, and if the solution exists on the last depth of the multiple nodes, then it may take a lot of time to search for depth for search. So, in the case of these two or three problems, depth for search cannot be used. There are some videos related to depth for search and breadth for search We will see these videos and then move to next uniform cost search So uniform cost search The difference between Depth First Search and Breadth First Search is that in Uniform Cause Search, the search strategy we are implementing is based on some information. Although, Uniform Cause Search is called UCS in short. This is a blind search algorithm. But uniform cost search makes decision based on basic information. Blind search is done but when nodes are visited, decision is based on cost. Not location based on where nodes are existing. So we can say that uniform cost search implements a priority queue and tries to access values based on the priority queue. If you have studied data structures and have idea of queue and stack, then you must have discussed the priority queue in data structures. And you can understand how to order values in priority queue. Another assumption in uniform cost search is that all nodes are on equal distance from starting nodes and can be directly accessed from starting nodes. In the next slides, we will see how to implement uniform cost search. So, same problem is present which we have solved through depth first search and breadth first search. And now we will try to implement this example through uniform cost search. So, in starting we have similarly S node available and when we will visit S, we will have three paths open A, B and C. Here you can see two pictures that I have shown. One picture on top is the same picture that we have used before in previous algorithms in which we have paths available about basic problem. And below that I have drawn another picture in which paths are available to directly visit all nodes from S. And for them, the... actual path is being made for them to go from S to that node that cost is also mentioned like if we have to go from S to A then its cost is 3 and in bottom picture also you can see its cost 3 is also mentioned but when we go from S to D so just now I discussed in last slide that when we In uniform cost search, we assume that all nodes are on equal distance and can be accessed directly from starting nodes. Now we cannot write distance from S to D as 3, but we assume that we are approaching D directly from S, so distance from S to A, cost from S to A plus cost from A to D, this is the complete cost. The distance from S to D will be mentioned. The reason for the 6 cost of going from S to D is that we can go directly to D by paying 6 cost from S without involving A. This is the working that agent is implementing on the backend whenever he has implemented on the search space. If we want to map given problem, then we can design internal map by ourselves. Which we store in priority list or priority queue. Similarly, if we want to go to SAE, then cost of going to SAE is 3 and cost of going to A to E is 7. So, cost of going to SAE is ultimately 10. And similarly, other costs are mentioned. So, the cost of visiting S is zero, but we have three paths available from S, B, A and C. So, now we have written it in the order of priority Q, the node whose cost is the lowest, its priority will be the highest. So, B's cost is 1, A's cost is 3 and C's cost is 8, so first we will visit B. When we visited B, a path from B to G has been opened and its cost is 21. As you can see in the picture below. So, by visiting B, we have added one extra node. In the priority cube, the top priority node is A. So, next we will visit A. By visiting A, we have three more nodes open. D, E and G. So B cost 6, C cost 8, E cost 10 So E is sorted by priority queue and entered after C G cost 18, if we are visiting G via B, then it costs 18 G cost 18, if we are visiting G via A, then it costs G is 18 for A and 21 for B Next node is D Cost of going to D is 6 No node is opening from D Next node is C G of C will open a new path. E of C will open a new path. G of C will open a new path. So, here you can see that Uniform Cost Search has found the optimal solution and we have searched the best path through that optimal solution. So, here if we see, in future the path that the agent will be using, that would be SCG and the cost that the agent will have to pay, that would be 13. Here we can see how many nodes we have visited. To search this solution we have to visit S, B, A, D, C, E and G. So we have to visit total 7 nodes through which we have searched our solution. The traversing cost we have paid, we have visited A, its cost is 3, B is 1, C is 8. So that becomes 12. We have visited D and E. We will add the cost of both of them. That becomes 22. Plus we have visited C to G and its cost is 5. So by paying 27 cost, we have traversed this problem. So traversing cost will be 27. The solution cost that we will have will be 13. Here you can compare the previous approaches we have discussed with them. And you can see that the highest number of nodes we used in breadth first search was 7. But when we visited 7 nodes in breadth first search, we had to pay around 38 traversing cost. In depth first search, traversing cost was 28. And despite that we visited more nodes than depth first search, but still traversing cost which we paid in uniform cost search, that is 27 which is minimum. That means by paying minimum traversing cost, we have found optimal solution. We have one more. Example here is available, we have it, you can see above the top, we have to go from S to the round node, which is G, and different paths are available to go to that. For instance, if we want to visit from S, we can go from S to P, from S to E, or from S to D, and so on and so forth. Multiple paths are available after that. So, We want to implement uniform cost search. So when we visit S, initial cost is 0. The cost of visiting D from S is 3. The cost of visiting E from S is 9. And the cost of visiting P from S is 1. So the minimum cost is P. First of all, we will visit P. When we visit P, another node will open. Q and its cost is 16. We have minimum cost path, so we will visit D. When we visit D, the nodes that are expanded are B, C and E. The cost of visiting B is 16. 4 is there. You can see that the cost of going from S to D is 3 plus the cost of going from D to B is 1 so the cost of going from S to B that would be 4. We will visit B. After visiting B the minimum cost according to the priority queue is E. We will visit E. After visiting E, the minimum cost is A, which we have hit through S, D, B. So we will visit A, A's cost is 6 and no note is further opening from A. Next, we have the path of 7 cost available, which is R, we will visit that. After that, F is opened. we will visit F and its cost is 8 after visiting 8 we have 2 nodes open C and G but before that E is available and its cost is 9 so we will visit E and now we have G available and its cost is 10 so we will visit G through F and that is our solution that is our goal node and that is our goal node And you can see how the solution has been expanded and how the search has been done. Instead of searching at the same level or at the same depth, the whole solution has been expanded and where the minimum cost has been found, the agent has followed that minimum cost. The good thing about uniform cost search is that uniform cost search is complete and optimal. We will always get the solution and we will be getting the optimal solution. So if there are any loops, uniform cost search can definitely provide us the solution. The bad thing about uniform cost search is that uniform cost search expands nodes in every possible direction and since we don't have heuristics available, actual information about goal location is not available, so the computational complexity of uniform cost search wo kaafi zyada ho sakte hai. These are few videos about uniform cost search and some comparison of breadth for search, depth for search and uniform cost search. So aap in videos ko dekkar aap guess karne ki koshish karenge ki aap n mein se kaunsi video jo hai wo uniform cost search ke baare mein hai, kaunsi depth for search ke baare mein hai or kaunsi breadth for search ke baare mein hai. When we implement these search strategies, sometimes we can get wrong and inaccurate results. A simple example of this is that if you are searching on the map and paths are available and you try to implement those paths directly, then it is possible that we have a situation like this. So, just because there was a path available and if we don't have accurate information about that path, then problems can occur. So, that's why blind search approaches are not used much and it is recommended that for complex problems, Use such search approaches in which we have more information about the environment, problem, and search space. Finally, this is a The problem which you have to solve before the class is A to B. A will be the starting node and B will be the ending node. You have to implement all three of them. We will try to solve this example in our live session. Thank you.