-1

我使用深度优先搜索制作了一个迷宫生成器，它返回一组磅和空格来指示迷宫。例子：

char maze[height][width] =
{
    "#########",
    "#   #   #",
    "# ### # #",
    "# #   # #",
    "# # # ###",
    "#   # # #",
    "# ### # #",
    "#   #   #",
    "#########",
};

代理将始终从左上角 (maze[1][1]) 开始并从右下角 (maze[7][7]) 退出。

我正在尝试使用深度优先搜索来制作求解器。

问题是我是一个初学者到中级程序员，所以我很难理解如何在 C++ 中实现深度优先搜索，而且我在迷宫中实现它的难度更大。

我对堆栈、队列等有基本的了解。我也知道 DFS 在树中的工作原理（理论上差不多），但我的主要问题是如何在存储在 2D 数组中的迷宫中实现这一点。

我想专门学习 DFS，这样我就可以开始了，然后我将实施其他搜索策略（例如 BFS）来开始接触 AI。

编辑：我不想要现成的代码！！！我希望您帮助我了解如何将伪代码传输到 C++ 中进行迷宫！

4

1 回答 1

2

所以深度优先搜索的基本操作是：

深度优先搜索流程图

这对任何任意图的工作方式与对树的工作方式相同。树只是一个特例。你甚至可以把你的迷宫想象成一棵树：

#########
#123#   #
#4### # #
#5#   # #
# # # ###
#   # # #
# ### # #
#   #   #
#########

树

在树与任意图上使用此算法的唯一区别在于，由于树的层次结构，它隐含地知道树中的哪些节点已被访问。对于任意图，您可能具有如下结构：

#####
#187#
#2#6#
#345#
#####

在检查节点 8 时，您不想将节点 1 视为新的访问地点。

使用迷宫记住已访问过哪些节点的一种方法是在'#'遇到它们时立即填充它们。

我几乎已经弄清楚了如何表示代理的位置，如何移动他等等，但我的问题主要是如何使用堆栈来跟踪代理的位置。根据我在谷歌中的发现，有些人保留了一堆访问过的地方，但我从来没有真正理解什么时候从堆栈中删除位置，这是我最大的困惑

堆栈本身不用于跟踪访问了哪些地方。它只跟踪通过迷宫的当前“路径”。当您到达死胡同时，节点会从堆栈中删除；这些节点必须保持标记为已访问，即使它们已从堆栈中删除。如果删除这些节点也会导致这些节点“未被访问”，那么您的搜索可能会不断尝试并重试死胡同。

我建议你先画出一些小迷宫，然后使用上面的流程图手动穿过它们。这将使您更好地理解算法。以下是一些示例迷宫：

Start at O, finish at X

####    #####      #####     #####
#OX#    #O X#      #O#X#     #O  #
####    #####      #####     # #X#
                             #####

然后考虑流程图中的每个框，并考虑它使用什么数据，如何表示该数据，以及如何使用该数据在代码中实现框的操作。

于 2013-11-06T19:09:19.530 回答