找到地球上,在整个是陡峭的大于30度的100个最长的斜坡算法?

问题描述 投票:2回答:1

这个问题是比较概念性的,因为我没有任何代码,它显示了作为现在。然而,我在想,如果我能得到我怎么能去编码这样的事情,而不必程序需要几年的时间来计算一些帮助。

基本上,想象一个wingsuit基地跳线需要至少30度的斜坡安全线飞到他的降落。我们如何去寻找最长的飞行路线,他可以采取在地球上?

        |----
        |     ----
        |         ----               A slope with a 3-1 glide angle
 100m   |             ----
        |                 ----
        |_________________________
                     300m

我们的星球上有〜面积510万平方公里。假设我们要采取一个数据点的每个200M,它出来作为一平方公里25个数据点。第n ^ 2这里的解决方案显然是不够的。

下面是我在一个潜在的解决方案的想法:遍历所有(510 * 25)万个可能的起始点。这些点连接到其相邻的点的邻居中的曲线图的形式。因为我们现在有相互连接的网格点的图表,我们可以删除不符合30度斜坡要求所有边缘。接下来,我们使用算法来找到一个向无环图的最长路径。

https://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/

请问我的解决方案的工作?是否有可能来计算?上其他解决方案的思考?

algorithm google-maps maps gis
1个回答
2
投票

通过抬高排序点。

为使每一个点的最长路径的排列,并用零初始化它 - 这就是路径的开始点。

降序高程的顺序处理的点。对于每一个点,最长路径的长度仰望它,并用它来调整其较低的邻居最长的路径。

每个点的最长路径将是正确的,当你处理它,因为它只能依赖于高海拔点,这将已经被处理。

记住,你看到最多的,这将是最长的路径的长度。如果你还记得它在哪里,那么你可以通过向后工作,多次找到与它的最长路径越高邻居重建的路径。

总时间为O(N日志N),由最初的排序为主。

© www.soinside.com 2019 - 2024. All rights reserved.