编程理论:解决迷宫

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)

每个节点都是路径的交汇点.D,I,J,L和O是死路,**是目标.当然,在您的实际树中,每个节点都有可能有三个孩子.

您的目标现在只是找到要遍历的节点以查找完成.任何ol'树搜索算法都可以.

看一下这棵树,通过简单地从树的最深部分的"跟踪"来看你的正确解决方案很容易:

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*算法,这是行业标准的寻路算法,它结合了广度优先搜索和启发式...有点像"智能广度优先搜索".

它基本上是这样的:

1. 将一条路径放入队列(您只走一步直进迷宫的路径).路径的"权重"由当前长度+距离末端的直线距离给出(可以用数学方法计算)
2. 弹出队列中权重最低的路径.
3. "爆炸"路径进入一步之后的每条路径.(即,如果你的路径是右左左右,那么你的爆炸路径是RLLRR和RLLRL,不包括穿过墙壁的非法路径)
4. 如果其中一条路径有目标,那么胜利!除此以外:
5. 计算爆炸路径的权重,并将它们全部放回队列中(不包括原始路径)
6. 按重量排序队列,先排低.然后从步骤#2重复

这是A*,我特别强调它,因为它或多或少是行业标准寻路算法,适用于所有寻路应用,包括从地图的一个边缘移动到另一个边缘,同时避开越野路径或山脉等.很好,因为它使用了尽可能短的距离启发式,这使它具有"智能".A*是如此多才多艺,因为如果你有任何问题,如果你有一个最短的距离启发式(我们很容易 - 直线),你可以应用它.

但值得注意的是,A*不是您唯一的选择.

事实上,维基百科类的树遍历算法仅列出了97个!(最好仍然会在此页面上链接)

抱歉长度= P(我倾向于絮絮叨叨)

Answer 2

存在许多迷宫解决算法:

http://en.wikipedia.org/wiki/Maze_solving_algorithm

http://www.astrolog.org/labyrnth/algrithm.htm#solve

对于机器人,Tremaux的算法看起来很有前景.

Answer 3

一个有趣的方法,至少我发现它很有趣,是使用细胞自动机.简而言之,被3"壁"细胞包围的"空间"细胞变成"壁"细胞.最后,剩下的唯一空间单元是通往出口的路径.

如果你看看Justin在他的答案中提到的树,那么你可以看到叶子节点有3个墙.修剪树直到你有一条路径.

Answer 4

这是我最喜欢的算法之一......

1) Move forward
2) Are you at a wall?
2a) If yes, turn left
3) Are you at the finish?
3a) If no, go to 1
3b) If yes, solved