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

Question

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

基本上，想象一个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/

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

Answer 1

通过抬高排序点。

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

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

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

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

总时间为O（N日志N），由最初的排序为主。