maze traversal puzzle

maze  

maze

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
  • random walk maze traversal

  • this implementation is 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?)

  • efficient? (w.r.t. time? w.r.t. space?)

  • can it be improved?

    • hint: Theseus' thread, Hansel+Gretel's breadcrumbs

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

    • there is a more general version of graph traversal

  • 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 of removal of nodes from L is j g k j g k e h l a m b i c d f)

  • perform an iterative dfs trace (hint: the only difference is that the list is a 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 1: use list to keep track of cells we have seen