algorithm - 编程理论 : Solve a maze

Question

解迷宫的可能方法有哪些？
我有两个想法，但我认为它们不是很优雅。

基本情况:我们有一个矩阵，这个矩阵中的元素以一种表示迷宫的方式排序，有一条进路和一条出路。

我的第一个想法是让机器人沿着迷宫的一侧穿过迷宫，直到它走出迷宫。我认为这是一个非常缓慢的解决方案。

第二个遍历标有 1 的每个连续项目，检查它可以去哪里(上、右、下、左)选择一种方式，然后继续它的路径。这甚至比第一个慢。

当然，如果我让这两个机器人在每个连接点都使用多线程，速度会快一点，但这也不是最好的方法。

需要有更好的解决方案来让机器人穿过迷宫。

编辑
首先:感谢您的精彩回答!

我的问题的第二部分是:如果我们有一个多维图，该怎么办？是否有特殊做法，或者 Justin L. 的答案是否也适用于此？
我认为这不是这种情况的最佳方式。

第三个问题:
这些迷宫求解器算法中哪一个是最快的？ (纯属假设)

Answer 1

您可以将迷宫想象成一棵树。

     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)

Where each node is a junction of paths. D, I, J, L and O are dead ends, and ** is the goal.Of course, in your actual tree, each node has a possibility of having as many as three children.

Your goal is now simply finding what nodes to traverse to to find the finish. Any ol' tree search algorithm will do.

Looking at the tree, it's pretty easy to see your correct solution by simply "tracing up" from the ** at the deepest part of the tree:

A B E H M **

请注意，当您在迷宫中有“循环”时，此方法只会稍微变得更复杂(即，如果可能，无需回溯，您可以重新进入您已经遍历的段落通过)。查看评论以获得一个不错的解决方案。

现在，让我们看看您提到的应用于这棵树的第一个解决方案。

您的第一个解决方案基本上是 Depth-First Search ，这真的不是那么糟糕。这实际上是一个非常好的递归搜索。基本上，它说的是，“始终首先采取最右边的方法。如果那里什么都没有，则原路返回，直到第一个可以直行或向左走的地方，然后重复。

深度优先搜索将按以下顺序搜索上面的树:

A B D (backtrack) E H L (backtrack) M ** (backtrack) O (backtrack thrice) I
(backtrack thrice) C F (backtrack) G J

请注意，您可以在找到 ** 后立即停止。

但是，当您实际编写深度优先搜索代码时，使用递归编程 会使一切变得容易得多。甚至迭代方法也可以工作，而且您永远不必明确编程如何回溯。查看链接文章以了解实现。

另一种搜索树的方法是 Breadth-First解决方案，按深度搜索树。它会按以下顺序搜索上面的树:

A (next level) B C (next level) D E F G (next level)
H I J (next level) L M (next level) ** O

请注意，由于迷宫的性质，广度优先检查的平均节点数量要多得多。广度优先很容易实现，方法是有一个路径队列来搜索，每次迭代从队列中弹出一条路径，通过获取它在一步后可以变成的所有路径并将这些新路径放入“爆炸”在队列的末尾。没有明确的“下一级”代码命令，这些命令只是为了帮助理解。

其实有一个整体expansive list of ways to search a tree .我刚才提到了两种最简单、最直接的方法。

如果你的迷宫又长又深，有循环和疯狂，而且很复杂，我建议 A*算法，这是行业标准的寻路算法，它将广度优先搜索与启发式算法相结合……有点像“智能广度优先搜索”。

它基本上是这样工作的:

1. 将一条路径放入队列中(您只需要一步直接进入迷宫的路径)。一条路径有一个“权重”，由它的当前长度+它到终点的直线距离(可以用数学计算)
2. 从队列中弹出权重最低的路径。
3. 将路径“分解”为一步后可能出现的每条路径。 (即，如果你的路径是 Right Left Left Right，那么你的分解路径是 R L L R R 和 R L L R L，不包括非法的穿墙路径)
4. 如果其中一条路径有目标，那么胜利!否则:
5. 计算分解路径的权重，全部放回队列(不包括原路径)
6. 按权重对队列进行排序，从小到大。然后从第 2 步开始重复

那是 A*，我特别强调它是因为它或多或少是适用于所有寻路应用的行业标准寻路算法，包括从一个边缘移动将 map 切换到另一张 map ，同时避开越野路径或山脉等。它之所以如此有效，是因为它使用了最短距离启发式，这赋予了它“智能”。 A* 用途广泛，因为对于任何问题，如果您有可用的最短距离启发式算法(我们的很简单——直线)，您就可以应用它。

但是值得注意的是，A* 不是您唯一的选择。

事实上，wikipedia category of tree traversal algorithms单独列出97个! (最好的还是会在之前链接的 this page 上)

抱歉，长度=P(我倾向于漫无边际)