产生最困难迷宫的迷宫算法？

Question

我一直在使用递归回溯算法，但它总是会产生非常简单的迷宫。哪种算法会产生最难解开的迷宫（如果合适，请提供有关辫子和偏向的信息）？

Answer 1

定量定义迷宫的“难度”并不容易。所以让我定性。

首先，递归Backtracker是一种“完美的迷宫”算法。它只产生一个解，就产生一个迷宫。关于迷宫生成的大多数工作都与生成完美的迷宫有关，因此我将仅针对这些迷宫。

迷宫算法有很多变种和分支。但实际上，只有12种基本的迷宫算法。我按照我个人（定性地和趣味性地）发现最难的顺序列出了它们：

1. 克鲁斯卡尔的
2. 普里姆斯
3. 递归Backtracker
4. 阿尔多·布罗德
5. 越来越多的树
6. 猎杀
7. 威尔逊的
8. 埃勒的
9. 蜂窝自动机 （简易）
10. 递归除法 （非常简单）
11. 响尾蛇 （可预测）
12. 二叉树 （有瑕疵）

我列出的前四名的难度并没有太大区别。对于那个很抱歉。也许您的实现存在缺陷。您很可能擅长做迷宫。尝试将它们放大。

Answer 2

虽然不是直接答案，但这篇关于可视化迷宫生成算法的文章是必看的。

Answer 3

您可以从这里检查迷宫生成算法：

迷宫分类