首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >船舶运动算法

问船舶运动算法
EN

Stack Overflow用户
提问于 2010-12-02 10:49:46
回答 4查看 653关注 0票数 2

假设我们有一个长方形的海。它很大- 10000x20000。

我们也有岛屿。为了简单起见,让我们假设它们也是矩形的。我们知道他们的确切位置(坐标)。

如果我们有一艘船,在地图上的某个地方- (x1,y1),我们怎样才能找到到达地图上另一个点的最短路径(x2,y2)而不经过任何一个岛屿?

更新:到目前为止还没有任何限制--无论是船还是海。如果我们能通过增加一些来简化(并加快)事情--这是非常受欢迎的。

这条路甚至不一定是最好的--例如,它可以有10%的折扣--完全可以接受。

EN

回答 4

Stack Overflow用户

回答已采纳

发布于 2010-12-02 14:05:55

  1. 与2D政治龙相邻的岛屿边界
  2. 将分离的政治龙的顶点(以及起点和终点)与边缘连接起来(它们不能跨越岛屿)
  3. 将A*应用于生成图

这样的图形远远小于10000x20000网格,让我们在更好的时间内找到更多真实的路径。

更新:如果岛屿不是很大,您只需将船移向终点,并绕过它们左右边界的岛屿即可。

票数 6
EN

Stack Overflow用户

发布于 2010-12-02 13:34:11

我会尝试将网格表示为一个图形,并运行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分钟的时间。

票数 1
EN

Stack Overflow用户

发布于 2010-12-02 14:18:05

如果这些岛屿在大范围内相对稀疏,你可以使用我去年实现的一种算法,用于机器人在有物体可避免的环境中追逐移动的球。

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

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/4334097

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档