Задача о назначениях и другие переодетые потоки

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

Как думаешь, почему «каждому подешевле» - плохая идея

Пять курьеров, пять заказов, у каждой пары своя цена. Простое правило: идём по курьерам и каждому отдаём самый дешёвый из ещё свободных заказов. Насколько плохо это может быть?

На матрице из задачи этой главы такое правило даёт 18 при оптимуме 13 - почти в полтора раза дороже. Причина знакомая: дешёвый заказ, взятый первым курьером, может быть ЕДИНСТВЕННЫМ дешёвым вариантом для пятого, и его вынужденная замена перекрывает всю экономию. А если вместо жадности дополнять поток без учёта цены, можно получить 43: назначь каждому курьеру одноимённый заказ, получится 13 + 11 + 2 + 9 + 8 = 43. Величина верная, стоимость зависит от выбора путей. Локальная выгода против глобальной - ровно та же история, что и с жадным паросочетанием, только теперь с ценами.

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

Раздача ролей в спектакле. Если каждому актёру по очереди давать роль, которая ему больше всего идёт, последнему достанется та, в которой он смешон, - и спектакль в целом будет хуже, чем если бы пара актёров поменялась ролями. Выигрывает не сумма личных предпочтений, а согласованная расстановка.

Механизм: как выглядит сведение

ЗАДАЧА О НАЗНАЧЕНИЯХ (n исполнителей, n работ, цена a[i][j])

сеть:  s → исполнитель i      пропускная способность 1, цена 0
       исполнитель i → работа j   пропускная способность 1, цена a[i][j]
       работа j → t           пропускная способность 1, цена 0
       пропустить n единиц минимальной стоимости

существует целый оптимум: дробных вершин нет

ТРАНСПОРТНАЯ ЗАДАЧА (склады с запасами, магазины с потребностями)

s → склад i            пропускная способность = запас,      цена 0
склад i → магазин j    пропускная способность = сколько угодно, цена = тариф
магазин j → t          пропускная способность = потребность, цена 0

Разница только в числах на рёбрах: у назначений везде единицы, у транспортной - объёмы. Алгоритм один и тот же.

цена решения:
    общий поток минимальной стоимости   O(K · E · log V) с потенциалами
    венгерский алгоритм                 O(n³), специализирован под назначения
    жадность                            быстро и неверно

В оценке SSP целое K ограничивает число дополнений при целых границах потока и целочисленном старте: каждое дополнение увеличивает величину хотя бы на 1. Для дробных ёмкостей число итераций нельзя оценить одной величиной K.

Правило

Задача о назначениях - поток минимальной стоимости на двудольной сети с единичными пропускными способностями: исток → исполнители (1), исполнитель → работа (1, цена = стоимость пары), работы → сток (1), пропустить n единиц. Транспортная задача - то же самое, но пропускные способности равны запасам и потребностям. Обе решаются общим алгоритмом; для назначений есть специализированный венгерский алгоритм за O(n³). Жадность «каждому самое дешёвое из свободного» неоптимальна и может проигрывать в разы. Если задача имеет конечный оптимум, при целых нижних и верхних границах потока и балансах есть целый оптимальный поток благодаря полной унимодулярности матрицы; целые дополняющие шаги находят его без округления.

Разбор: пять курьеров, разрыв втрое

Матрица цен из задачи главы:

          з1   з2   з3   з4   з5
курьер 1  13    4    7    6    9
курьер 2   1   11    5    4    2
курьер 3   6    7    2    8    3
курьер 4   1    3    5    9    7
курьер 5  13    6    2    4    8

Жадность по курьерам: первый берёт з2 (4), второй - з1 (1), третий - з3 (2), четвёртый из оставшихся з4, з5 берёт з5 (7), пятому достаётся з4 (4). Итого 4 + 1 + 2 + 7 + 4 = 18. Обход по столбцам и обход по всем клеткам подряд дают 19 - то есть жадность на этой матрице держится в районе 18-19 при оптимуме 13.

Оптимум - 13, и достигается он так: курьер 1 → з2 (4), курьер 2 → з5 (2), курьер 3 → з3 (2), курьер 4 → з1 (1), курьер 5 → з4 (4). Сумма 4 + 2 + 2 + 1 + 4 = 13.

Посмотри, что здесь произошло. Курьер 2 мог взять з1 за 1 - самый дешёвый элемент своей строки, - но эту единицу «отдали» курьеру 4, у которого других дешёвых вариантов нет. Курьер 2 ушёл на з5 за 2, потеряв единицу, а выигрыш составил гораздо больше. Именно такие обмены и находит алгоритм: не поштучно, а цепочками через обратные рёбра.

Разбор: почему у транспортной задачи тот же алгоритм

Три склада с запасами 20, 30, 10 и три магазина с потребностями 25, 20, 15. Тарифы за единицу:

            м1   м2   м3
склад 1      4    6    9
склад 2      5    3    7
склад 3      8    2    4

s → склад1 = 20,  s → склад2 = 30,  s → склад3 = 10     (цена 0)
склад i → магазин j = ∞, цена = тариф
магазин1 → t = 25,  магазин2 → t = 20,  магазин3 → t = 15   (цена 0)
пропустить 60 единиц

