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

1-Dでは、すべてのポイントまでの距離の合計を最小化するポイントが中央値であることに注意してください。

2次元では、問題はO(n log n)次のように解決できます。

x座標の並べ替えられた配列を作成し、配列内の各要素について、その座標を選択するための「水平」コストを計算します。要素の水平コストは、X軸に投影されたすべてのポイントまでの距離の合計です。これは、アレイを2回（左から右に1回、逆方向に1回）スキャンすることにより、線形時間で計算できます。同様に、並べ替えられた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配列のためにより多くのスペースを必要としますが、各距離を1回だけ計算します。これには、「N個のベストポイントを取得する」種類の問題や、計算量の多いメトリックに適しているという利点があります。ただし、x86またはx64アーキテクチャでは、マンハッタンメトリックには何ももたらされないと思います。メモリアクセスが計算を大きく左右します。

于 2012-10-16T00:23:48.857 に答える