你可以把你的迷宫想象成一棵树。
A
/ \
/ \
B C
/ \ / \
D E F G
/ \ \
H I J
/ \
L M
/ \
** O
(which could possibly represent)
START
+ +---+---+
| A C G |
+---+ + + +
| D B | F | J |
+---+---+ +---+---+
| L H E I |
+---+ +---+---+
| M O |
+ +---+
FINISH
(ignoring left-right ordering on the tree)
其中每个节点都是路径的交汇处。 D、I、J、L、O 是死胡同，** 是目标。
当然，在你的实际树中，每个节点有可能有多达three孩子们。
您现在的目标只是找到要遍历哪些节点才能找到终点。任何树搜索算法都可以。
查看这棵树，只需从树最深处的 ** 向上“追踪”，就可以很容易地看到正确的解决方案：
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*算法，这是行业标准的寻路算法，它将广度优先搜索与启发式相结合......有点像“智能广度优先搜索”。
它基本上是这样工作的：
- 将一条路径放入队列中（您只需走一步直接进入迷宫的路径）。路径的“权重”由其当前长度+距终点的直线距离（可以通过数学计算）给出
- 从队列中弹出权重最低的路径。
- 将路径“分解”为一步后可能出现的每条路径。 （即，如果您的路径是 Right Left Left Right，那么您的分解路径是 R L L R R 和 R L L R L，不包括非法穿过墙壁的路径）
- 如果其中一条路径有目标，那么胜利！否则：
- 计算分解后的路径的权重，并将其全部放回队列中（不包括原始路径）
- 按权重对队列进行排序，最低的在前。然后从步骤 #2 开始重复
那就是A*，我特别强调了它，因为它或多或少是行业标准的寻路算法all寻路的应用程序，包括从地图的一个边缘移动到另一个边缘，同时避开越野路径或山脉等。它工作得很好，因为它使用了最短可能距离启发式，这赋予了它“智能”。 A* 的用途如此广泛，因为对于任何问题，如果您有可用的最短距离启发式（我们的很简单 - 直线），您就可以应用它。
BUT值得注意的是，A* 是not你唯一的选择。
事实上，树遍历算法的维基百科类别仅列出97个！ （最好的仍然会在这一页之前链接）
抱歉，篇幅太长了=P（我倾向于胡言乱语）
