algorithm - ライン上の他のすべてのポイントまでの距離の合計が最も低いポイントを見つける

Question

この問題を再帰的または「分割統治」の方法で解決できるかどうか疑問に思っていました。これが私の問題の視覚化です：

ここに画像の説明を入力

Input:
22 // point no 1
35 // point no 2
5  // ...
44
45
20
46

Output: 2 // point with number 2 has got the lowest sum (87)

これを反復的に行う方法は知っていますが、もっと最適なことを考えています。

score 5 · Accepted Answer

これは中央値と呼ばれます。値を並べ替えて、中心を選択するだけです。nが偶数の場合、2つの中央の値のいずれでもかまいません。

中央値を計算するためのO（n）アルゴリズムもあります。

score 2 · Accepted Answer

解が中央値であるという答えは正しいですが、

複数のソリューション

点の数が偶数の場合: p ₁ < … p _n < p _{n + 1} < … < p _2n 、任意の点xの距離の合計は最小になります。ただし、*p _n ≤ x ≤ p _{n + 1です。}

中央値が機能する理由を理解するには、次のことを考慮してください。

該当するすべてのに対してp _i < p _i+1nとなる点があるとします。i

単純なので、合計Sを最小化するにはx = p ₁が最良の選択であると考えるかもしれません。xを 1増やすと、合計Sはどうなりますか? p ₁からは 1 離れていますが、他のすべての点からは 1 近くなっています。

したがって、S _{p ₁ + 1} = S _{p ₁} + 1 - (n - 1)

合計はx = p ₂までこのように変化し続けます: 勾配は1 - (n - 1) = 2 - n ポイントp ₂を通過した後、勾配は2 - (n - 2) = 4 - nに変化します、その後6 - n、次に8 - nなど

通過するポイントごとに傾きが常に 2 ずつ増加することは簡単にわかります。接近するポイントの量は 1 ずつ減少し、遠ざかるポイントの量は 1 ずつ増加し、傾きが 2 ずつ変化することになります。

ある時点で、勾配は負から

ポイントの数が偶数の場合、あるポイントで勾配がゼロになることは簡単にわかります。
p ₁ < p ₂ < … p _n < p _{n + 1} < … p _{2n - 1} < p _2n

点p _nとp _n+1の間に位置する場合、左側と右側の両方に同じ量の点があります。つまり、これらの 2 点間を移動すると、等量の点 (正確にはn ) が近づき、遠ざかるので、合計S _{p _n <= x <= p _{n + 1}}は変化しません。

ポイントの数が奇数の場合、p _{(n + 1)/2}は最小値を示します。これは、勾配が負から正に変化するポイントであるためです。