用 "islands" 解决迷宫
Solving maze with "islands"
我有这个迷宫布局，但我在思考如何实施解决方案时遇到了困难：
我知道迷宫求解算法有很多资源，例如http://www.astrolog.org/labyrnth/algrithm.htm 但我不确定哪种算法最适合给定的迷宫。
标有“*”的三个区域是 MazeSolver 在能够从地图顶部的入口退出迷宫之前需要前往的位置。
我将不胜感激解决迷宫岛部分的伪代码。我会寻找一个简单的解决方案，最佳时间并不是真正的问题。问题是，即使事先向解算器提供了迷宫的概览，但在迷宫解算器实际执行迷宫时可能并不完全准确，因此它比预先编码或使用无所不知的算法要复杂一些迷宫的视图和需要 "half" human/doable 如果你明白我的意思...
虽然每次救援都会向 robot/robot 程序员提供一张矿山地图，但由于新的采矿或事件造成的破坏，该地图可能已过时。
对于此应用程序，机器人需要首先定位所有救援区域并确定它们是否被占用。机器人必须完全自主。调查完这些后，机器人应该检查所有供人类使用的通道。
机器人应该也能自主导航。虽然 GPS 系统是一个自然的选择，但在这种情况下，由于岩石天花板的厚度阻止了任何 GPS 信号，因此无法使用它，因此您还需要为机器人设计一个导航系统。为此，可以向机器人添加小的硬件改动，例如额外的传感器或可部署的无线电信标。请注意，至少有一个避难所位于“岛屿”中。
假设您不是在寻找走出迷宫的最短路径 - 只是任何路径，请为您的岛屿创建一些顺序：island1,island2,...,islandk.
现在，假设您知道如何解决 "regular" 迷宫，您需要从以下位置找到路径：
start->island1, island1->island2, ...., islandk->end
一些评论：
- 可以使用 BFS, or DFS 解决 "regular" 迷宫（虽然后者不是最优的）。
- 如果您正在寻找更高效的解决方案，您可以使用
all-to-all shortest path 而不是多个 "regular" 迷宫求解。
- 如果您正在寻找最短路径，这是 Traveling Salesman Problem. Possible solution is discussed here 的变体。
- 如果您还想遍历所有段落，可以使用 DFS 来完成，一直持续到发现所有节点。同样，这不会是最短的此类路径，但找到最短路径将是 NP-Hard。
这个问题与 Travelling salesman problem 问题有关，它是 NP-Hard，所以我不希望有任何快速解决大量岛屿的方法。
对于少量岛屿，您可以这样做：对于每 2 个岛屿（包括您的起始位置），计算它们之间的最短路径。由于您对相对较低比例的顶点之间的距离感兴趣，我建议使用 Dijkstra's algorithm，因为它相对容易并且可以手动完成（对于相当大的 graf）。
现在您拥有所有兴趣点之间的最短距离，此时您需要找到它们之间的哈密顿最优路径。幸运的是，距离满足一个度量，所以你可以有 2-approximation（简单，甚至手工）或什至 3/2-approximation（不那么容易）算法，但没有已知的多项式算法。
对于 3 个岛屿的完美解决方案，您只需检查 6 种访问方式（简单），但对于 6 个岛屿，您可以通过 720 种方式访问它们，而 n 在 n! 祝你好运。
我有这个迷宫布局，但我在思考如何实施解决方案时遇到了困难：
我知道迷宫求解算法有很多资源，例如http://www.astrolog.org/labyrnth/algrithm.htm 但我不确定哪种算法最适合给定的迷宫。
标有“*”的三个区域是 MazeSolver 在能够从地图顶部的入口退出迷宫之前需要前往的位置。
我将不胜感激解决迷宫岛部分的伪代码。我会寻找一个简单的解决方案，最佳时间并不是真正的问题。问题是，即使事先向解算器提供了迷宫的概览，但在迷宫解算器实际执行迷宫时可能并不完全准确，因此它比预先编码或使用无所不知的算法要复杂一些迷宫的视图和需要 "half" human/doable 如果你明白我的意思...
虽然每次救援都会向 robot/robot 程序员提供一张矿山地图，但由于新的采矿或事件造成的破坏，该地图可能已过时。
对于此应用程序，机器人需要首先定位所有救援区域并确定它们是否被占用。机器人必须完全自主。调查完这些后，机器人应该检查所有供人类使用的通道。
机器人应该也能自主导航。虽然 GPS 系统是一个自然的选择，但在这种情况下，由于岩石天花板的厚度阻止了任何 GPS 信号，因此无法使用它，因此您还需要为机器人设计一个导航系统。为此，可以向机器人添加小的硬件改动，例如额外的传感器或可部署的无线电信标。请注意，至少有一个避难所位于“岛屿”中。
假设您不是在寻找走出迷宫的最短路径 - 只是任何路径，请为您的岛屿创建一些顺序：island1,island2,...,islandk.
现在，假设您知道如何解决 "regular" 迷宫，您需要从以下位置找到路径：
start->island1, island1->island2, ...., islandk->end
一些评论：
- 可以使用 BFS, or DFS 解决 "regular" 迷宫（虽然后者不是最优的）。
- 如果您正在寻找更高效的解决方案，您可以使用 all-to-all shortest path 而不是多个 "regular" 迷宫求解。
- 如果您正在寻找最短路径，这是 Traveling Salesman Problem. Possible solution is discussed here 的变体。
- 如果您还想遍历所有段落，可以使用 DFS 来完成，一直持续到发现所有节点。同样，这不会是最短的此类路径，但找到最短路径将是 NP-Hard。
这个问题与 Travelling salesman problem 问题有关，它是 NP-Hard，所以我不希望有任何快速解决大量岛屿的方法。
对于少量岛屿，您可以这样做：对于每 2 个岛屿（包括您的起始位置），计算它们之间的最短路径。由于您对相对较低比例的顶点之间的距离感兴趣，我建议使用 Dijkstra's algorithm，因为它相对容易并且可以手动完成（对于相当大的 graf）。
现在您拥有所有兴趣点之间的最短距离，此时您需要找到它们之间的哈密顿最优路径。幸运的是，距离满足一个度量，所以你可以有 2-approximation（简单，甚至手工）或什至 3/2-approximation（不那么容易）算法，但没有已知的多项式算法。
对于 3 个岛屿的完美解决方案，您只需检查 6 种访问方式（简单），但对于 6 个岛屿，您可以通过 720 种方式访问它们，而 n 在 n! 祝你好运。