This video introduces the depth-first search algorithm. Discover how the algorithm operates in the context of a maze.
- [Instructor] Depth-first search is a very important algorithm with many applications in the real world. Let's first look at how depth-first search works in our maze GUI, then we will discuss some of its applications. So if we go to our GUI code in our project and we select maze_gui_explore, and I'm also going to open config so that I can choose whichever maze that I want. I think this is quite a good one to start with, a diagonal maze, so we'll stay with that for now. So then if I run my GUI, Ctrl + Shift + F10 for me, and we're in explore mode of our GUI, as we looked at earlier on. So I'm going to stick with DFS now, so that's the DFS button in red in the middle, and I can choose where I want to place my treasure. So if I place it near the bottom there, and then I press S, and off it goes looking for the treasure. And in this case, it finds it quite quickly. Now, DFS can be described as an aggressive algorithm, in the sense that it will continue down a particular path until either it finds its goal or reaches a dead end, at which point it backtracks to the last viable position and tries a different path from there. DFS is better in situations where the goal is to discover a path to a given destination as soon as possible. However, it does not guarantee finding the shortest path. Let's look at some more examples. Reset. Now, you'll see later on, when we look at the implementation, why it's taking this rather strange looking path where it's missing out every second line. Okay, let's look in a different maze. So if I go back to config, comment out the maze we were working with, and let's go to the Pac-Man maze again. So I save that, and then if, at this point, I do Shift + F10, it will still run the old file. But then if I want to run it from the file that I'm in, I do Ctrl + Shift + F10. So that's just a little detail about keyboard shortcuts in PyCharm. So DFS in the Pac-Man maze. So I'll place the treasure and I'll press S, and you can see that once the opponent leaves that central box, it then quite aggressively pursues available paths until it no longer can, at which point it will backtrack. So that's happened a few times now, where it's had no success, and then it's gone back to the previous viable place until it goes ahead and finds the treasure. Okay, so that's just an overview of how it's going to work in our maze, the depth-first search. Now let's have a look at some of the applications for depth-first search. Now there are lots of applications and this is just a small selection. So, generally speaking, if you want to do some optimization for a particular aspect of a situation, whether it's cost or speed or safety or some other variable, very useful for pathfinding, very useful for scheduling and there's others as well. So data serialization and also simulations of games, and often a simulation can be in some ways quite serious in the sense that you're simulating a real life situation. So it seems game-like in its approach, but actually it's got more serious applications. So that's just some of the applications of depth-first search.