3

2D グリッドには n 個のポイントがあります。要件は、すべてのアイテムをそのポイントに移動するコストが最小になるように、それらすべてのポイント (n-1 ポイント) から単一のポイント (n ポイントのセット内) に 1 つのアイテムを移動することです。そのような点が複数ある場合は、任意の点をランダムに選択できます。引っ越し費用は以下のように計算されます。

コスト計算式

ポイントがある場合、オブジェクトを隣接する 8 つのポイントすべて(x,y)に移動するのに必要なコストは 1 ユニットです。(x,y){(x+1,y),(x+1,y+1),(x,y+1),(x-1,y+1),(x,y-1),(x-1,y-1),(x,y-1),(x+1,y-1)}

誰かがこれに O(N) アルゴリズムを提案できますか? O(N2) アルゴリズムを試しました (各ペアを取得してコストを計算するなど)。

4

3 に答える 3

2

すべてのポイントを「中心」に移動したいようです。中心は、総コスト値が最小のポイントとして定義されます。3 点の場合、答えは三角形の重心付近にあると思います。重心は、3 つの x 値すべてと 3 つの y 値すべてを単純に平均することによって得られるポイントです。

3点を超えて拡大すると、平均点が正解か正解に近いかのどちらかだと思います。ポイント間にユークリッド距離の式を使用していた場合、求めるポイントが単なる平均であることはほぼ確実です。しかし、45 度の角度を必要以上に「少なく」カウントする修正されたタクシー キャブ ジオメトリを使用しています。(0,0) から (5,5) までのコストは、標準ジオメトリを使用した 5 sqrt(5) (約 40% 以上) ではなく、定義により 5 です。ただし、水平方向または垂直方向の移動の場合、指標は同じです。では、正しい答えは私の簡単な推測からどのくらい離れているのでしょうか? 半径を推定できる場合は、次のアルゴリズムをお勧めします。

  • コンピューターの平均点 ( O(n) 時間で実行)
    C = 新しいポイント (平均 (xVals)、平均 (yVals))
  • コンピューターの半径 - ユークリッドの素早い答えから実際の答えがどれだけ離れているかの推定値。
  • その半径内のすべてのポイントを検討し、C よりも総コストが低くなるかどうかを確認します。

この最後の項目は O(r^2) で実行され、r が n よりもはるかに小さいことを示すことができる限り、適切な解決策があります。

于 2012-06-14T15:04:50.987 に答える
0

私の推測では、O(n) ソリューションは不可能です。入力データセットに円に近似するすべての点がある場合、アルゴリズムはすべての点をチェックして、それが最適な解であるかどうかを確認する必要があるようです。

現在、n に比例する時間で「通常の」ケースを処理するための優れたアルゴリズムがおそらくあります。
ベストファースト検索のポイントを順序付けするための AO(N log N) ヒューリスティックはありそうです。Aスターも可能かもしれませんが、もっと難しいようです.

于 2012-06-14T16:50:24.243 に答える
0

線形時間で n ポイントの重心を計算し、その重心に最も近い点も線形時間で計算できると思います。

質量中心を取得するには:

center = points[0];
for (int i=1; i<points.length; ++i) {
  center = massCenter(center, i+1, points[i]);
}

Point massCenter(Point currCent, int weight, Point p) {
  double x = (currCent.x * weight + p.x)/(weight+1);
  double y = (currCent.y * weight + p.y)/(weight+1);
  return new Point(x, y);
}

中心を正しく計算するために、点の座標を 2 つと仮定しました。

于 2012-06-14T14:59:36.857 に答える