Why do these labyrinth generation algorithms produce labyrinths with different properties?

Question

I looked at the Wikipedia entry on the labyrinth generation algorithms and found that the article strongly hinted that different labyrinth generation algorithms (randomized depth search, randomized Kruskal's, etc.) produce labyrinths with different characteristics. This, apparently, suggests that the algorithms produce random labyrinths with different probability distributions over the set of all labyrinths of one solution (spanning trees on a rectangular grid).

My questions:

• Is it correct? That is, I am reading this article correctly and is it written correctly?
• If so, why? I do not see an intuitive reason why different algorithms will produce different distributions.

Answer 1

Well, I think it's pretty obvious that different algorithms generate different mazes. Let me just talk about covering the trees of the grid. Suppose you have a grid G, and you have two algorithms for creating a spanning tree for the grid:

Algorithm A:

• Select any edge of the grid, with a probability of 99% choose horizontal, otherwise vertical
• Add an edge to the labyrinth unless adding it creates a loop
• Stop when each vertex is connected to each other vertex (full spanning tree)

Algorithm B:

• Like algorithm A, but set the probability to 1% instead of 99%

"Obviously, Algorithm A produces labyrinths with a large number of horizontal passes and Algorithm B lazurites with a large number of vertical passages. That is, there is a statistical correlation between the number of horizontal passages in the labyrinth and the labyrinth created by Algorithm A.

Of course, the differences between Wikipedia algorithms are more complex, but the principle is the same. Algorithms determine the space of possible labyrinths for a given grid in an uneven, structured manner.

LOL I remember a scientific conference where a researcher presented his results about its algorithm, which did something “for graphs”. The results were statistical and presented for "random graphs". Someone asked the audience: "What distribution of random graphs did you draw from the graph?" Answer: "... they were prepared by our graph generation program." Duh!

Answer 2

Interest Ask. Here is my random 2c.

Comparing Prim with, say, DFS, the latter seems to have a tendency to create deeper trees simply because the first “runs” have more space to create deep trees with fewer branches. On the other hand, the Prim algorithm seems to create trees with a large branching because any open branch can be selected at each iteration.

One way to ask this is to look at the probability that each algorithm will generate a depth tree> N. I have a hunch that they will be different. A more formal approach to proving this may be to assign some weights to each part of the tree and show that it will be more likely or try to characterize the space in some other way, but I will be undulating and guess it correctly :). I am interested in what makes you think that this will not happen, because my intuition was the opposite. And no, the Wiki article does not provide a convincing argument.

EDIT

One easy way to see this is to look at the initial tree with two children with a total of k nodes for example.

*---* ... * \--* ... * 

Select a random node as the beginning and end. DFS will produce one of two labyrinths, either the entire tree or part of it with a direct path from start to finish. The Prim algorithm will generate a “maze” with a direct path from beginning to end using secondary paths of length 1 ... k.

Answer 3

It is not statistical until you ask each algorithm to produce each solution.

What you perceive as a statistical bias is only a bias to the preferred, first solution.

This bias cannot be algorithmic (set-theory crosswise), but depending on the implementation (as a bias in choosing an axis in quick sort).

Answer 4

Yes, that's right. You can create different mazes by starting the process in different ways. Some algorithms start with a completely closed grid and remove the walls to create a path through the maze, while some start with an empty grid and add walls that go beyond the path. This in itself can lead to different results.