Welcome to The Nonlinear Library, where we use Text-to-Speech software to convert the best writing from the Rationalist and EA communities into audio.
This is: Problem Solving with Mazes and Crayon, published by johnswentworth on the LessWrong.
I want to talk about a few different approaches to general problem solving (for humans). It turns out that they can all be applied to mazes, so I’ll use some disney-themed mazes to illustrate each approach.
We’ll start off with some traditional path-search algorithms (DFS, BFS, heuristic). Next, we’ll talk about how these algorithms can fall short for everyday problem solving. 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.
I’ll assume no technical background at all, so if you’ve seen some of this stuff before, feel free to skim it.
DFS and BFS
You have a maze, with a start point and an end point, and you are searching for a path through it. In algorithms classes, this problem is called “path search”.
The very first path search algorithms students typically learn are depth-first search (DFS) and breadth-first search (BFS). Here’s DFS, applied to the Pinocchio maze above:
Basically, the DFS rule is “always take the right-most path which you haven’t already explored”. So, in the Pinoccchio maze, we start out by turning right and running until we hit a wall (the first “x”). Then we turn around and go back, find another right turn, and hit another dead end. Turn around again, continue.
That’s depth-first search. 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.
Breadth-first search, on the other hand, tries all paths in parallel:
In this snapshot, we’ve hit three dead ends, and we have four separate “branches” still exploring the maze. It’s like a plant: every time BFS hits an intersection, it splits and goes both ways. It’s “breadth-first”: it explores all paths at once, keeping the search as wide as possible.
There’s lots more to say about these two algorithms, but main point is what they have in common: these are brute-force methods. They don’t really do anything clever, they just crawl through the whole maze until they stumble on a solution. Just trying out paths at random will usually solve a maze about as quickly as DFS or BFS (as long as you keep track of what you’ve already tried).
Let’s be smarter.
Heuristic Search
A human solving a maze usually tries to work their way closer to the end. If we’re not sure which way to go, we take the direction which points more toward the goal.
Formalizing this approach leads to heuristic search algorithms. The best-known of these is A, but we’ll use the more-human-intuitive “greedy best-first” search. Like breadth-first search, best-first explores multiple paths in parallel. But rather than brute-force searching all the paths, best-first focuses on paths which are closest to the goal “as the bird flies”. Distance from the goal serves as an heuristic to steer the search.
Here’s an example where best-first works very well:
By aggressively exploring the path closest to the goal, Pluto reaches his bone without having to explore most of the maze.
But heuristic search comes with a catch: it’s only as good as the heuristic. If we use straight-line distance from the goal as an heuristic, then heuristic search is going to work well if-and-only-if the solution path is relatively straight. If the solution path wiggles around a lot, especially on a large scale, then heuristic search won’t help much. That’s what happens if we apply best-first to the Pinocchio maze:
. the best-first solution in this case is almost identical to DFS.
General Problem Solving
In AI, path search is used to think about solving problems in general. It turns out all sorts of things can be cast as path search problems: puzzles, planning, and of course navigation. Basically any problem who...
view more