Content deleted Content added
m →Maze-Routing algorithm: decapitalized common nouns, added wikilinks |
m →Random Mouse Algorithm: Decapitalized common nouns |
||
Line 4:
Mazes containing no loops are known as "simply connected", or "perfect" mazes, and are equivalent to a [[Tree (graph theory)|''tree'']] in graph theory. Thus many maze solving algorithms are closely related to [[graph theory]]. Intuitively, if one pulled and stretched out the paths in the maze in the proper way, the result could be made to resemble a tree.<ref>{{youtube|k1tSK5V1pds|Maze to Tree}}</ref>
== Random
This is a trivial method that can be implemented by a very unintelligent [[robot]] or perhaps a mouse. It is simply to proceed following the current passage until a junction is reached, and then to make a random decision about the next direction to follow. Although such a method would always [[Las Vegas algorithm|eventually find the right solution]], this algorithm can be extremely slow.
== Wall follower ==
[[File:maze01-02.png|left|frame|Traversal using ''
[[File:MAZE.png|right|thumb|upright=1.5|Maze with two solutions]]
[[File:MAZE solution.png|right|thumb|upright=1.5|Solution to above maze. The solution is the boundary between the connected components of the wall of the maze, each represented by a different colour.]]
| |||