# jemdoc: addcss{rbh.css}, addcss{jacob.css}
= maze traversal puzzle
~~~
{}{raw}
maze
~~~
~~~
{}{raw}
maze
~~~
~~~
- [https://en.wikipedia.org/wiki/Theseus\#The_myth_of_Theseus_and_the_Minotaur theseus and minotaur]
- [https://en.wikipedia.org/wiki/Hansel_and_Gretel\#Plot hansel and gretel]
- [https://en.wikipedia.org/wiki/Maze_solving_algorithm algorithms]
- mathematical games guru ~ [https://en.wikipedia.org/wiki/Martin_Gardner mg] ~
[http://www.martin-gardner.org/ mg.org] ~
[https://en.wikipedia.org/wiki/List_of_Martin_Gardner_Mathematical_Games_columns
SciAm col list]
- mg 1959 Jan col /about mazes and how they can be traversed/
-- in mg book 2: Origami Eleusis and the Soma Cube
~~~
~~~
{solve this maze (from the internet)}
{{}}
- what algorithm did you use to solve it?
~~~
~~~
{algorithm 0: random walk}{}
current cell <-- origin
while current cell != destination
current cell <-- random neighbour of current cell
print current cell
~~~
~~~
{random walk maze traversal}
- [https://github.com/ryanbhayward/games-puzzles-algorithms/blob/master/simple/maze/rmaze.py random walk maze traversal]
- this implementation is [https://en.wikipedia.org/wiki/Recursion recursive]
-- pro: easy to describe, leave some implementation details to language implementers
-- con: harder to learn, lose control to language implementers (e.g. stack overflow)
~~~
~~~
{analysis of algorithm}
- correct? (does it always do what it is supposed to?)
-- yes: every reachable location will, with positive probability, be reached
-- proof: consider a path from start to goal with distance t
-- assume each cell has at most k neighbours
-- what is prob that we reach the goal after exactly t iterations?
-- at least {{1 / (k^t)}}
- efficient? (w.r.t. time? w.r.t. space?)
-- no: if at least one nbr of start cell is not goal,
then for any positive integer n,
probability that there are at least n iterations is positive
-- proof: start-notgoal-start-notgoal-start-notgoal ...
-- prob. we are on this path after n iterations at least {{1/(k^n)}}
- can it be improved?
-- hint: Theseus\'s thread, Hansel\+Gretel\'s breadcrumbs:
-- keep track of visited cells
~~~
~~~
{algorithm 1: random walk with remembering}{}
current cell <-- origin
mark current cell
while current cell != destination
current cell <-- unmarked random neighbour of current cell
mark current cell
print current cell
~~~
~~~
{analysis of algorithm?}
- correct? (does it always do what it is supposed to?)
-- no: why?
- efficient?
-- yes: for a maze with n cells, at most n-1 iterations (why?)
~~~
~~~
{a maze and its adjacency graph}{}
X X X X X X a - b - c - d
X . . . . X | |
X . X . X X e f
X . . X . X |
X . . . . X g - h i
X X X X X X | | |
j - k - l - m
nodes or points: a b c ... m
edges or lines: ab ae bc cd cf eg gh gj hk im jk kl lm
~~~
~~~
{graph traversal}
- our version
-- from a given start node, see what nodes we can reach
by following edges
- maintain list L of nodes seen but not yet explored
-- do not add a node to a list if we have already seen it
- breadth first search:
-- L is queue, FIFO list
-- so remove node appended earliest
- iterative depth-first search:
-- L is stack, LIFO list
-- so remove node appended most recently
- depth-first search
-- recursive (recurse as soon as unseen nbr found)
-- differs slightly from iterative-dfs
~~~
~~~
{iterative bfs,dfs}{}
for all nodes v: v.seen <- False
L = [start], start.seen = True
while not empty(L):
v <- L.remove()
for each neighbour w of v:
if w.seen==False:
L.append(w), w.seen = True
~~~
~~~
{example trace of bfs}{}
use the above adjacency graph, start from node j
initialize L = [ j ]
while loop execution begins
remove j from L L now [ ]
nbrs of j are g,k
append g to L, g.seen <- T L now [ g ]
append k to L, k.seen <- T L now [ g, k ]
while loop continues (bfs, so L is queue, so remove g)
remove g from L L now [ k ]
nbrs of g are e,h,j
append e to L, e.seen <- T L now [ k, e ]
append h to L, h.seen <- T L now [ k, e, h ]
j already seen
while loop continues: remove k from L
v <- k L now [ e, h ]
nbrs of k are j,h,l
j already seen
h already seen
append l to L, l.seen <- T L now [ e, h, l ]
while loop continues: ...
~~~
~~~
{exercises}
- complete the above bfs trace
-- hint: order in which edges are examined is jg jk ge gh gj kh kj kl ...
-- so order of removal from L is j g k e h l a m b i c d f
- perform an iterative dfs trace
-- hint: only difference is that list is stack
~~~
~~~
{recursive dfs}{}
for all nodes v: v.seen <- False
def dfs(v):
v.seen <- True
for each neighbour w of v:
if w.seen==False:
dfs(w)
dfs(start)
~~~
~~~
{example dfs trace}{}
use above graph, start from j
dfs(j) nbrs g,k
. dfs(g) nbrs e,h,j
. . dfs(e) nbrs a,g
. . . dfs(a) nbrs b,e
. . . . dfs(b) nbrs a,c
. . . . . a already seen
. . . . . dfs(c) nbrs b,d,f
. . . . . . b already seen
. . . . . . dfs(d) nbrs c
. . . . . . . c already seen
. . . . . . dfs(f) nbrs c
. . . . . . . c already seen
. . . . e already seen
. . . g already seen
. . dfs(h) nbrs g,k
. . . g already seen
. . . dfs(k) nbrs g,h,l
. . . . g already seen
. . . . h already seen
. . . . dfs(l) nbrs k,m
. . . . . k already seen
. . . . . dfs(m) nbrs l,i
. . . . . . l already seen
. . . . . . dfs(i) nbrs m
. . . . . . . m already seen
. . j already seen
. k already seen
~~~
~~~
{example, above maze graph, from j}{}
- assume nbrs are stored in alphabetic order
- iterative bfs: order of removal from list?
j g k e h l a m b i c d f
- iterative dfs: order of removal from list?
j k l m i h g e a b c f d
- recursive dfs: order of dfs() calls?
j g e a b c d f h k l m i
- iterative dfs with nbrs added to list in reverse order:
j g e a b c d f k h l m i
notice that this differs from recursive dfs
~~~
~~~
{algorithm 2: use list to keep track of cells we have seen}
- list cells examined in FIFO manner (queue)?
-- [https://en.wikipedia.org/wiki/Breadth-first_search breadth-first search]
- list cells examined in FILO manner (stack)?
-- [https://en.wikipedia.org/wiki/Depth-first_search depth-first search]
- [https://github.com/ryanbhayward/games-puzzles-algorithms/blob/master/simple/maze/maze.py bfs-dfs maze traversal]
~~~