距離計算優化

我正在寫一個算法來計算2d平面中點的最近鄰點。目前，我蠻力計算每一個距離通過兩個for循環距離計算優化

for(i=0; i<N ;i++){ 
    for (j=0; j<N; j++{ 
     /* distance computation */ 
     /* remember smallest distance for all i */ 
    } 
}

我已經有一個if(i==j) continue;語句，使我們避免了計算相同點之間的距離。我想知道如何進一步優化這個算法。例如，我如何解釋距離（i，j）=距離（j，i）的對稱性？我還有其他意見嗎？

此外，你可以向我描述另一種算法，這將是更好的方法來執行此計算？我研究過二叉樹，但是我不確定它們是如何應用於我的問題的！

來源

2017-02-24 AngusTheMan

你想返回一個解決方案或所有方案的算法的細節？（有一般的多最近的鄰居） – niceman

你可以通過j在i+1來解釋對稱性。這也將照顧i == j情況沒有特殊情況：

for (i = 0 ; i != N ; i++) { 
    for (int j = i+1 ; j != N ; j++) { 
     dist = ... // Compute the distance 
     distance[i][j] = distance[j][i] = dist; // Set in both directions 
    } 
}

來源

2017-02-24 12:14:37 dasblinkenlight

-1

計算出所有的點（0,0）之間的距離。然後按升序排序距離。

現在，特殊點的後繼者和前輩是最近的鄰居。

來源

2017-02-24 12:21:49 Liju

即使在1D中，這也不起作用。按照距離0排序的點[-2,1,3]給出[1，-2，3]。與3最近的鄰居不是-2。 –

我們的電腦屏幕像素協調是圖的「第四象限」。其中（0,0）是左上角。不存在負值的可能性。 – Liju

你想用quadtrees爲你的數據結構

這nice post爲您提供關於如何進行

來源

2017-02-24 12:52:42 Fezvez

距離計算優化

回答

相關問題