x 座標と y 座標を持つ (2D の) N ポイントが与えられます。他の (N-1) 点から P までの距離の合計が最小になるように、(N 個の与えられた点で) 点 P を見つける必要があります。
例のために。与えられた N 点 p1(x1,y1),p2(x2,y2) ...... pN(xN,yN)。p1 、p2 .... PN の中から、他のすべての点からの距離の合計が最小になる点 P を見つけました。
ブルート フォース アプローチを使用しましたが、より良いアプローチが必要です。私も中央値、平均値などを見つけようとしましたが、すべてのケースでうまくいくわけではありません。
次に、Xを多角形の頂点として扱い、この多角形の重心を見つけ、重心に最も近い点をYから選択するというアイデアを思いつきました。しかし、重心がポリゴンの頂点までの距離の合計を最小化するかどうかはわかりません。これが良い方法かどうかはわかりません。この問題を解決するアルゴリズムはありますか?
ポイントが適切に分散されていて、その数が多すぎてブルート フォース (各ポイントから他のすべてのポイントまでの合計距離を計算すること) が魅力的でない場合は、次の方法で十分な答えが得られる可能性があります。「適切に分散」とは、(ほぼ) 一様に、または (ほぼ) ランダムに、複数の場所で顕著なクラスタリングがないことを意味します。
空間全体に均一なk*kグリッド (kは奇数) を作成します。ポイントが適切に分散されている場合、探しているポイントは (おそらく) このグリッドの中央のセルにあります。グリッド内の他のすべてのセルについて、各セル内のポイント数をカウントし、各セル内のポイントの平均位置を概算します (セルの中心を使用するか、セル内(x,y)のポイントの平均を計算します)。
中央のセル内の各ポイントについて、中央のセル内の他のすべてのポイントまでの距離と、他のセル内のポイントまでの加重平均距離を計算します。もちろん、これは、ポイントから他のセルのポイントの「平均」位置までの距離であり、他のセルのポイント数で重み付けされます。
計算負荷の増加に対して、より高い値の精度の向上を調整しk、ポイントに最適なものを見つけ出す必要があります。セル全体のポイントの分布が均一ではない場合、このアプローチは適切ではない可能性があります。
この種のアプローチは、点が重力や電荷など、距離を超えて作用するプロパティを持つ大規模なシミュレーションで非常に広く使用されています。それがあなたのニーズに合っているかどうかはわかりません。
考慮するポイントは、幾何中央値として知られています
各サンプルまでの距離の二乗和を最小化するものとして幾何中央値と同様に定義される重心または重心は、単純な式で見つけることができます。その座標はサンプルの座標の平均ですが、そのような式はありません。は幾何学的中央値で知られており、明示的な公式や、算術演算と k 乗根のみを含む正確なアルゴリズムは一般に存在しないことが示されています。
あなたの質問を理解しているかどうかはわかりませんが、最小スパニングツリーを計算すると、ツリーの任意のポイントから他のポイントまでの合計が最小になります。