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

Question

我正在浏览 the Wikipedia entry on maze generation algorithms并发现该文章强烈暗示不同的迷宫生成算法(随机深度优先搜索、随机 Kruskal 等)产生具有不同特征的迷宫。这似乎表明该算法会在所有单一解决方案迷宫(矩形网格上的生成树)的集合上生成具有不同概率分布的随机迷宫。

我的问题是:

1. 这是否正确？也就是说，我是否正确阅读了这篇文章，这篇文章是否正确？
2. 如果是，为什么？我看不出不同算法会产生不同分布的直观原因。

Answer 1

嗯，我认为很明显不同的算法会生成不同的迷宫。我们只讨论网格的生成树。假设你有一个网格 G，你有两种算法来为网格生成生成树:

算法A:

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

算法 B:

1. 与算法 A 相同，但将概率设置为 1% 而不是 99%

“显然”算法 A 产生具有大量水平 channel 的迷宫，而算法 B 产生具有大量垂直 channel 的迷宫。也就是说，迷宫中水平 channel 的数量与算法 A 生成的迷宫之间存在统计相关性。

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

LOL 我记得在一次科学 session 上，一位研究人员展示了她的算法的结果，该算法对“图形”做了一些事情。结果是统计的并呈现为“随机图”。有人问听众“你是从哪个分布的随机图形中绘制图形的？”答案是:“呃……它们是由我们的图形生成程序生成的”。呸!