距离计算优化
我正在写一个算法来计算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)的对称性?我还有其他意见吗?
此外,你可以向我描述另一种算法,这将是更好的方法来执行此计算?我研究过二叉树,但是我不确定它们是如何应用于我的问题的!
你可以通过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
}
}
计算出所有的点(0,0)之间的距离。 然后按升序排序距离。
现在,特殊点的后继者和前辈是最近的邻居。
即使在1D中,这也不起作用。按照距离0排序的点[-2,1,3]给出[1,-2,3]。与3最近的邻居不是-2。 –
我们的电脑屏幕像素协调是图的“第四象限”。其中(0,0)是左上角。不存在负值的可能性。 – Liju
你想返回一个解决方案或所有方案的算法的细节?(有一般的多最近的邻居) – niceman