查找N点数据集中跨越5个点的最大总距离

我试图解决的问题涉及大约5000个GPS点的数据集，以及在该数据集内找到导致总距离最大的5个点的任务。查找N点数据集中跨越5个点的最大总距离

（注意，开始和结束不一定在同一地点）

天真的解决办法是遍历所有的点数据集中，直到最大总距离为五个嵌套循环发现，但这是不切实际鉴于距离计算是有点慢：

for (i = 0; i < points.length; i++) { 
    pointA = points[i]; 

    for (j = i; j < points.length; j++) { 
    pointB = points[j]; 
    distanceAB = distance(pointA, pointB); 

    for (k = j; k < points.length; k++) { 
     pointC = points[k]; 
     distanceBC = distance(pointB, pointC); 

     // ... 

     score = distanceAB + distanceBC + distanceCD + distanceDE; 
     if (score > winner.score) { 
     // save new winner 
     } 
    } 
    } 
}

是否有这个问题，需要做的工作少的解决方案？

来源

2017-07-17 TBieniek

你需要找到一个最长的5个顶点的简单路径吗？ – DAle

如果距离计算很慢，您可以缓存这些结果。它应该“仅”需要大约1250万个值。 –

@DAle这听起来大致就像我想要做的，是的 – TBieniek

非封闭有序路径连得5分

如果路径中的点要有序，那么你需要找到一个DAG有固定数量的边缘的最长路径。这可以通过简单的dynamic programming算法来完成。复发是

答案将是：max(f(i,4))。：

闭有序的连得5分

如果我们需要找到你的图片就像一个闭合路径（与有序的点），然后为每个start一点上，我们需要找到这个函数的值路径

与start为出发点的闭合路径的最大长度将
longest(start) = max(f(i,4) + dist(i,start))。

因此，答案将是：max(longest(start))。

来源

2017-07-17 12:22:19 DAle

查找N点数据集中跨越5个点的最大总距离

回答

相关问题