2

假设我们有一个矩形海。它非常大 - 10000x20000。

我们也有岛屿。为简单起见，我们假设它们也是矩形的。我们知道它们的确切位置（坐标）。

如果我们有一艘船，在地图上的某个地方 - (x1, y1)，我们如何在不经过任何岛屿的情况下找到到地图上另一点 (x2, y2) 的最短路径？

更新：到目前为止，没有任何限制——无论是船还是海。如果我们可以通过添加一些来简化（并加快）事情 - 这是非常受欢迎的。

这条路甚至不必是最好的——例如，可以享受 10% 的折扣——完全可以接受。

4

4 回答 4

6
  1. 用 2D poligons 近似岛屿的边界
  2. 将分离的 poligons 的顶点（以及起点和终点）与边连接起来（它们不能跨越岛屿）
  3. 将 A* 应用于结果图

这样的图表远小于 10000x20000 网格，让您在更好的时间找到更真实的路径

更新：如果岛屿不大，您可以将船移向终点方向并绕过其左侧或右侧边界上的岛屿

于 2010-12-02T14:05:55.477 回答
1

我会尝试将网格表示为图形并运行 Dijkstra 算法。

该图可能需要 1G 甚至更多，但它适合任何现代计算机的 RAM。

算法复杂度为O(E + V*log(V))，即O(网格大小)。由于有〜10 ^ 8个节点，我想它一定是可行的。假设我们每个节点有大约 1000 个 CPU 滴答。如果我们有 4G CPU，一个滴答是 2.5*10^-10 秒，即我们有 2.5*10-7 秒。每个节点。对于 2*10^8 个节点，我们有 ~ 1 分钟。

于 2010-12-02T13:34:11.817 回答
0

如果岛屿在大视野中相对稀疏，您可以使用我去年实施的算法，用于机器人在需要避开物体的环境中追逐移动的球。

我所做的是在机器人、球和障碍物周围定义网格点，并在整个环境中添加一个稀疏的均匀网格。两个网格点之间的边缘成本取决于障碍物与该边缘的距离（如果边缘通过障碍物成本将是无限的）。然后使用 A* 计算最佳路线。这是在一台用 Java 编程的旧笔记本电脑上每秒完成 40 次。

于 2010-12-02T14:18:05.510 回答
0

与 Tiendil 的建议相关，LaValle 的规划算法书讨论了如果岛屿是 2D 多边形，在最短路径搜索的图形中包含哪些边。

于 2010-12-03T02:36:54.373 回答