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

Question

我正在浏览维基百科关于迷宫生成算法的词条，发现这篇文章强烈暗示不同的迷宫生成算法(随机深度优先搜索、随机克鲁斯卡尔等)会产生具有不同特征的迷宫。这似乎表明，这些算法会在所有单解迷宫（矩形网格上的生成树）的集合上产生具有不同概率分布的���机迷宫。

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

- templatetypedef

---

+1 - 这是一个有趣的问题。乍一看似乎很明显，但当你把它表述为关于可能迷宫空间中概率分布的问题时，它就变得非常有趣且不那么显而易见了。 - Nick Johnson

你的直觉会让你相信哪些算法会产生相同的分布？ - mhum

Answer 1

嗯，我认为很明显不同的算法会生成不同的迷宫。让我们来谈谈网格的生成树。假设你有一个网格G并且你有两个算法来为网格生成一棵生成树：

算法A:

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

算法B:

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

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

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

哈哈，我记得有一次科学会议上，一位研究人员介绍了她的算法在“图形”方面做了一些事情。结果是统计的，并针对“随机图”进行了展示。有人从观众中问道：“你从哪个随机图分布中绘制这些图形？”回答是：“嗯...它们是由我们的图形生成程序生成的。” 哎呀！

- Antti Huima

Answer 2

有趣的问题。这里是我的随机想法。

比较Prim算法和DFS算法，后者似乎更倾向于生成深度更深的树，仅仅是因为第一次“运行”有更多的空间可以用较少的分支创建深度更深的树。另一方面，Prim算法似乎会创建具有更多分支的树，因为每次迭代都可以选择任何开放的分支。

一个问法是看看每个算法产生深度> N的树的概率是多少。我有一种预感它们会不同。更正式的方法是给树的每个部分分配一些权重，并显示更可能被采取或尝试以某种其他方式表征空间，但我会手摆手并猜测它是正确的 :）。 我对于你认为它不会的原因很感兴趣，因为我的直觉是相反的。不，维基百科的文章没有给出令人信服的论据。

编辑

一个简单的方法是考虑一个初始树，它有两个孩子，总共有k个节点，例如：

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

选择一个随机节点作为起点和终点。深度优先搜索算法将生成两种迷宫之一，即整个树或者从起点到终点的直接路径部分。Prim算法将生成从起点到终点的“迷宫”，其中包括长度为1...k的次要路径。

- dfb

Answer 3

只有在您要求每个算法生成其可能的所有解决方案时，它才是统计学的。

您所感知到的统计偏差只是对首选第一解决方案的偏见。

这种偏见可能不是算法性质（集合论上），而是实现相关的（例如快速排序中枢选择的偏见）。

- Apalala

---

我不认为我理解你所说的内容。你能详细说明吗？链接中描述的所有算法都是经典非随机算法的随机版本。 - templatetypedef

我的意思是，除非你让每个算法生成它能够生成的所有迷宫，否则没有足够的信息来确定每个算法的随机性/偏差。我没有研究过这些算法，所以不知道它们是否能够产生所有可能的迷宫集合。 - Apalala

实际上，如果您能够证明其中一些算法无法生成所有可能的迷宫，我相信您立即就会发现它们具有不同的分布。 - templatetypedef

Answer 4

是的，这是正确的。您可以通过以不同的方式开始过程来生成不同的迷宫。一些算法从完全关闭的网格开始，通过移除墙壁来生成迷宫中的路径，而另一些算法则是从空网格开始，通过添加墙壁来留下一条路径。这本身就可以产生不同的结果。

- Rasika

---

算法能够产生不同的结果并不意味着这些结果的分布有什么不同......例如，我可以通过拆除墙壁或重新添加墙壁来创建相同的迷宫。 - templatetypedef