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

Question

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

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

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

Answer 1

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

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

Answer 2

您的算法适用于god模式。通常你应该做

1. 如果当前单元格是出口，则完成
2. 如果当前单元格有任何未访问过的不是墙的邻居
   
   1. 随机选择未访问的非墙邻居 之一
   2. 将当前单元格添加到堆栈中
   3. 没有什么
   4. 使所选单元格成为当前单元格
   5. 递归调用这个函数
3. 别的
   
   1. 从堆栈中删除最后一个当前单元格
   2. 回溯到该函数的上一次执行

Answer 3

拆墙就是拆墙！你从一个网格开始，每个网格都被 4 面墙完全包围。当你随机移动 (2.1) 时，你移除了连接单元的墙。