如何在数轴上最优地放置两点以最小化到一组给定点的总距离

Question

给定数轴上的几个点，例如 x=1、2、5 和 6。我需要在数轴上放置两个附加点 x1 和 x2，使得 x=1,2,5 之间的总距离,6 且 x1 和 x2 被最小化。搜索这些点的有效方法是什么？

例如对于 x=1,2,5,6 且 x1 = 1，x2 = 6 是最佳的，因为 1-1=0,2-1=1,6-5=1,6-6=0。所以总距离是 2

Answer 1

如果我们只放置一个点，我们希望将其放置在 x 点的中间位置。中位数使平均绝对误差最小化。当然还有总错误。直观的解释是，在数轴上向左移动一步（-1），总误差会随着向左的点数而减少，并随着向右的点数而增加。最佳结果是两边的点数相同：中位数。

如果我们可以放置两个点，我们将希望将它们放置为其中一个是第一组点的中值，另一个是第二组点的中值。将点分成两组的选择只有 N 个，因此我们可以评估每个选项并选择最好的一个。

import numpy as np
x = np.array([1, 2, 3, 4, 5, 1000, 1001, 1002])
# Sum of the first k elements.
sums = np.insert(np.cumsum(x), 0, 0)
N = len(x)
# Split is the index of the last element in the first half.
split = np.arange(N-1)
# The median positions.
i1 = (split + 1)//2
i2 = split + (N - split)//2
# From start to before i1.
e1 = x[i1]*i1 - sums[i1]
# From after i2 to the split.
e2 = sums[split+1] - sums[i1] - x[i1]*(split - i1 + 1)
# From the split to before i2.
e3 = x[i2]*(i2 - split - 1) - sums[i2] + sums[split+1]
# From after i2 to the end.
e4 = sums[-1] - sums[i2 + 1] - x[i2]*(N - i2 - 1)
error = e1 + e2 + e3 + e4
best = np.argmin(error)
print(f"best x1: {x[i1[best]]}, x2: {x[i2[best]]}, error: {error[best]}")
# best x1: 3, x2: 1001, error: 8

上述代码的两个问题：

• 很难写出没有相差一错误的内容。我只能希望这是对的。
• 这里的推理是倒退的。我们计算误差时，就好像分割之前的所有内容都更接近 x1 而不是 x2。一般情况并非如此。但我认为 1）对于正确的解决方案来说这是正确的，2）它会导致高估错误解决方案的错误。所以最终还是成功了。