Минимальное расстояние от 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)