Given a set A consisting of all possible solvable mazes on an n by n square grid, what is the average running time to solve the mazes in A using a standard backtrack algorithm with no optimizations?

The algorithm checks each ajacent space clockwise for a channel, then visits each channel and either marks it off if it encounters a dead end, or previously covered point, or if it reaches the end point the algorithm completes.

This question was on an exam, and I figured O(n^2) cause there is O(n^2) spaces to visit for each maze, but my prof insisted the correct answer could be O(n log n).

A proof would be greatly appreciated.

Thanks!

  • 1
    Note that $O(n\log n)\subset O(n^2)$ so your professor is making a stronger claim that does not contradict yours. – David Richerby Nov 3 '14 at 8:34
  • You always walk a tree. What I'd try is construct larger mazes from smaller ones, e.g. by adding one row on the side, and try to count how the number of walks will increase. – reinierpost Nov 3 '14 at 11:07
  • @reinierpost, but I am trying to obtain the average time for the set of all possible mazes, your method would only analyze a small subset of that set. – Gabriel Ratener Nov 3 '14 at 22:02
  • No, it wouldn't. However, I haven't studied it well enough to determine whether this can actually work. – reinierpost Nov 3 '14 at 23:03
  • I worked on this problem and could come up with the average case's lower bound. It was not what you stated. – InformedA Nov 4 '14 at 19:15

Your question on the exam is asking for average case analysis -- visiting all the cells to solve the maze is the worst case.

Informally think this way: Whenever you move to a new cell, you can move to at maximum 3 directions, which one direction is to go back to your previous cell (this choice is discarded since it's of course not what you want to do to explorer the maze.) In the two other options left, one of the direction will lead you to the target, the other one does not. What's the expectation of find the target in each move? Does it hint something $O(n \log n)$?

Also try to picture this as you are exploring a tree structure. What's the average height of a tree?

  • The average height of the tree seems irrelevant in this case, since the algorithm must backtrack through multiple branches until it finds a series of branches that lead to a solution. – Gabriel Ratener Nov 4 '14 at 18:18
  • Would the ratio of the number of cells needing to be visited to the total number of cells in the maze change as the maze scales? – Gabriel Ratener Nov 4 '14 at 18:20
  • @GabrielRatener "The average height of the tree seems irrelevant in this case, since the algorithm must backtrack through multiple branches until it finds a series of branches that lead to a solution." The algorithm could have found the solution in the first branch it visits without ever having to backtrack. You need to look at average case, not worst case – xiamx Nov 4 '14 at 20:04
  • True, but as n increases, the probability of never having to backtrack becomes very small. – Gabriel Ratener Nov 4 '14 at 21:01
  • Try to think how many times you will backtrack in average – xiamx Nov 4 '14 at 23:25

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.