algorithm - 在 N 点数据集中查找 5 个点的最大总距离

Question

我要解决的问题涉及一个包含大约 5000 个 GPS 点的数据集，以及在该数据集中找到导致最大总距离的 5 个点的任务。

(注意Start和End不一定在同一个位置)

天真的解决方案是五个嵌套循环，迭代数据集中的所有点，直到找到最大的总距离，但考虑到距离计算有点慢，这是不切实际的:

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
      }
    }
  }
}

是否有解决此问题的解决方案需要做更少的工作？

Answer 1

5 个点的非封闭有序路径

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

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

5 个点的封闭有序路径

如果我们需要像您的图片一样找到闭合路径(带有有序点)，那么对于每个 start 点，我们需要找到此函数的值:

以start为起点的闭合路径的最大长度为
最长(开始)= max(f(i，4)+ dist(i，开始))。

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