algorithm - 选择一个点，使其与集合中其他点之间的距离总和最小

Question

我读了一篇关于几乎相同问题的帖子。但在这里我简化了问题，希望能提供一个具体的证明。

有一个A包含一些离散点（一维）的集合，例如{1, 3, 37, 59}。我想选择一个点A，可以最小化该点与其他点之间的距离之和。

那里可能有很多帖子，我的问题只是那些版本，如果不是离散的，1-d我知道如何证明它，但是当像上面那样离散时我失败了。AA

请用具体的证据给我答案，谢谢。

Answer 1

不是严格（甚至松散）的数学证明，如果这是您需要的，那么您很可能在错误的地方问:)

让我们调用一维坐标x，假设加注x向右移动。您正在寻找的重点是mx.

• 如果mx右边的点多于左边的点，则向右移动mx会将距离提高到左侧较少的点，并将其降低到右侧的更多点，这将降低平均距离。

• 换句话说，mx左边不能比右边少，如果有，有办法降低平均值。

反之亦然。

如果元素的数量是奇数，则满足上述要求的唯一点就是中位数。

如果元素个数是偶数，则两个中间元素之间的任何点都满足条件。

Answer 2

由于点之间的总距离函数是线性的，并且距离函数在任何地方都是连续的，因此必须在集合中的一个点处达到最小值。因此，您可以将 A 限制在给定的集合中。

以下是从点 {-3, 1, 2, 5} 开始的总距离函数的图表，例如：

假设 L 指向左侧，R 指向 A 右侧。

向右移动一个点会使距离改变 d * (L + 1 - R)（其中 d 是到下一个点的距离）。同样，向左移动一点会使距离改变 d * (R + 1 - L)。

最小化 |LR| 的点 是这个距离最小的地方。那是中位数（如果它在集合中），或者是中位数的两个相邻点中的任何一个（如果不是）。

Answer 3

考虑最快的方法来找到点之间的最小距离问题尝试看看最接近的点对问题。