Как оптимально разместить две точки на числовой прямой, чтобы минимизировать общее расстояние до набора заданных точек

Если бы нам нужно было разместить только одну точку, мы бы хотели разместить ее в срединном положении точек 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) это приводит к завышению ошибки для неправильных решений. Так что в конце концов это сработает.