Минимальное расстояние от m точек до n фиксированных точек на прямой

1,00
р.
Формальная постановка задачи следующая: даны N точек на прямой и последовательность n1, n2, n3 ... неубывающая. Расположите M точек так, чтобы сумма расстояний от ближайших точек ni, n (i + 1) ... до точки mi была минимальной для i = 1 ... M.
Неформальная интерпретация задачи: расположите M заправок на дороге так, чтобы N проживающих вдоль дороги людей тратили как можно меньше времени на то, чтобы добраться до заправки. Для одной АЗС условие простое: количество людей справа и слева от АЗС должно быть одинаковым.
M <= N<br>При большем количестве АЗС задача усложняется. Я привел пример размещения 3 заправок среди 10 точек. Каждый из них создает определенный сегмент, и на этом сегменте справа и слева от АЗС находится одинаковое количество людей.
Однако это не оптимальное решение. Мое предположение: для оптимальности требуется дополнительное условие: справа и слева должно быть одинаковое количество точек, по которым данная АЗС является ближайшей. Пример такого расположения показан на рисунке ниже, и действительно, сумма расстояний для такой ситуации меньше.
Проблема в том, что я не понимаю, как на этапе обустройства заправок проверить, какая точка будет ближайшей. Это видно на первой картинке: мы расставляем точки так, чтобы с каждой стороны было одинаковое количество людей, но после расстановки оказывается, что ближайшая к ним АЗС не та, которую мы ожидали.

Ответ
Теория
Первый факт. Если одна бензоколонка и сколько угодно клиентов, то одно из оптимальных решений - разместить бензоколонку в позиции медианы массива клиентов.
Тут есть два утверждения: во-первых, позиция бензоколонки совпадает с позицией оного из клиентов и, во-вторых, дан точный рецепт как эту позицию выбрать.
Второй факт. Если бензоколонок несколько, то всё равно есть оптимальное решение когда все бензоколонки совпадают с координатами клиентов.
Простое решение
Второй факт позволяет решить задачу очень просто:
# xs - координаты клиентов, ys - координаты АЗС # возвращает сумму наименьших расстояний от клиентов до АЗС def dist(xs, ys): return sum(min(abs(x - y) for y in ys) for x in xs)
# xs - координаты клиентов, m - число АЗС # возвращает минимальное расстояние от клиентов до АЗС и расположение АЗС def baseline(xs, m): return min((dist(xs, ys), ys) for ys in itertools.combinations(xs, m))
Это решение имеет сложность n * m * Cnk(n, m), где n - число клиентов (len(xs)), Cnk - "це из эн по ка" - количество комбинаций размера k из множества размера n.
Первые два множителя - время вычисления dist, последний - время перебора комбинаций (АЗС ставятся различным клиентам).
Оптимизировать не буду, это решение нужно только для тестирования.
Рекурсивное решение задачи
Движемся в сторону динамического программирования. Чтобы решить задачу для m колонок надо разбить клиентов на две группы. Правой группе назначается одна колонка, левой группе m - 1 колонка. Из всех таких разбиений требуется выбрать минимум. Для простоты эта функция возвращает только сумму расстояний, расположение АЗС не сохраняется:
@functools.cache def recursive(xs, m): if m == 1: ys = xs[len(xs) // 2], return dist(xs, ys)
return min( recursive(xs[:j], m - 1) + recursive(xs[j:], 1) for j in range(m - 1, len(xs)) )
Сложность n * (n * n * m). Левое слагаемое - вычисление растояний для случая одной колонки, правое слагаемое - сложность рекурсии. Мы заполняем таблицу размером n * m. Каждая ячейка требует n операций для заполнения. От одного множителя n можно избавится. Об этом ниже.
Быстрое вычисление суммы расстояний до одной колонки
Даны координаты клиентов xs в неубывающем порядке. Из них выбирается подсписок xs[j1:j2]. Требуется найти наилучшее положение одной АЗС и сосчитать сумму расстояний до неё.
Из первого факта следует что АЗС надо поставить в медиану xs[(j1 + j2) // 2]. Вычислить сумму расстояний до неё можно за O(j2 - j1). Есть способ вычисления этой суммы за O(1).
Считаются кумулятивные суммы для xs. С их помощью расстояние вычисляется за константу. Код не самый приятный, извините.
def make_min_dist1(xs):
def accumulate(a): s = 0 yield s for v in a: s += v yield s
sums = tuple(accumulate(xs))
def min_dist1(j1, j2): assert j1 < j2 j = (j1 + j2) // 2 y = xs[j]
# hi_dist = (sums[j2] - sums[j]) - (j2 - j) * y # lo_dist = (j - j1) * y - (sums[j] - sums[j1]) # return lo_dist + hi_dist return -((j1 + j2) % 2) * y + sums[j2] + sums[j1] - 2 * sums[j]
return min_dist1
Динамическое программирование
Динмамическое программирование не отличается от предложенного Zergatul. Кеш устроен сложнее и компактнее, вычисление расстояний для одной колонки сделано за константу. Вычисляется и расстояние и расположение АЗС. Код очень сложный, ещё раз извините:
def dynamics(xs, m):
min_dist1 = make_min_dist1(xs)
n = len(xs)
if m == 1: return min_dist1(0, n), (xs[n // 2], )
# min_dist(i, j) best solution is in cache[i - 1][j - i + 1] cache = []
def min_dist(i, j): # cache[i - 2][j - i + 1] stores best solution for min_dist(i - 1, k) task return min( (cache[i - 2][k - i + 1][0] + min_dist1(k, j), k) for k in range(i - 1, j) ) # min_dist(1, j) best solution is in cache[0][j] cache.append(tuple((min_dist1(0, j), 0) for j in range(1, n - m + 2))) for i in range(2, m): # min_dist(i, j) best solution is in cache[i - 1][j - i + 1] cache.append(tuple(min_dist(i, j) for j in range(i, n - m + i + 1)))
d, k = min_dist(m, n)
def min_point(k): yield xs[(k + n) // 2] for i in reversed(range(1, m)): _, k1 = cache[i - 1][k - i] yield xs[(k1 + k) // 2] k = k1
return d, tuple(min_point(k))[::-1]
Сложность этого решения n * n * m.
Тест на параболе - 500 клиентов, 10 АЗС выполняется за 0.7 секунды:
print(*dynamics(tuple(i * i for i in range(500)), 10))
2803416 (2500, 17689, 36864, 59049, 84100, 110889, 139129, 168921, 199809, 232324)