为什么这些迷宫生成算法会生成具有不同属性的迷宫？

Question

我正在浏览关于迷宫生成算法的维基百科条目,并发现该文章强烈暗示不同的迷宫生成算法(随机深度优先搜索,随机Kruskal等)产生具有不同特征的迷宫.这似乎表明算法在所有单解迷宫(在矩形网格上生成树)的集合上产生具有不同概率分布的随机迷宫.

我的问题是:

1. 它是否正确？也就是说,我正确阅读这篇文章,这篇文章是否正确？
2. 如果是这样,为什么？ 我没有看到不同算法产生不同分布的直观原因.

Answer 1

嗯,我认为很明显不同的算法生成不同的迷宫.我们来谈谈网格的生成树.假设您有一个网格G,并且您有两种算法来为网格生成生成树:

算法A:

1. 选择网格的任何边缘,99%概率选择水平边缘,否则选择垂直边缘
2. 将边缘添加到迷宫中,除非添加它将创建一个循环
3. 当每个顶点连接到每个其他顶点时停止(生成树完成)

算法B:

1. 作为算法A,但将概率设置为1%而不是99%

"显然"算法A产生具有大量水平通道的迷宫,算法B迷宫具有许多垂直通道.也就是说,迷宫中的水平通道数与算法A产生的迷宫之间存在统计相关性.

当然,维基百科算法之间的差异更复杂,但原理是相同的.算法以非均匀的结构化方式为给定网格采样可能的迷宫空间.

大声笑我记得在一次科学会议上,一位研究人员向她展示了她的算法结果,该算法做了"用于图表"的事情.结果是统计的并且呈现为"随机图".有人问观众"你从哪个随机图的分布中绘制图表？" 答案是:"呃......它们是由我们的图形生成程序生成的".咄!