ほぼ同じ問題について話している投稿を読みました。しかし、ここでは、具体的な証明が提供されることを期待して、問題を単純化します。
A
のようないくつかの離散点 (1 次元) を含むセットがあります{1, 3, 37, 59}
。A
そして、この点と他の点の間の距離の合計を最小にすることができる1 つの点を選びたいと思います。
そこにはたくさんの投稿があるかもしれません。私の問題は1-d
それらのバージョンにすぎA
ませんA
.
Plzは具体的な証拠を添えて答えてくれます、ありがとう。
厳密に(または大まかに)数学的な証明ではありません。それが必要な場合は、間違った場所で質問している可能性があります:)
1D座標x
と呼び、レイズx
が右に移動しているとしましょう。あなたが探しているポイントはですmx
。
mx
左よりも右に多くのポイントがある場合、右に移動mx
すると、左側のポイントが少なくなり、右側のポイントが多くなり、平均距離が短くなります。
言い換えればmx
、右よりも左にポイントを少なくすることはできません。ある場合は、平均を下げる方法があります。
逆もまた真です。
要素の数が奇数の場合、上記の要件を満たす唯一のポイントは中央値です。
要素の数が偶数の場合、2つの中間要素の間の任意の点が条件を満たすことになります。
ポイント間では総距離関数は線形であり、距離関数はどこでも連続であるため、セット内のポイントの 1 つで最小値を取得する必要があります。したがって、 A が特定のセットに含まれるように制限できます。
例として、ポイント {-3, 1, 2, 5} からの合計距離関数のグラフを次に示します。
A の左側に L ポイント、右側に R ポイントがあるとします。
1 つのポイントを右に移動すると、距離が d * (L + 1 - R) だけ変化します (d は次のポイントまでの距離です)。同様に、ポイントを 1 つ左に移動すると、距離が d * (R + 1 - L) だけ変化します。
|LR|を最小化するポイント この距離が最小になる場所です。それは中央値 (セット内にある場合)、またはそうでない場合は中央値に隣接する 2 つのポイントのいずれかです。
ポイントの質問間の最小距離を見つけるための最速の方法を考慮して、最も近いポイントの問題のペアを調べてみてください。