algorithm - 迷宫问题和递归回溯算法

Question

我想实现递归回溯算法来解决迷宫问题，但我无法理解 2.3 命令(“移除当前单元格和所选单元格之间的墙”)对我有帮助吗？

1. 将当前单元格标记为“已访问”
2. 如果当前小区有任何邻居没有被访问过
   1. 随机选择一个未访问过的邻居
   2. 将当前单元格加入栈中
   3. 移除当前单元格和所选单元格之间的墙
   4. 使所选单元格成为当前单元格
   5. 递归调用这个函数
3. 其他
   1. 从堆栈中移除最后一个当前单元格
   2. 回溯到该函数的上一次执行

编辑事实上，我想要一个算法来通过使用堆栈来解决迷宫问题。

Answer 1

该算法是迷宫生成器，而不是迷宫求解器。这个想法是你想创建一个随机迷宫。您还希望迷宫中的所有点都可以从所有其他点到达。

如果您只是随机移除墙壁，您的迷宫很可能不会连接。递归回溯算法通过创建随机行走 并沿着该随机行走移除墙壁来处理此问题。递归回溯部分允许你走到迷宫中的每一个单元格，即使你走到了死胡同。