假设我们有一个长方形的海。它很大- 10000x20000。
我们也有岛屿。为了简单起见,让我们假设它们也是矩形的。我们知道他们的确切位置(坐标)。
如果我们有一艘船,在地图上的某个地方- (x1,y1),我们怎样才能找到到达地图上另一个点的最短路径(x2,y2)而不经过任何一个岛屿?
更新:到目前为止还没有任何限制--无论是船还是海。如果我们能通过增加一些来简化(并加快)事情--这是非常受欢迎的。
这条路甚至不一定是最好的--例如,它可以有10%的折扣--完全可以接受。
发布于 2010-12-02 14:05:55
这样的图形远远小于10000x20000网格,让我们在更好的时间内找到更多真实的路径。
更新:如果岛屿不是很大,您只需将船移向终点,并绕过它们左右边界的岛屿即可。
发布于 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分钟的时间。
发布于 2010-12-02 14:18:05
如果这些岛屿在大范围内相对稀疏,你可以使用我去年实现的一种算法,用于机器人在有物体可避免的环境中追逐移动的球。
我所做的就是在机器人、球和障碍物周围定义网格点,并在整个环境中添加一个稀疏的均匀网格。两个网格点之间的边界成本取决于障碍物与该边缘的距离(如果边界通过障碍物,则代价将是无限的)。然后用A*计算出最佳路线。这是在一台用Java编程的旧笔记本电脑上每秒完成40次。
https://stackoverflow.com/questions/4334097
复制相似问题