迷宫问题和递归backtracker算法 [英] maze problem and Recursive backtracker algorithm

问题描述

我要实现的递归backtracker算法来解决迷宫问题，但是我无法理解2.3命令（删除当前单元格和所选单元格之间的墙）将任何帮助我吗？

1. 标记为'访问'当前单元格
2. 如果当前单元格具有尚未被访问任何邻居
   1. 选择随机的未访问过的一位邻居
   2. 在当前单元格添加到堆栈
   3. 删除当前单元格，选择的单元格之间的墙
   4. 请选定单元格当前单元格
   5. 在递归调用这个函数
3. 其他
   1. 从堆栈中删除最后一个当前单元格
   2. 原路返回到previous执行此功能

编辑 其实我想一个算法使用栈解决迷宫问题。

解决方案

这算法是一个迷宫的发电机的不是一个迷宫的求解器的。我们的想法是要创建一个随机的迷宫。你也想​​在迷宫中所有的点是从所有其他点到达。

如果你只是随意删除墙壁很可能是你的迷宫将无法连接。递归回溯算法需要照顾的通过创建一个随机的走的，并沿着随机游走拆除围墙。递归回溯一部分，还可以步行到每一个细胞都在迷宫中，甚至当你达到一个死胡同。

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 ?

1. Mark the current cell as 'Visited'
2. If the current cell has any neighbours which have not been visited
   1. Choose randomly one of the unvisited neighbours
   2. add the current cell to the stack
   3. remove the wall between the current cell and the chosen cell
   4. Make the chosen cell the current cell
   5. Recursively call this function

3. else
   1. remove the last current cell from the stack
   2. Backtrack to the previous execution of this function

Edit In fact I want an algorithm to solve maze problem by using stack.

解决方案

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.

这篇关于迷宫问题和递归backtracker算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！