x座標とy座標を持つN点（2D）が与えられている。他の（N-1）点からPまでの距離の合計が最小になるように点P（N点の点）を見つける必要があります。他の点に最も近い点を見つける
ex。 p1（x1、y1）、p2（x2、y2）...... pN（xN、yN）を与えられたN個の点。 我々は、他のすべての点からの距離の和が最小であるp1、p2 .... PNの中の点Pを見つける。
私はブルートフォースアプローチを使用しましたが、私はより良いアプローチが必要です。私はまた、中央値、平均などを見つけることによって試しましたが、すべての場合に働いていません。
私は、Xをポリゴンの頂点として扱い、このポリゴンの重心を見つけて、セントロイドに最も近いY点を選択するという考えを思いつきました。しかし、重心がポリゴンの頂点までの距離の和を最小にするかどうかはわからないので、これが良い方法かどうかはわかりません。この問題を解決するアルゴリズムはありますか？
あなたのポイントがきれいに配られている場合、その数が多すぎると（各ポイントから他のポイントまでの合計距離を計算する）魅力的でない場合、次のようにすれば十分な回答が得られる場合があります。 「うまく分散されている」とは、（ほぼ）一様に（またはほぼ）ランダムに、複数の場所に著しいクラスタリングがないことを意味します。
均一なk*kグリッドを作成します（kは奇数整数です）。あなたのポイントがきれいに分散されている場合、探しているポイントは（おそらく）このグリッドの中央のセルにあります。グリッド内の他のすべてのセルについては、各セルのポイント数をカウントし、各セルのポイントの平均位置を近似します（セル中心を使用するか、セル内のポイントの平均値を計算します）。
中央セルの各ポイントについて、中央セルの他のすべてのポイントまでの距離と、他のセルのポイントまでの加重平均距離を計算します。これは、もちろん、点から他のセルの点の「平均」位置までの距離であり、他のセルの点の数によって重み付けされる。
計算量が増えることから、より高い値の高い値のkを選択して、あなたのポイントに最適なものを見つけ出す必要があります。細胞間の点の分布が一様でない場合、このアプローチは適切ではない可能性があります。
この種のアプローチは、ポイントが重力や電荷などの距離を超えて動作するプロパティを持つ大規模なシミュレーションで非常に広く使用されています。それがあなたのニーズに合っているかどうかはわかりません。
私はあなたの質問を理解しているかどうかはわかりませんが、最小スパンニングツリーを計算するときに、任意のポイントからツリーの他のポイントまでの合計が最小です。
あなたは最小化する必要があります単一点から他のすべての点までの要約距離。最小スパニングツリーは、任意のポイントから他のポイントに到達できるエッジを構築するために必要な距離の最小合計を計算します。これは、OPが求めているものではありません。 –
考慮した点は、各試料までの距離の二乗の和を最小化するように幾何学的中央値と同様に定義された幾何学的中央
重心または質量の中心として知られている、により求めることができます単純な公式 - その座標はサンプルの座標の平均ですが、そのような公式は幾何学的中央値では知られておらず、算術演算とk番目の根だけを含む正確な公式も一般的に存在しないことが示されています。
私たちは皆、GoogleとWikipediaの使い方を知っています。質問者は説明を探しています。 – Jordan
私はちょうどこれがよく理解された問題であり、それが現在の状態であることを質問者に伝えたいと思っていました。 私はそれを簡潔にするために答えを編集しました –
ブルートフォースアプローチの最適化は、距離の代わりに二乗された距離を計算することです。これは、平方根の計算が非常に高価な操作であるためです。 –
@KshitijMehtaは、距離の平方和を最適化することは、距離の合計を最適化することと同じではありません。 –
ちょっとコーダー、私はこの問題に対処するアルゴリズムを思いついたと思います。それはかなり複雑で、答えとしてまともな説明を投稿できるようになるのはおそらく数日前です。あなたがまだ興味を持っているかどうか教えてください... – Cephron