3 ms·

How would you express the algorithmic complexity of an algorithm like this, that incorporates a random walk which must hit a particular point before the algorit

by lukev 16y ago

How would you express the algorithmic complexity of an algorithm like this, that incorporates a random walk which must hit a particular point before the algorithm can proceed? In theory, this algorithm could run for any arbitrarily large amount of time. Although the probability of that is low, doesn't it make the worst-case time for this algorithm unacceptable?

jamis 16y ago
You're absolutely right. Both this one and Aldous-Broder both have a worst-case where the algorithm never terminates. As for whether the algorithm is "unacceptable", that depends on the application. For games? Yeah, this is probably far from your best option for generating mazes. But for cases where you absolutely must have a uniform spanning tree, your options are limited. Wilson's is much better than Aldous-Broder, but still not perfect. Robin Houston has described a variant that combines both Aldous-Broder and Wilson (doing AB until about 30% of the field is filled, and then switching to Wilson's) which empirically improves the odds quite a bit, but as long as you're doing a blind random walk, you're pretty much never guaranteed to finish.
- lukev 16y ago
  Ok... that's what I thought. Thanks. By the way, thanks for this series of articles... I've found it most diverting. I guess I'm the sort of person who enjoys "recreational maze generation" :p
jankassens 16y ago
The worst-case is indeed arbitrarily long, but the amortized runtime can be analyzed. See: http://en.wikipedia.org/wiki/Amortized_analysis http://en.wikipedia.org/wiki/Amortized_analysis
adrianN 16y ago
You can bound the expected cover time of a random walk on a graph. This is an intensively studied problem: http://scholar.google.de/scholar?q=covering+time+random+walk http://scholar.google.de/scholar?q=covering+time+random+walk iirc the expected cover time for any graph is polynomial with high probability. Something like |E|^3 or so.
- repsilat 16y ago
  Interestingly, even over an infinite grid you should get to your target with probability 1: http://www.math.cornell.edu/~mec/Winter2009/Thompson/randomwalks.html http://www.math.cornell.edu/~mec/Winter2009/Thompson/randomw...

by lukev 16y ago

jamis 16y ago

You're absolutely right. Both this one and Aldous-Broder both have a worst-case where the algorithm never terminates. As for whether the algorithm is "unacceptable", that depends on the application. For games? Yeah, this is probably far from your best option for generating mazes. But for cases where you absolutely must have a uniform spanning tree, your options are limited. Wilson's is much better than Aldous-Broder, but still not perfect. Robin Houston has described a variant that combines both Aldous-Broder and Wilson (doing AB until about 30% of the field is filled, and then switching to Wilson's) which empirically improves the odds quite a bit, but as long as you're doing a blind random walk, you're pretty much never guaranteed to finish.

lukev 16y ago
Ok... that's what I thought. Thanks. By the way, thanks for this series of articles... I've found it most diverting. I guess I'm the sort of person who enjoys "recreational maze generation" :p

jankassens 16y ago

The worst-case is indeed arbitrarily long, but the amortized runtime can be analyzed. See: http://en.wikipedia.org/wiki/Amortized_analysis http://en.wikipedia.org/wiki/Amortized_analysis

adrianN 16y ago

You can bound the expected cover time of a random walk on a graph. This is an intensively studied problem: http://scholar.google.de/scholar?q=covering+time+random+walk http://scholar.google.de/scholar?q=covering+time+random+walk iirc the expected cover time for any graph is polynomial with high probability. Something like |E|^3 or so.

repsilat 16y ago
Interestingly, even over an infinite grid you should get to your target with probability 1: http://www.math.cornell.edu/~mec/Winter2009/Thompson/randomwalks.html http://www.math.cornell.edu/~mec/Winter2009/Thompson/randomw...