迷宫问题和递归回溯算法
我想实现递归回溯算法来解决迷宫问题，但我无法理解 2.3 命令（“移除当前单元格和所选单元格之间的墙”）对我有帮助吗？
- 则将当前单元格标记为“已访问”
- 如果当前单元格有任何未访问过的邻居，
- 随机选择一个未访问过的邻居
- 将当前单元格添加到堆栈
- 移除当前单元格和所选单元格之间的墙壁
- 将所选单元格设为当前单元格
- 递归调用此函数
- else
- 从堆栈中删除最后一个当前单元
- 回溯到该函数的上一次执行
编辑 事实上，我想要一种使用堆栈来解决迷宫问题的算法。
i want to implement the Recursive backtracker algorithm to solve maze problem, but i cant understand 2.3 Command ("remove the wall between the current cell and the chosen cell") would any help me ?
- Mark the current cell as 'Visited'
- If the current cell has any neighbours which have not been visited
- Choose randomly one of the unvisited neighbours
- add the current cell to the stack
- remove the wall between the current cell and the chosen cell
- Make the chosen cell the current cell
- Recursively call this function
- else
- remove the last current cell from the stack
- Backtrack to the previous execution of this function
Edit
In fact I want an algorithm to solve maze problem by using stack.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
该算法是迷宫生成器，而不是迷宫求解器。这个想法是你想创建一个随机迷宫。您还希望迷宫中的所有点都可以从所有其他点到达。
如果你只是随机移除墙壁，你的迷宫很可能不会连接起来。递归回溯算法通过创建随机行走并沿着该随机行走移除墙壁来解决这个问题。递归回溯部分允许您走到迷宫中的每个单元格，即使您到达死胡同。
That algorithm is a maze generator not a maze solver. The idea is that you want to create a random maze. You also want all points in the maze to be reachable from all other points.
If you just randomly remove walls it is likely that your maze will not be connected. The recursive backtracking algorithm takes care of this by creating a random walk and removing the walls along that random walk. The recursive backtracking part allows you to walk to every cell in the maze, even when you reach a dead end.
你的算法适用于
god模式。通常你应该这样做Your algorithm is for
godmode. Normally you should do拆墙简单来说就是拆墙！您从一个单元网格开始，每个单元都完全被 4 堵墙包围。当你在（2.1）周围随机移动时，你移除了连接细胞的壁。
Removing the wall simply means removing the wall! You start with a grid of cells, each of which is totally surrounded by 4 walls. As you move randomly around (2.1) you remove the wall joining the cells.