All right, now it's time to get the robot to the gold. In order to do that, we're going to look at some fundamental algorithms for searching graphs. So by the end of this video, you'll be able to perform an algorithm called Depth-first Search for searching a graph you'll be able to implement that algorithm, and you'll also be able to describe how the abstract data type stack works as well as how a stack is used in depth research. So let's go back to our graph representation. Here it is. And remember that our goal is to take a robot which exists at some location in this world, and get it to the gold. Now I drops the background with the walls and the grid and everything because we really don't need that anymore. Our task is fully defined by the graph that you see here. So how are we gonna get the robot from where it starts to the gold? Well in order to do that, we need to really search for a path from the robots starting point to the gold. We're going to look at two different ways to perform that search. The first is called Depth-first search and the second is called Breadth-first search. We'll look at Depth-first search first. Now, before we start looking at the search I want to say that there's lots of different ways we can play around with this problem here. We're talking about a robot in a world. It might be the case that while the robot is searching, it's actually physically moving through the world. Or it might be the case that it has a copy of the map before hand, and it's doing all of its planning before it starts moving. And which situation the robot is in, is going to effect which algorithm it chooses to ultimately find it's gold. We're not gonna get into those details quite yet in this video but you have the opportunity to explore some of these details a little bit later on in this course. So, in order to search this graph let's be a little bit more abstract. So I'll represent the robot's starting position with this vertex labelled X or sorry not X,S, and I'll represent the robot's goal position with that vertex labeled G, for goal. And then just so I can have a little bit more concreteness, I'm gonna give all these other vertices in the map letters, so I can talk about them. Ok. So now we're ready to begin. And let me just show you how a Depth-first Search on this graph is going to work. So the robot starts at position S, and then what it's going to do is it's going to search all the way deep along a single path until it gets stuck, or it reaches its goal. And only then will it decide to go in a different direction. And the way the robot is going to explore from any particular node it has to be very methodical in its exploration is it's first gonna try to go up if that's a possibility and if it's not it's gonna try to go left and if that's not a possibility it will try to go down and if that's not a possibility only then it will try to go right. So let's look at how a Depth-first Search with that order of exploration will work so robot starts at position X. Or S. And it goes up to position I. So now it's at position I. It's exploring from I. So it'll again try to go up. It can go up, it goes to H. It tries again to go up. It can go up, it goes to D, now from D, it can look and see, well, I can't go up, there is no edge that will lead me up. So let me try going to the left. It tries to go left, and it can, and it reaches position C. It tries to go up, it can't, it goes left, position B. It tries to go up again, it can't, so it goes left, it goes to position A. And then from A is says, well let me try to go up, no edge up, let me try to go left, no left edge, so what does it do? It goes down. It goes down to E. Now it's sitting here exploring from E, and from E it's going to try and go up, and there is an edge up from E, and so it's going to say, hey, maybe I should go to A. But should he go back to A? Well,no because A is already been explored. We don't wanna go back to A because if we're going back to A we'll get start in a loop, going A, E,A ,E, A,E and that'll be no good. We'd never get any closer to our goal. So we have to keep track of the fact that we've already seen A and we don't wanna go back there, so if we do that, then the robot will notice okay, I've already been to A, so let me try some other direction. Let me try going down. And sure enough it goes down and it reaches the goal. So you'll notice that the robot really just tried to continue to pursue one path, deeper and deeper and deeper until it got to the goal. So that's why this algorithm is called Depth-first Search first. Because it searches deep, as deep as possible. However it's not always that simple. So lets modify the graph structure just slightly and try this search again. So we're still gonna start at position S and everything is gonna start the same. So we're gonna start searching up, we go to I To H, to D, to C, to B, to A, but now we're at A, and the robot's kind of stuck. So my question for you is following this depth-first mantra, what do you think is going to be the next unexplored node that gets explored using this algorithm? Okay, if you said F, then you were right, and look at how that happens. So right now the robot is all the way over there in A, exploring from A, but it's stuck, there's no place to go from A. So what it's going to do is it's going to backtrack. It's going to say, well what about from B? Where could I have gone from B that I maybe didn't go? And from B, it's gonna see oh, I could have gone down. So let me try going down to F. Well F is a dead end too. So at this point, it's gonna do the same thing, it's gonna backtrack. It's gonna say B, anywhere else I can go? No, not anywhere that I haven't been. So let me try C. No, D? No, H? I, S, aha. Now from S, I've got new possibilities. So it's going to go out from S to L, to K, to J, and ultimately reach its goal. So you can see the Depth-first Search did find the goal, but it went all the way to the end of that A and F path before it came back to S and started exploring down the path that would actually lead it towards its goal. So that's the major of Depth-first Search. It's going to go all the way deep before it backtracks and tries to go in a different direction.
