实现用于DFS、BFS迷宫的树

Question

我的程序从文件中获取一个 char 数组作为输入。该数组如下所示：

"#########",
"# #     #",
"# ##  # #",
"#     # #",
"### # ###",
"#   # # #",
"# # #####",
"#   #   #",
"#########",

我正在实现深度优先搜索和广度优先搜索来解决这个迷宫问题，从[1,1]开始，到[width - 1,height - 1]结束。

我考虑创建一个代表迷宫的树，然后使用每个算法分别遍历该树。

我将从每一行开始扫描空单元格，在每个空单元格中，其右侧、左侧和下方的每个单元格都将成为该单元格的子节点。它看起来像这样：

    for (int i = 0; i < width; i++)
    {
        for (int j = 0; j < height; j++)
        {
            if (isEmpty(maze[i][j]))
                    {
                         putChildren(maze[i-1][j], maze[i][j+1], maze[i+1][j]);
                         //this will check if it's a wall first
                    }       
    }

将树以这种方式实现，然后使用DFS和BFS遍历树是否是可行的策略？还是我应该采用其他方法？

- Powerbyte

---

你使用的是哪种编程语言？ - Roger Pate

C++ （我会进行编辑） - Powerbyte

Answer 1

很不错的项目，我很喜欢这样的东西。顺便问一下，你考虑过定向尝试算法（也称为A*算法）吗？我认为这对你会更好，特别是在处理2D数组时。它在通常情况下比其他方法具有更好的性能，并且您不需要使用链接单元格。此算法还有一些改进，包括与“尝试方向优先”方法相关联的内存链接。当然，如果您要处理非常庞大的矩阵时，请考虑使用此算法。

- esavier

---

我实际上计划稍后实现A*算法，但首先我想要实现深度优先搜索和广度优先搜索。我基本上想要实现所有这些算法来锻炼我的思维并熟悉它们以及人工智能的一般知识。 - Powerbyte

我在人工智能领域工作很多，如果我可以给你一个提示，那就是没有解决问题的好方法。你需要准备好面对可能需要实现两种算法并选择更适合情况（在问题分析后）。为了使迷宫求解器尽可能好，您应该允许您的实现“感知”周围环境。还要考虑制作2D（带有“visited”布尔标志）数组而不是图形。在某些情况下，这更容易，在某些情况下更难，但它值得实现，而不是通常的图形。 - esavier

即使您使用图形，也请使用visited标志，如果您遇到死路，可以将它们擦除。使用贪心算法，它将为您找到最快的解决方案并返回它。还有一种不错的算法（但需要实现），称为洪水填充房间标记。您应该假设房间之间有通道，并仅在树中标记那些通道以及“开始”和“结束”，洪水填充将仅考虑可通过的方式，并且应该丢弃任何像开放式房间或死路这样的地方。 - esavier

Answer 2

你的想法很好，也很直接，但我认为你误解了树和图的区别。

首先，没必要从迷宫图形中创建一棵树——可以在一般图上运行 BFS、DFS、A* 等算法。

而且，并不是每个迷宫都能表示成树的形式。

我们来看一个例子：

"#####",
"#   #",
"# # #",
"#   #",
"#####",

迷宫中显然存在一个循环，因此它不能被表示为一棵树。您的示例也有几个循环。

- pkacprzak