algorithm - 迷宫算法生成最困难的迷宫？

Question

我一直在玩递归回溯算法，但它总是会产生非常简单的迷宫。什么算法产生最难解决的迷宫(如果合适，请包括有关辫子和偏向方向的信息)？

Answer 1

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

首先，Recursive Backtracker 是一种“完美迷宫”算法；它使用一个且只有一个解决方案生成迷宫。大多数关于迷宫生成的工作都与生成完美的迷宫有关，因此我的回答仅限于此。

迷宫算法有很多变体和分支。但实际上，只有 12 种基本迷宫算法。我将它们按照我个人(定性和轶事)认为最难到最难的顺序列在这里:

1. Kruskal's
2. Prim's
3. Recursive Backtracker
4. Aldous-Broder
5. Growing Tree
6. Hunt-and-Kill
7. Wilson's
8. Eller's
9. Cellular Automaton (简单)
10. Recursive Division (很简单)
11. Sidewinder (可预测的)
12. Binary Tree (有缺陷)

我的榜单前四名难度相差不大。对于那个很抱歉。也许您的实现存在缺陷。很可能，你只是擅长走迷宫。尝试将它们变大。