我找到了几个解决迷宫问题的算法。那些足够简单的算法只适用于出口在外部边界的情况（如Wall-follower、Pledge等）。
是否有更复杂的算法适用于边界形状随机、区域成本不平等且出口可能在迷宫内部的情况？（顺便说一下，所有元素都是二次的）
更新：此外，我们事先不知道迷宫的样子，只能看到特定的区域。
是否有更复杂的算法适用于边界形状随机、区域成本不平等且出口可能在迷宫内部的情况？（顺便说一下，所有元素都是二次的）
更新：此外，我们事先不知道迷宫的样子，只能看到特定的区域。
3个回答
4
如果您指的是像在纸上找到的“普通”二维迷宫，您可以使用图像分析来解决它们（使用图像分析）。但是，如果您以某种方式位于（2D/3D）迷宫内部并且必须找到出路，则可能应该使用一些机器学习技术。如果您不知道迷宫的确切外观，也就是说，您只能“看到”其中的一部分，这将起作用。
更新：除了最短路径查找算法系列之外，我还可以提到所谓的Trémaux算法，旨在供人类在迷宫内部使用。它类似于简单的递归回溯器，并将为所有迷宫找到解决方案。
描述：
当你走过一条通道时，请在身后画一条线以标记你的路径。当你遇到死路时，转身返回你来的路。当你遇到一个之前没有去过的十字路口时，请随机选择一条新的通道。如果你正在走一条新的通道，并遇到了一个之前去过的十字路口，请将其视为死路并返回你来的路，以免绕圈或错过其他通道。如果你正在走一条之前去过的通道（即已标记一次），并且遇到了一个十字路口，请选择任何可用的新通道，否则选择“旧”的通道。每个通道都将是空的（如果尚未访问），标记一次或标记两次（如果你被迫返回）。当你到达解决方案时，被标记恰好一次的通道将指示回到起点的直接路线。如果这个迷宫没有解决方案，你会发现自己回到起点，所有通道都被标记了两次。
更新：除了最短路径查找算法系列之外，我还可以提到所谓的Trémaux算法，旨在供人类在迷宫内部使用。它类似于简单的递归回溯器，并将为所有迷宫找到解决方案。
描述：
当你走过一条通道时，请在身后画一条线以标记你的路径。当你遇到死路时，转身返回你来的路。当你遇到一个之前没有去过的十字路口时，请随机选择一条新的通道。如果你正在走一条新的通道，并遇到了一个之前去过的十字路口，请将其视为死路并返回你来的路，以免绕圈或错过其他通道。如果你正在走一条之前去过的通道（即已标记一次），并且遇到了一个十字路口，请选择任何可用的新通道，否则选择“旧”的通道。每个通道都将是空的（如果尚未访问），标记一次或标记两次（如果你被迫返回）。当你到达解决方案时，被标记恰好一次的通道将指示回到起点的直接路线。如果这个迷宫没有解决方案，你会发现自己回到起点，所有通道都被标记了两次。
- Stefan Marinov
4
我担心Trémaux算法只对通道较窄的迷宫有效。在我的情况下，可能只有几个块有更多的自由单元格。 - Sergey
你说得对。问题在于，当我听到/读到“迷宫”时，我只想象到一个有狭窄通道的迷宫。 :)你总是可以使用最短路径算法。通过良好的建模和哈希函数，A*算法会给你带来方便。如果你能在你的情况下实现（斐波那契）堆，Dijkstra算法会变得非常快，并且你不必考虑哈希函数，这有时可能会很棘手。 - Stefan Marinov
所以我将使用A*（或其他我目前不太了解的复杂算法）来寻找到达当前移动期间所需的点的路径。但是，在这种类型的迷宫中，我如何决定从可见点集中移动到哪个点更好呢？我有一些想法，但不确定它们的有效性。 - Sergey
嗯，这个问题没有“完美”的答案。如果您没有任何标准来选择下一个点，可以使用欧几里得距离或曼哈顿距离，如果您无法计算此类距离或其他任何内容，则可以随机选择。如果要解决的迷宫之间存在一些相似之处，则可以为“A*”找到一个“聪明”的预测函数，但并不存在适用于所有情况的“完美迷宫求解器”。 - Stefan Marinov
2
“最短路径”算法可以找到通向出口的最短路径，无论出口在哪里。如果成本相等，则可以使用“BFS”算法；否则，需要使用类似于“Dijkstra算法”或“A*算法”（基本上是一种有信息的Dijkstra）来找到最短路径。
要使用这些算法，您需要将迷宫建模为图形：“G =（V，E）”，其中“V = {迷宫中所有可移动的方块}”，“E = {(u，v) |您可以在单个步骤中从u移动到v}”。
如果方块具有成本，请让每个方块的成本为“cost（v）”，您将需要一个加权函数：“w：E-> R”：将其定义为“w（u，v）= cost（v）”。
要使用这些算法，您需要将迷宫建模为图形：“G =（V，E）”，其中“V = {迷宫中所有可移动的方块}”，“E = {(u，v) |您可以在单个步骤中从u移动到v}”。
如果方块具有成本，请让每个方块的成本为“cost（v）”，您将需要一个加权函数：“w：E-> R”：将其定义为“w（u，v）= cost（v）”。
- amit
1
Pledge算法对你所说的迷宫非常有用。 它包括：
选择一个方向，如果你知道通往目标的大致方向，那就好了，但随机方向也可以。 假设你选择北方。
朝着那个方向走，直到遇到障碍物。
沿着障碍物前进，记录你转了多少。例如，向北走，你撞上一堵东西向的墙。 你向东转弯（90度），并沿着墙一路向南（180度），向西（270度）和再次向北（360度）。 直到你转过的角度为0，你才停止跟随墙壁。 所以你继续沿着它向西（270度它向相反的方向旋转），向南（180度），向东（90度），最后向北（0度）。 现在你可以停止跟随。
每当遇到障碍物时都要这样做。 最终，你将到达迷宫的最北部。 如果你还没有找到目标，因为你选择了错误的方向，请尝试使用东、南或任何最接近目标的方向重试。
选择一个方向，如果你知道通往目标的大致方向，那就好了，但随机方向也可以。 假设你选择北方。
朝着那个方向走，直到遇到障碍物。
沿着障碍物前进，记录你转了多少。例如，向北走，你撞上一堵东西向的墙。 你向东转弯（90度），并沿着墙一路向南（180度），向西（270度）和再次向北（360度）。 直到你转过的角度为0，你才停止跟随墙壁。 所以你继续沿着它向西（270度它向相反的方向旋转），向南（180度），向东（90度），最后向北（0度）。 现在你可以停止跟随。
每当遇到障碍物时都要这样做。 最终，你将到达迷宫的最北部。 如果你还没有找到目标，因为你选择了错误的方向，请尝试使用东、南或任何最接近目标的方向重试。
- Weux
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接