Суммы сошлись: 20 + 30 + 10 = 60 = 25 + 20 + 15. Решение этой сети - стоимость 240:

склад 1 → м1: 20 единиц по 4 = 80
склад 2 → м1:  5 единиц по 5 = 25
склад 2 → м2: 20 единиц по 3 = 60
склад 2 → м3:  5 единиц по 7 = 35
склад 3 → м3: 10 единиц по 4 = 40
                       итого  240

Почему 240 - минимум, а не просто цена допустимого плана? Возьми числа для складов u=(0,1,−2) и для магазинов v=(4,2,6). Для каждой пары u[i]+v[j] не больше тарифа: например, 1+6=7 для второго склада и третьего магазина, а −2+2=0≤2 для третьего склада и второго магазина. Умножь каждое неравенство на неотрицательный объём перевозки x[i,j] и сложи. Полная отправка запасов и покрытие спроса дают нижнюю границу любой цены: 20·0+30·1+10·(−2)+25·4+20·2+15·6=240. Наш план достигает этой границы, значит он оптимален. Это двойственный сертификат из главы о линейном программировании, записанный числами.

Обрати внимание на склад 3: его тариф до м2 равен 2, но в плане он везёт товар в м3 по 4, а склад 2 обслуживает м2 по 3. Обменяем 10 единиц: склад 3 направим в м2, а освободившиеся 10 единиц склада 2 - в м3 по 7. Стоимость вырастет на 10·((2+7)−(4+3))=20. Локальная экономия на одном маршруте здесь вызывает большую потерю на другом.

Если бы запасы превышали потребности, лишнее просто не пошло бы через сеть - достаточно требовать поток величины, равной суммарной потребности. Если бы наоборот, задача была бы неразрешима, и алгоритм честно не набрал бы нужной величины.

Всё отличие от назначений - в числах на рёбрах, а не в алгоритме. Отсюда и практический приём: столкнувшись с новой задачей распределения, не спеши искать «алгоритм для неё» - попробуй нарисовать сеть. Если получилось расставить пропускные способности и цены так, что задача стала потоком, ты уже победил: дальше работает готовая библиотека.

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

Первое: решать назначения жадно - получишь правдоподобный и неоптимальный ответ. Второе: в транспортной задаче забыть про баланс запасов и потребностей: при несовпадении надо либо добавлять фиктивный склад (или магазин), либо явно требовать поток нужной величины. Третье: неверно считать цены на рёбрах из истока всегда несущественными. В полном назначении каждое ребро s→исполнитель насыщено, поэтому его цена добавляет одну и ту же константу к каждому решению. Но при избытке запасов транспортной задачи объёмы отдельных складов меняются: цены s→склад влияют на выбор даже при фиксированной общей величине потока. Четвёртое: применять реализацию венгерского алгоритма, рассчитанную только на квадратные матрицы, к прямоугольной без дополнения - недостающие строки или столбцы добивают фиктивными с нулевой ценой. При лишних исполнителях фиктивные работы оставляют часть исполнителей свободными; при лишних работах фиктивные исполнители оставляют часть работ без назначения. Готовый решатель SciPy принимает и прямоугольную матрицу. Пятое: округлять дробный ответ произвольного LP-решателя. Гарантируется существование целой оптимальной вершины, но между двумя такими вершинами могут лежать дробные оптимумы.

Например, в матрице 2×2 из единиц обе перестановки стоят 2. Их среднее назначает каждому работнику по половине каждой работы и тоже стоит 2. Это допустимый оптимум LP, но физическому назначению соответствует одна из двух целых перестановок. Независимое округление четырёх половин может нарушить ограничения строк и столбцов. Для транспортной задачи условие целости относится и к запасам с потребностями.

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

Это самый практичный сюжет раздела. Назначение заказов курьерам, распределение смен между сотрудниками с учётом предпочтений (предпочтение = цена), развоз товара со складов, привязка объектов на соседних кадрах видео, сопоставление записей двух баз с оценкой похожести - всё это задача о назначениях или транспортная. Она решается точно и быстро, и вместо эвристик стоит взять готовую реализацию: scipy.optimize.linear_sum_assignment решает назначения модификацией алгоритма Jonker-Volgenant и принимает прямоугольные матрицы (документация SciPy). Понимание сведения к потоку нужно, когда постановка чуть меняется: «один курьер может взять два заказа» - и пропускная способность его ребра становится двойкой, а всё остальное остаётся тем же.

Теперь сам

Три исполнителя, три работы, цены:

      р1   р2   р3
и1     5    9    3
и2     8    2    7
и3     4    6    5

Найди жадный ответ по строкам и оптимум. Сравни.

и1р1 и2р2 и3р3 = 5 + 2 + 5 = 12
и1р1 и2р3 и3р2 = 5 + 7 + 6 = 18
и1р2 и2р1 и3р3 = 9 + 8 + 5 = 22
и1р2 и2р3 и3р1 = 9 + 7 + 4 = 20
и1р3 и2р1 и3р2 = 3 + 8 + 6 = 17
и1р3 и2р2 и3р1 = 3 + 2 + 4 = 9      ← минимум