7 
Input: list of 2d points (x,y) where x and y are integers.

Distance: distance is defined as the Manhattan distance. 
    ie:
    def dist(p1,p2) 
         return abs(p1.x-p2.x) + abs(p1.y - p2.y)

什么是找到最接近所有其他点的点的有效算法。

我只能想到一个蛮力 O(n^2) 解决方案：

minDist=inf
bestPoint = null
for p1 in points:
    dist = 0
    for p2 in points:
        dist+=distance(p1,p2)
    minDist = min(dist,minDist)
    bestPoint = argmin(p1, bestPoint)

基本上看每一对点。

4

3 回答 3

12

请注意，在一维中，最小化到所有点的距离之和的点是中位数。

在二维中，问题可以解决O(n log n)如下：

创建一个排序的 x 坐标数组，并为数组中的每个元素计算选择该坐标的“水平”成本。元素的水平成本是到投影到 X 轴上的所有点的距离之和。这可以通过扫描阵列两次（一次从左到右，一次在相反方向）以线性时间计算。类似地，创建一个 y 坐标的排序数组，并为数组中的每个元素计算选择该坐标的“垂直”成本。

现在对于原始数组中的每个点，我们可以O(1)通过添加水平和垂直成本来计算所有其他时间点的总成本。所以我们可以计算 中的最佳点O(n)。因此总运行时间为O(n log n)。

于 2012-10-16T00:28:26.327 回答
3

您正在寻找的是质量中心。

您基本上将所有 xs' 和 ys' 加在一起并划分为整个系统的质量。现在，你有质量均匀的粒子，让它们的质量为 1。

那么你所要做的就是将粒子的位置相加并除以粒子的数量。

假设我们有 p1(1,2) p2(1,1) p3 (1,0)

// we sum the x's 

    bestXcord = (1+1+1)/3 = 1

//we sum the y's 

    bestYcord = (2+1)/3 = 1

所以 p2 是最接近的。

在 O(n) 中解决

于 2012-10-16T00:14:12.870 回答
1

从您的初始算法开始，可以进行优化：

minDist=inf
bestPoint = null
for p1 in points:
    dist = 0
    for p2 in points:
        dist+=distance(p1,p2)
        //This will weed out bad points rather fast
        if dist>=minDist then continue(p1)
    /*
    //Unnecessary because of new line above
    minDist = min(dist,minDist)
    bestPoint = argmin(p1, bestPoint)
    */
    bestPoint = p1

这个想法是，尽可能快地丢弃异常值。这可以进一步改进：

  • 使用启发式“内部”点启动 p1 循环（这会创建一个好的minDist第一个点，因此更差的点会被更快地丢弃）
  • 使用启发式“外部”点启动 p2 循环（这使得dist上升速度更快，可能更快地触发退出条件

如果你用大小换取速度，你可以走另一条路：

//assumes points are numbered 0..n
dist[]=int[n+1]; //initialized to 0
for (i=0;i<n;i++)
  for (j=i+1;j<=n;j++) {
    dist=dist(p[i], p[j]);
    dist[i]+=dist;
    dist[j]+=dist;
  }
minDist=min(dist);
bestPoint=p[argmin(dist)];

它需要更多空间用于 dist 数组，但每个距离只计算一次。这具有更适合“获得 N 个最佳点”类型的问题和计算密集型度量的优势。我怀疑它不会为 x86 或 x64 架构上的 manhattan 度量带来任何好处：内存访问将在很大程度上主导计算。

于 2012-10-16T00:23:48.857 回答