I do not recommend solving problems this way unless they are very small, very simple problems. If we use the random variant, it’s randomly trying things out until you hit something which works. It’s trying every possible solution until you hit on one which works. What do our maze-solving algorithms look like in a more general problem-solving context?īrute-force search is, well, brute-force search. Basically any problem whose solution is a sequence of steps (or can be made a sequence of steps). It turns out all sorts of things can be cast as path search problems: puzzles, planning, and of course navigation. In AI, path search is used to think about solving problems in general. … the best-first solution in this case is almost identical to DFS. Here’s an example where best-first works very well: Distance from the goal serves as an heuristic to steer the search. But rather than brute-force searching all the paths, best-first focuses on paths which are closest to the goal “as the bird flies”. Like breadth-first search, best-first explores multiple paths in parallel. The best-known of these is A*, but we’ll use the more-human-intuitive “greedy best-first” search. If we’re not sure which way to go, we take the direction which points more toward the goal.įormalizing this approach leads to heuristic search algorithms. 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).Ī human solving a maze usually tries to work their way closer to the end. 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.
0 kommentar(er)
