编程理论：解决迷宫问题

Question

编程理论：解决迷宫问题

algorithmmaze

76

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

基本情况：我们有一个矩阵，这个矩阵中的元素按一定方式排序，代表着一个迷宫，有一个入口和一个出口。

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

第二种方式是经过每一个标有1的连续项，检查它可以往哪里走（上、右、下、左），选择一个方向并继续前进。这比第一种方式还要更慢。

当然，在每个交叉口上将两个机器人多线程化会快一些，但那也不是最好的方式。

需要有更好的方法来让机器人通过迷宫。

编辑
首先：感谢大家的好回答！

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

第三个问题：
这些迷宫解决算法中哪个/哪些是最快的？（纯属假设）

- therufa

7

我通常从结尾开始，然后逆推着做。这个方法几乎每次都有效！ - Joe Phillips

1

你可以阅读http://www.cut-the-knot.org/ctk/Mazes.shtml，这是一个关于迷宫的不错介绍。 - Dr. belisarius

6

电脑不知道何为起点和终点，从终点开始并不能提供任何帮助。 - Dominique

1

@Dominique 仅是主观观察：人类迷宫设计师倾向于在迷宫出口只绘制一条分支。这就是为什么通常从终点开始搜索会快一些 - 当然，对于Justin L.的ASCII艺术来说并非如此。 - Dr. belisarius

1

多维图形也可以用树来表示 =) - Justin L.

显示剩余3条评论

14个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- comonad · Answer 1

有许多算法以及许多不同的设置可以指定哪个算法最佳。以下是一个有趣设置的想法：

假设您拥有以下属性...

您移动机器人并希望最小化其运动，而不是其CPU使用率。
该机器人可以检查仅其相邻单元格或沿走廊查看或不查看横向。
它有GPS。
它知道其目的地的坐标。

然后，您可以设计一种人工智能，它...

每次接收到有关迷宫的新信息时，绘制地图。
计算所有未观察位置（以及自身和目标位置）之间的最小已知路径长度。
可以根据周围结构优先检查未观察位置。（如果从那里无法到达目的地...）
可以根据到目的地的方向和距离优先检查未观察位置。
可以根据收集信息的经验优先检查未观察位置。（平均能看多远，需要走多远？）
可以优先检查未观察位置以找到可能的捷径。（经验：是否存在许多循环？）

- raghavankl · Answer 2

这个 Azkaban 算法可能会对您有所帮助， http://journals.analysisofalgorithms.com/2011/08/efficient-maze-solving-approach-with.html

- Tyler Durden · Answer 3

解决迷宫问题的最佳方法是使用连通性算法，例如并查集，这是一种准线性时间算法，假设路径压缩已完成。

并查集是一种数据结构，可以告诉您集合中两个元素是否具有传递性连接。

要使用并查集数据结构来解决迷宫问题，首先使用邻居连通性数据来构建并查集数据结构。然后对并查集进行压缩。为了确定迷宫是否可解，比较入口和出口值。如果它们具有相同的值，则它们是相连的，迷宫是可解的。最后，要找到解决方案，您从入口开始，并检查与其每个邻居关联的根。只要找到一个以前未访问过的邻居，其根与当前单元格相同，您就会访问该单元格并重复该过程。

这种方法的主要缺点是，如果有多条路径，它将无法告诉您通过迷宫的最短路线。

- Jubin Chheda · Answer 4

虽然不是专门针对你的情况，但我遇到过几个编程竞赛问题，发现李氏算法非常方便快速地编写代码。它并不是所有情况下最有效的算法，但很容易实现。这里是我为一个比赛编写的一个示例。