查找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個點的最大總距離

回答

相關問題