3
$\begingroup$

Given a randomly generated maze of dimensions n x n, with the entrance point always being the top left corner (0,0) and the exit point always being the bottom right corner (n,n) what is the theoretical worst-case running time of finding a path through this maze?

  • The maze has a density of d (for example, if d = 0.5, then half of the maze is filled with obstacle/wall cells)
  • The path finding algorithm uses a stack to keep track of the path and for back tracking when necessary
  • The algorithm uses a search order of down, right, up, left
Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ What do you think? Have you tried finding some bad inputs? $\endgroup$
    – Yuval Filmus
    Commented Mar 9, 2017 at 19:56
  • 1
    $\begingroup$ Any reason why the one-hand-to-the-wall algorithm wouldn't work? $\endgroup$
    – gnasher729
    Commented Mar 10, 2017 at 9:40

1 Answer 1

Reset to default
-1
$\begingroup$

If you are only interested by the worst-case scenario, you need to consider an algorithm always picking the worst possible move at any point in time. The answer is intrinsic to both the method used to find the path through the maze and the maze topology. In fact, two randomly generated mazes might be very different from each other, one could have a path from start to end with no dead end while the other might have a lot of path intersection and dead ends. In the latter, a naive algorithm might perform worse if hitting a dead end mean searching backward to the last intersection before to attempt another path. Again, the answer is intrinsic to the algorithm used to traverse the maze and the maze topology.

Improve this answer
$\endgroup$
2
  • $\begingroup$ This doesn't seem to answer the question that was asked. Presumably the question was asking for the algorithm with the lowest worst-case running time. If you would like to request clarification or offer relevant commentary that doesn't quite answer the question, please post a comment rather than writing in the 'answer' field. Alternatively, if you can answer the question, I encourage you to edit your answer to add a full answer. Thank you! $\endgroup$
    – D.W. ♦
    Commented Mar 10, 2017 at 16:40
  • $\begingroup$ If you haven't visited a cell x, then it should be possible to have a labyrinth where you must walk through x to find a path. So I suppose that all n x n cells must be visited. On the other hand, none needs to be examined twice, because if you didn't find a way from x then you won't find one the next time. If your algorithm takes time t to visit a cell, worst case would be t * n^2. $\endgroup$
    – gnasher729
    Commented Mar 10, 2017 at 17:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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