Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.
|
|
|
|
Re: finite maze solving algorithm
Posted:
Dec 2, 2004 11:41 PM
|
|
lewis@SPYDER.MITRE.ORG (Keith A. Lewis) wrote in message news:<coihf4$bod$2@newslocal.mitre.org>...
> Kevin Saff <news@kevin.saff.net> writes in article <I808DL.GF2@news.boeing.com> dated Tue, 30 Nov 2004 18:22:32 GMT:
>
>>Michael Michalchik wrote:
>>> I was wondering if anyone knows if all possible topologies of finite
>>> 2d mazes can be solved by a finite algorithm. For example, we know
>>> that all fully connected mazes can be solved by picking a wall and
>>> exhaustively following it. Can a general solution work for all mazes
>>> including the ones that are piecewise disconnected? If this is
>>> possible, is the general solution a solved problem?
>>
>>Interesting. How are you defining a maze, here? Usually, I think of a
>>maze as just a graph, which you can solve using something simple like
>>depth-first search, regardless of whether it is planar. It is probably
>>better to think in terms of connectedness of rooms than connectedness of
>>walls.
>
> The basic problem with a depth-first search is the chance you'll get into a
> loop going around and around a disconnected piece. The problem can be
> avoided by making a rule to never cross your own path.
>
> Or is there something more that I'm missing?
If you keep going in circles, then you are not doing a depth-first
search. Depth-first search will systematically explore *any* maze
in its entirety.
In depth-first-search, you keep traversing down previously untraversed
paths until either you reach a place where all possible paths have
already been traversed or you reach a dead end. In these situations,
you "backtrack" along the path you've just traversed until reach a
place where there is an unexplored corridor, and then you head down that
corridor.
To find your way through an actual maze (i.e. not one written on paper),
you need some way of marking passages. A 19'th century algorithm for
traversing a maze is as follows. Bring along a pile of pennies to
mark passages as you enter and leave junctions. During the algorithm,
passages without pennies haven't been traversed yet, those with one
penny have been traversed exactly once, and those with two pennies have
been traversed and then backtracked along in the opposite direction.
Enter the maze. When you encounter a junction that you haven't seen
before (no passageways with pennies), then choose a passage at random
(remember to drop a penny in the passage you just left and in the
passage you just entered). If you hit a dead end, turn around and go
back. If you are walking down a passage for the first time and you
encounter a junction you've seen before, then turn around and head
back (remember to drop two pennies, one for entering the junction
and one for leaving). If you are walking down a passage for the
second time and encounter a junction, then take a new passage if
there is one, otherwise take an old passage (marked with one penny).
When you reach the solution, passages marked exactly once will
indicate a direct path back to the start. If there is no solution,
then you will end up back at the start with all passages marked twice.
|
|
|
|
