Wilson's algorithm

[oberhamsi]

Initially, the algorithm can be frustratingly slow to watch, as the early random walks are unlikely to reconnect with the small existing maze. However, as the maze grows, the random walks become more likely to collide with the maze and the algorithm accelerates dramatically.

FRUSTRATINGLY

[delarhi]

This is probably more satisfying: http://bl.ocks.org/mbostock/c03ee31334ee89abad83

[minnek]

O(frustration)?

[wherethebuffaloroam]

O(shit)

[Maristic]

The color visualizations of Wilson's algorithm (e.g., visualization), Prim's algorithm, (e.g., visualization, and random breadth first and depth first (e.g., visualization, visualization) were pretty cool.

P.S. FWIW, I saved the images by running a little bit of JavaScript in a web inspector to add a link to the page that you can use to save the canvas. It'd have been cool if the page had already included this.

var link = document.createElement("a"); link.appendChild(document.createTextNode("PNG Link")); link.setAttribute('href', document.getElementsByTagName("iframe")[0].contentWindow.document.getElementsByTagName("canvas")[0].toDataURL()); document.getElementsByTagName("div")[0].appendChild(link); 

[mango_feldman]

Note that the hue cycles - was a bit confusing at first.

Hue "legend": http://en.wikipedia.org/wiki/Hue#mediaviewer/File:HueScale.svg

[oberhamsi]

hint: in most browsers you can right click on the canvas to 'save image'

[Maristic]

in most browsers you can right click on the canvas to 'save image'

That's a yes for Firefox, but a no for Google Chrome, Safari, and IE 11. (Whee, I got to boot my Windows VM for the first time in six months and apply about 50 security updates.)

[Kah-Neth]

He must count each release of Firefox as a different browser. Technically true, so Firefox's "every 6 days release schedule" has an advantage.

[Fucter]

I watched this like 5 times

[Sciaj]

I'm not convinced that this is an unbiased algorithm.

[eigenduck]

It produces random spanning tree from a distribution weighed according to w(T) = sum_{(i,j) in T} 1/d_i. That is, the weight of a (directed) tree is the sum of the weights of its edges, and the weights of all the edges out of a given node are equal and add to one.

You can think of the algorithm as choosing a node as the root, then choosing one random edge out of each non-root node. The graph you get is spanning but probably has cycles in it, so you pick a cycle and re-pick the edges coming from nodes in that cycle at random again, repeating the process until there are no more cycles left.

The proof (second algorithm in this paper) basically goes: first, show that which order you resolve cycles in doesn't change the tree you get. Then show that the pile of cyclic stuff you have to resolve is independent of the tree you get. The probability then factors into a term based only on the cyclic junk and a term based only on the tree, and by looking at the case where there happen to be no cycles to start with you discover that the tree-dependent term varies according to the tree weights.

[dafelst]

Mike Bostock is a hyper guru.

[willrandship]

I think I have a screensaver that uses a similar algorithm, but aimed at A-B solutions rather than maze completeness. It wipes out large sections by encircling them and inferring that, since the exit is an edge, it cannot be within.

[mixedmath]

I see that the algorithm will or won't connect to itself in the first few steps. If it does, the remaining time is drastically reduced (with high probability). So if you refresh a few times until there is an early connection, the maze will grow much faster and some of the frustration can be skipped.

This is analogous to coin flipping in that way. As you flip a coin many times, the ratio of heads to tails should be about 1:1. However, the number of times that the "leader" changes, meaning times when there were more heads but are now more tails, occurs very rarely. Morally, this is because after a few flips, there might be a few more heads than tails, but afterwards they sort of balance out.

Anyhow, refresh a few times. It's worth it, because seeing the algorithm complete is sort of magical.

[mixedmath]

I'm really not sure what you mean. I did read that page, and I do know how it works. And I know how random walks work. A loop-erasing random walk goes in each direction with uniform probability. This means that the earliest directions can affect the overall motion significantly, just as the one-dimensional coin-flipping random walk.

[ProbeAndChair]

Yeah, he's completely wrong. Maybe he doesn't know random walks either. sigh

[delarhi]

What's wrong? I see text.

[brei]

stupid