They don’t really do anything clever, they just crawl through the whole maze until they stumble on a solution. There’s lots more to say about these two algorithms, but main point is what they have in common: these are brute-force methods. It’s “breadth-first”: it explores all paths at once, keeping the search as wide as possible. It’s like a plant: every time BFS hits an intersection, it splits and goes both ways. In this snapshot, we’ve hit three dead ends, and we have four separate “branches” still exploring the maze. We go as far as we can down one path (“depth-first”) and if we hit a dead end, we turn around, back up, and try another path.īreadth-first search, on the other hand, tries all paths in parallel: Then we turn around and go back, find another right turn, and hit another dead end. So, in the Pinoccchio maze, we start out by turning right and running until we hit a wall (the first “x”). Here’s DFS, applied to the Pinocchio maze above:īasically, the DFS rule is “always take the right-most path which you haven’t already explored”. The very first path search algorithms students typically learn are depth-first search (DFS) and breadth-first search (BFS). In algorithms classes, this problem is called “path search”. You have a maze, with a start point and an end point, and you are searching for a path through it. I’ll assume no technical background at all, so if you’ve seen some of this stuff before, feel free to skim it. Then we’ll move on to the interesting part: two techniques which often work better for everyday problem solving, and lend some interesting insights when applied to mazes. Next, we’ll talk about how these algorithms can fall short for everyday problem solving. We’ll start off with some traditional path-search algorithms (DFS, BFS, heuristic). It turns out that they can all be applied to mazes, so I’ll use some disney-themed mazes to illustrate each approach. I want to talk about a few different approaches to general problem solving (for humans).
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |