您可以将迷宫想象成一棵树。
一个 / / 公元前 ///DEFG / HIJ / LM / ** O（可能代表） 开始 + + --- + --- + | ACG | + --- + + + + | DB | F | J |+ --- + --- + + --- + --- +| LHEI |+ --- + + --- + --- + | MO | + + --- + 完（忽略树上的左右顺序）
每个节点都是路径的交汇点。D，I，J，L和O是死胡同，**是目标。当然，在您的实际树中，每个节点最多可以拥有 三个 子节点。
现在，您的目标只是找到要遍历的节点以找到终点。任何其他的树搜索算法都可以。
查看树，只需从树的最深处的**中“追溯”即可轻松找到正确的解决方案：
A B E H M **
请注意，当您的迷宫中有“圈”时，这种方法 只会 变得 稍微
复杂一些（即，如果可能的话，没有回溯，您可以重新输入已经遍历的段落）。检查评论，找到一个不错的解决方案。
现在，让我们看看您提到的应用于该树的第一个解决方案。
您的第一个解决方案基本上是“ 深度优先搜索”
，它的确不错。实际上，这是一个很好的递归搜索。基本上，它说：“始终首先使用最右边的方法。如果什么都没有，请回溯到可以直行或左行的位置，然后重复。
深度优先搜索将按以下顺序搜索上述树：
A B D (backtrack) E H L (backtrack) M ** (backtrack) O (backtrack thrice) I(backtrack thrice) C F (backtrack) G J
请注意，一旦找到**，您就可以停止。
但是，当您实际编写深度优先搜索的代码时，使用 递归编程
可以使一切变得容易得多。即使是迭代方法也可以使用，并且您不必显式编程如何回溯。查看链接的文章以了解实现。
搜索树的另一种方法是“ 广度优先”
解决方案，该解决方案按深度搜索树。它将按以下顺序搜索上面的树：
A (next level) B C (next level) D E F G (next level)H I J (next level) L M (next level) ** O
请注意，由于迷宫的性质，广度优先的平均节点数量要多得多。广度优先是很容易实现的，它有一个要搜索的路径队列，并且每次迭代都会从队列中弹出一个路径，通过一步一步获取所有可以变成的路径，然后放置这些新路径来“爆炸”在队列末尾。没有明确的“下一级”命令可以编码，而这些命令只是为了帮助理解。
实际上，有很多搜索树的方法。我刚刚提到了两种最简单，最直接的方法。
如果您的迷宫非常非常长且很深，并且有循环和疯狂，并且很复杂，那么我建议您使用 A
*
算法，这是行业标准的寻路算法，将广度优先搜索与启发式技术结合在一起……类似“智能广度优先搜索”。
它基本上是这样的：
- 将一条路径放在队列中（您仅一步步进入迷宫的路径）。路径具有“权重”，该权重由其当前长度+到端点的直线距离（可以通过数学计算）得出
- 从队列中弹出权重最低的路径。
- 一步之后，将路径“分解”为所有路径。（即，如果您的路径为“左右”，则您的分解路径为RLLRR和RLLRL，不包括穿过墙壁的非法路径）
- 如果这些路径之一有目标，那就胜利！除此以外：
- 计算爆炸路径的权重，并将所有权重放回队列（不包括原始路径）
- 按重量对队列进行排序，从最低到最低。然后从步骤2重复
这就是 A ，我特别介绍了它，因为它或多或少是针对寻路的 所有
应用的行业标准寻路算法，包括从地图的一个边缘移动到另一边缘，同时避开越野道路或山脉等。很好，因为它使用了 最短的距离启发式算法 ，这使其具有“智能”。A
用途广泛，因为如果遇到任何问题，如果您有尽可能短的距离启发式算法（我们很容易-直线），则可以应用它。
但是 请注意，A * 不是 您唯一的选择，这非常有价值。
实际上，树遍历算法的维基百科类别仅列出了97个！（最好的仍然会在此页面的前面链接）
抱歉，长度= P（我倾向于漫步）
