Разбор: где поставить склад на трассе

Если ты знаешь, почему сумма расстояний минимальна в медиане, а наибольшее - в середине, листай до «Теперь сам».

Как думаешь, где ставить

Шесть магазинов вдоль трассы, на километрах 3, 8, 10, 11, 40 и 55. Где поставить склад, чтобы машины ездили меньше? Ответь себе до чтения.

Первое, что хочется сказать, - «где-то посередине» или «поближе к кучке магазинов в начале трассы». А теперь добавим: магазин на 55-м километре - гипермаркет, у него 30 заказов в день, у остальных вместе 22. Ответ меняется полностью - и это сигнал, что в просьбе «чтобы ездили меньше» спрятано несколько разных задач.

На что это похоже

Перетягивание каната. Сдвинь склад на километр вправо - все магазины справа станут ближе, все слева - дальше. Если справа «тянут» сильнее (больше заказов), сдвигаться выгодно. Склад останавливается там, где силы уравнялись, - а это точка, по каждую сторону от которой не больше половины заказов.

Механизм: от просьбы к модели

Вход - километры магазинов и число заказов в день; склад ставится на целом километре, у отметки трассы. Вид ответа - лучший: одна точка. Что значит «лучше» - три честных толкования:

• сумма пробега: каждый заказ - отдельная поездка, минимизируем Σ |x − pᵢ| · wᵢ;
• сумма без весов: каждый магазин - одна поездка в день, независимо от заказов;
• самый дальний: важна гарантия «доставка не дольше часа», минимизируем max |x − pᵢ|. Час переводится в километры, потому что машины идут по одной трассе с одной скоростью: время доставки пропорционально расстоянию. Например, при 60 км/ч час - это 60 км, и склад, до дальнего магазина от которого 26 км, гарантию выполняет. Если скорость на участках разная, мерить надо минутами, и это уже другая модель.

Размер - сотни магазинов, но точку можно искать не перебором, а рассуждением.

Почему медиана. Пусть склад в x; L - суммарный вес магазинов левее x и в самой точке x, R - строго правее. Сдвиг на километр вправо (пока по дороге нет магазинов) уменьшает пробег правых на R и увеличивает пробег остальных на L, то есть меняет сумму на L − R. Пока L < R, сдвигаться вправо выгодно; как только L ≥ R, уже нет. Значит, минимум - в магазине, на котором накопленный слева вес вместе с ним самим впервые достигает половины. Это взвешенная медиана. На примере ниже: левее 55-го километра 22 заказа из 52, а вместе с гипермаркетом - 52, половина набирается ровно на нём. Для наибольшего расстояния работает другое рассуждение: дальний магазин всегда один из крайних, и уравнять расстояние до обоих можно только в середине между ними.

Правило

Когда «лучше» означает сумму расстояний, ответ - (взвешенная) медиана; когда наибольшее расстояние - середина между крайними. Прежде чем считать, выясни, какое из толкований нужно: на одних и тех же данных они дают разные точки.

Разбор: три критерия - три склада

Перебор по всем целым километрам - исполняемая спецификация, медиана и середина - быстрые ответы; сверяем. Перебирать трассу целиком не нужно: склад за крайним магазином хуже, чем на самом крайнем, - сдвиг внутрь приближает его ко всем сразу. Поэтому перебор идёт от левого крайнего магазина до правого, какими бы ни были их километры.

# магазины вдоль трассы: [километр, заказов в день]
magaziny = [[3, 10], [8, 4], [10, 1], [11, 2], [40, 5], [55, 30]]

def summa(x):
    # километров в день: каждый заказ едет со склада x к магазину
    # (только в одну сторону; туда-обратно - всё вдвое, ответ тот же)
    s = 0
    for m in magaziny:
        s = s + abs(m[0] - x) * m[1]
    return s

def hudshee(x):
    # самый дальний магазин
    h = 0
    for m in magaziny:
        h = max(h, abs(m[0] - x))
    return h

def perebor(cel):
    # от крайнего левого магазина до крайнего правого
    levyj = min(magaziny)[0]
    pravyj = max(magaziny)[0]
    luchshij = levyj
    for x in range(levyj, pravyj + 1):
        if cel(x) < cel(luchshij):
            luchshij = x
    return luchshij

def vzveshennaya_mediana():
    # точка, где набралась половина всех заказов при обходе слева
    vsego = 0
    for m in magaziny:
        vsego = vsego + m[1]
    nakopleno = 0
    for m in sorted(magaziny):
        nakopleno = nakopleno + m[1]
        if 2 * nakopleno >= vsego:
            return m[0]

