algorithm - 迷宫求解算法。复杂的迷宫

Question

我发现了几种解决迷宫的算法。那些足够简单的仅适用于出口在外部边界的情况（Wall-follower，质押......）。

是否有一些更复杂的算法来处理边界形状随机、区域成本不等以及出口可能位于迷宫内某处的情况？（顺便说一句，所有元素都是二次的）

更新：此外，我们不知道迷宫的外观，并且只能看到某些区域。

Answer 1

如果您指的是可以在纸上找到的“正常”二维迷宫，您可以使用图像分析来解决它们。但是，如果您不知何故位于（ 2D/3D）迷宫本身并且应该找到出路，您可能应该部署一些机器学习技术。如果你不知道你的迷宫到底长什么样，也就是你只“看到”它的一部分，这很有效。

更新：除了最短路径查找算法系列之外，我还可以涉及所谓的Trémaux 算法，该算法旨在供迷宫内的人使用。它类似于简单的递归回溯器，将为所有迷宫找到解决方案。

描述：

当你走下一条通道时，在你身后画一条线来标记你的路径。当你遇到死胡同时，转身回到你来的路。当你遇到一个你以前没有去过的路口时，随机选择一个新的通道。如果你走在一个新的通道上，遇到了一个你以前去过的路口，把它当作一个死胡同，回到你来的路，这样你就不会绕圈子或错过通道。如果沿着您之前访问过的通道（即标记一次）并且遇到一个路口，如果有可用的任何新通道，则选择“旧”通道。每个段落要么是空的（如果还没有访问过），要么被标记一次，要么被标记两次（如果你被迫回溯）。当您找到解决方案时，仅标记一次的路径将指示返回起点的直接方式。

Answer 2

最短路径算法正在寻找到出口的最短路径，无论出口在哪里。

如果成本相等 - BFS会做 - 否则，您需要类似dijkstra 算法或A* 算法[这基本上是一个知情的 dijkstra] 来找到最短路径。

要使用这些算法，您需要将迷宫建模为图形：G=(V,E)在哪里V = { all moveable squares in the maze }和E = {(u,v) | you can move from u to v in a sinlgle step }

如果正方形有成本让它cost(v)每个正方形，您将需要一个加权函数：：w:E->R将其定义为w(u,v) = cost(v)

Answer 3

质押算法对于您所说的那种迷宫很有用。它包括：

选择一个方向，如果你知道目标的大致方向很好，但随机方向也可以。假设你选择北方。

朝那个方向走，直到遇到障碍物。

跟随障碍物，跟踪你转动了多少。例如，向北行驶时，您会遇到一堵东西向的墙。您转东（90 天），然后沿着墙转南（180 天）、西（270 天），然后再转北（360 天）。你不会停止跟随墙壁，直到你转动的量变成 0。所以你继续跟随它向西（270d 它转向相反的方向），向南（180d），向东（90d），最后向北（0d） . 现在你可以停止关注了。

每当遇到障碍物时就这样做。您最终将到达迷宫的最北端。如果您仍然没有找到目标，因为您选择了错误的方向，请使用东或南或任何最接近目标的方向重试。