def bez_vesov():
    # медиана положений, если заказы не учитывать
    km = []
    for m in magaziny:
        km.append(m[0])
    km.sort()
    return km[(len(km) - 1) // 2]

x = perebor(summa)
print("сумма с заказами: перебор", x, "медиана", vzveshennaya_mediana(),
      "| км в день", summa(x))
x = bez_vesov()
print("медиана без заказов:", x, "| км в день с заказами", summa(x))
x = perebor(hudshee)
# склад - на целом километре: если середина крайних между отметками,
# обе соседние отметки одинаково хороши, и // берёт левую
print("самый дальний: перебор", x, "середина крайних", (3 + 55) // 2)
print("    до дальнего", hudshee(x), "| км в день", summa(x))

сумма с заказами: перебор 55 медиана 55 | км в день 916
медиана без заказов: 10 | км в день с заказами 1580
самый дальний: перебор 29 середина крайних 29
    до дальнего 26 | км в день 1234

Гипермаркет на 55-м километре один держит больше половины заказов, поэтому взвешенная медиана - прямо у него, и пробег 916 км в день. Медиана без весов ставит склад на 10-й километр, в кучку мелких магазинов, - и машины проезжают 1580 км: на 72% больше. Критерий «самый дальний» даёт 29-й километр, гарантию «не дальше 26 км» - и 1234 км пробега. Ни один ответ не ошибка: каждый - оптимум своей задачи. Ошибка - выбрать критерий молча.

Разбор: два склада - разрез отсортированного списка

Бюджет позволяет два склада. Перебор пар километров от 3-го до 55-го - 53 · 52 / 2 = 1378 вариантов, а при трассе в 1000 км - полмиллиона. Модель сокращает работу: каждый магазин ездит на ближайший склад, поэтому магазины, отсортированные по километру, делятся на левую часть (к левому складу) и правую. Почему непрерывными частями: если склады стоят в a < b, магазин левее середины между ними ближе к a, правее - к b. Середина одна, значит, все магазины левого склада лежат левее всех магазинов правого. Остаётся перебрать место разреза, а в каждой части склад - её взвешенная медиана по первому разбору.

magaziny = [[3, 10], [8, 4], [10, 1], [11, 2], [40, 5], [55, 30]]

def stoimost(sklady):
    # каждый магазин обслуживает ближайший склад
    s = 0
    for m in magaziny:
        blizhe = 10 ** 9
        for x in sklady:
            blizhe = min(blizhe, abs(m[0] - x))
        s = s + blizhe * m[1]
    return s

# перебор: все пары километров от крайнего магазина до крайнего
proverok = 0
luchshee = [10 ** 9, 0, 0]
for a in range(3, 56):
    for b in range(a + 1, 56):
        proverok = proverok + 1
        c = stoimost([a, b])
        if c < luchshee[0]:
            luchshee = [c, a, b]
print("перебор пар:   ", luchshee, "вариантов", proverok)

def mediana(gruppa):
    vsego = 0
    for m in gruppa:
        vsego = vsego + m[1]
    nakopleno = 0
    for m in gruppa:
        nakopleno = nakopleno + m[1]
        if 2 * nakopleno >= vsego:
            return m[0]

# модель: ближайший склад делит отсортированные магазины на левую и
# правую часть; в каждой части склад - её взвешенная медиана
po_poryadku = sorted(magaziny)
luchshee = [10 ** 9, 0, 0]
for i in range(1, len(po_poryadku)):
    a = mediana(po_poryadku[:i])
    b = mediana(po_poryadku[i:])
    c = stoimost([a, b])
    if c < luchshee[0]:
        luchshee = [c, a, b]
print("разрез списка: ", luchshee, "вариантов", len(po_poryadku) - 1)

перебор пар:    [118, 3, 55] вариантов 1378
разрез списка:  [118, 3, 55] вариантов 5

Почему перебор разрезов не может промахнуться, хотя stoimost потом переназначает магазины ближайшему складу. Возьмём лучшую пару складов; её магазины делятся каким-то разрезом. На этом разрезе медиана каждой части обслуживает свою часть не хуже, чем склад из лучшей пары, - медиана оптимальна для части по первому разбору. А переназначение ближайшему складу стоимость только уменьшает. Значит, на этом разрезе программа получит не больше оптимума, а меньше оптимума не бывает.

Ответ совпал: склады на 3-м и 55-м километрах, 118 км пробега в день. Вариантов - 5 разрезов вместо 1378 пар. Граница правила: так просто только на прямой. Для k складов разрез превращается в динамику по отрезкам отсортированного списка (раздел 15), а на плоскости или в дорожной сети задача о k складах с минимальной суммой - k-медиана - NP-трудна, и там уже нужны приближения и локальный поиск (раздел 22).

Что ломается без этого

Критерий выбрали молча. Отчёт обещает «оптимальное размещение», логисты меряют пробег, а алгоритм минимизировал самое дальнее расстояние. Разница здесь - 35%.

Веса забыли. Медиана без учёта заказов ставит склад в кучку мелких магазинов, далеко от того, кто даёт больше половины поездок.

Перебор там, где хватает модели. Перебор пар километров на трассе в 1000 км - полмиллиона вариантов, разрез отсортированного списка - сотни.

Зачем это в работе

Тот же выбор критерия стоит за любой «оптимизацией расположения»: где держать реплику базы (средняя задержка или худшая?), какую версию считать «типичной» в отчёте (среднее или медиана?), куда ставить точку выдачи. Медиана устойчива к далёким точкам: один магазин на краю карты или один сбойный замер сдвигают её на одну позицию, а середину крайних - на половину расстояния. К весу она не равнодушна, и так и надо: куда больше поездок, туда и тянет. А «самый дальний» нужен там, где есть гарантия перед каждым, а не в среднем.

Теперь сам

1. Магазины на километрах 2, 5, 9, 20, по одному заказу в день у каждого. Где склад по сумме пробега? Где по самому дальнему?
2. К тем же магазинам добавили пятый, на 100-м километре, тоже с одним заказом. Как сдвинутся оба ответа?
3. Почему при чётном числе магазинов без весов годится любая точка между двумя средними?