Венгерский алгоритм

Сорок курьеров ждут на случайных перекрёстках Алматы, а в сорока кафе и ресторанах готовы заказы — места кафе взяты из OpenStreetMap. Нужно решить, кто за каким заказом поедет, чтобы вместе курьеры проехали по улицам как можно меньше. Первое, что приходит в голову, — отдавать каждый заказ ближайшему свободному курьеру. Второе — снова и снова брать самую короткую из оставшихся пар. Первое даёт 140,6 км, второе — 138,6, а лучшее распределение — 121,5 км. Перебором его не найти: распределений 40! — число из 48 цифр. Венгерский алгоритм находит лучшее меньше чем за миллисекунду.

Переключайте способы. У «короткой пары первой» красная линия — самая длинная поездка — 12,9 км через полгорода: короткие пары разобраны, и последним курьерам достаются заказы, которые остались, а остаются как раз неудобные. При десяти курьерах так получается поездка в 15,8 км. Ближайший свободный ошибается иначе: первые заказы забирают курьеров, которые были бы нужнее следующим, и при восьмидесяти курьерах он проезжает 256,2 км против 191,7 у лучшего распределения — на треть больше.

Идея

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

Дадим каждому курьеру и каждому заказу по числу — потенциалу — так, чтобы у любой пары потенциалы в сумме не превышали её цены. Пары, где сумма потенциалов равна цене, назовём честными. Если удастся распределить всех только по честным парам, распределение лучшее, и потенциалы это доказывают. Алгоритм добавляет курьеров по одному, а когда честных пар не хватает, сдвигает потенциалы: так, чтобы появилась новая честная пара и ни одна из прежних не испортилась.

Почему меньше нельзя

Пусть c_ij — цена пары «курьер i, заказ j», u_i — потенциал курьера, v_j — потенциал заказа, и для всех пар u_i + v_j ≤ c_ij. Разность c_ij − u_i − v_j ≥ 0 называют приведённой ценой; у честных пар она равна нулю.

Обратное тоже верно: для лучшего распределения такие потенциалы всегда найдутся. Это частный случай теоремы двойственности линейного программирования, а для этой задачи его доказал в 1931 году Енё Эгервари. Венгерский алгоритм доказывает это ещё раз — построением: он выдаёт и распределение, и потенциалы. Листинг ниже это проверяет: у сорока курьеров сумма потенциалов — те же 121,5 км, из 1600 пар честных 113, и все 40 пар ответа среди них. Кто сомневается в ответе, может проверить его за n² сравнений, не повторяя поиск.

Как двигаются потенциалы

Начнём с нулевых потенциалов: при неотрицательных ценах все неравенства выполнены. Курьеров добавляем по одному. Новый курьер i ищет себе заказ по честным парам. Если честная пара ведёт к свободному заказу — готово. Если к занятому, можно попробовать передвинуть его курьера: тот ищет другой заказ по своим честным парам, и так далее. Курьеры и заказы, до которых дошёл такой поиск из i, образуют дерево. Если в дереве нашёлся свободный заказ, все курьеры вдоль пути до него сдвигаются на следующий заказ — путь переворачивается, — и распределённых становится на одного больше. Это тот же увеличивающий путь, что в алгоритме для паросочетаний, только идёт он по честным парам.

Если дерево упёрлось и свободных заказов в нём нет, найдём δ — наименьшую приведённую цену от курьеров дерева до заказов вне его. Прибавим δ к потенциалам всех курьеров дерева и вычтем δ из потенциалов всех заказов дерева.

После сдвига дерево растёт на новую честную пару. Если её заказ свободен — путь найден; если занят, в дерево входит его курьер, и поиск продолжается. Каждый сдвиг добавляет в дерево заказ, поэтому за одного курьера сдвигов не больше n. Если для каждого заказа вне дерева хранить наименьшую приведённую цену до него из дерева, сдвиг стоит O(n): найти наименьшее и обновить массив. Курьеров n, итого O(n³).

Если присмотреться, это алгоритм Дейкстры в приведённых ценах: массив наименьших цен — расстояния, дерево — уже найденные вершины, δ — расстояние до следующей. Потенциалы делают все приведённые цены неотрицательными, и потому Дейкстра здесь работает, — тот же приём, что у алгоритма Джонсона для графов с отрицательными рёбрами.

Шесть курьеров и шесть заказов с той же карты, 25 шагов. Курьеры 1, 3 и 5 сразу находят свободный заказ: им хватает одного сдвига. Курьер 2 хочет заказ B, уже отданный первому, и первый пересаживается на E. Последний, шестой, курьер проходит через три занятых заказа — D, A и E, — потенциалы сдвигаются четыре раза, и при перевороте пути пересаживаются ещё двое. Сумма потенциалов всё время остаётся нижней границей ответа и к концу доходит до 37,0 км — цены лучшего распределения. «Ближайший свободный» и «короткая пара первой» на этих же шести дают по 40,1 км.

Код

Листинг считает расстояния по улицам сорока запусками Дейкстры, затем распределяет тремя способами и проверяет ответ потенциалами. Функция hungarian — классическая короткая запись метода: столбец 0 фиктивный, в него ставится добавляемый курьер, minv — наименьшие приведённые цены до заказов вне дерева, way — откуда пришли, чтобы перевернуть путь.

Самое дорогое здесь — не распределение, а таблица цен: сорок запусков Дейкстры по 7909 перекрёсткам. Сам венгерский алгоритм для 40 × 40 — десятки тысяч простых действий. В сцене выше та же картина: Дейкстра занимает десятки миллисекунд, распределение — меньше одной.

Сколько это стоит

Для сотен и тысяч курьеров O(n³) хватает с запасом. Когда n — десятки тысяч, а у каждого курьера разумных заказов всего несколько, полную таблицу не строят: остаются только близкие пары, и те же кратчайшие увеличивающие пути ищут по разреженному графу. На кратчайших увеличивающих путях построен и вариант Роя Джонкера и Тона Волгенанта (1987); функция linear_sum_assignment в SciPy — его версия без начальной расстановки.

Варианты

Курьеров больше, чем заказов. Строками делают заказы, столбцами курьеров: алгоритм работает с прямоугольной таблицей, где строк не больше, чем столбцов, и лишние курьеры просто остаются без пары.

Наибольшая сумма. Если нужна не наименьшая цена, а наибольшая выгода, достаточно сменить знак у всех чисел — или вычесть все числа из одного большого, чтобы цены оставались неотрицательными.

Запрещённые пары. Пару, которая невозможна, — курьер не успеет, заказ не по его маршруту — заменяют очень большой ценой, больше любого допустимого распределения. Если в ответ всё же попала такая пара, допустимого распределения нет.

Никто не едет далеко. Наименьшая сумма может отправить одного курьера через весь город. Если важнее самая длинная поездка, её находят двоичным поиском по порогу: есть ли распределение, где все пары не длиннее порога, — это вопрос о паросочетании. А уже среди таких распределений ищут наименьшую сумму венгерским алгоритмом с запрещёнными парами. Это вторая задача ниже.

Аукцион. Димитрий Берцекас в 1979 году предложил считать потенциалы ценами: свободный курьер выбирает самый выгодный для себя заказ и повышает на него ставку настолько, насколько этот заказ выгоднее второго по выгоде. Такой аукцион хорошо делится между процессорами и быстро работает на разреженных задачах.

Поток наименьшей стоимости. Если у курьера несколько мест в сумке, а у кафе несколько заказов, задача становится потоком наименьшей стоимости; венгерский алгоритм — его частный случай, где все пропускные способности равны единице.

Заказы приходят по одному. Ближайший свободный курьер — решение «здесь и сейчас», и сцена показывает, сколько оно стоит. Если подождать и собрать заказы за несколько секунд, на собранных можно решить задачу о назначениях: распределение станет лучше, а ожидание — дольше. Где найти равновесие, зависит от того, что дороже: минута клиента или километр курьера.

История

Летом 1953 года Харольд Кун занимался задачей о назначениях и читал книгу Дёнеша Кёнига по теории графов 1936 года. В ней он нашёл теорему о паросочетаниях — по сути, двойственность для таблиц из нулей и единиц — и сноску на статью Енё Эгервари 1931 года, которая обобщала её на любые числа. Статья была написана по-венгерски с кратким пересказом по-немецки. Кун, как он вспоминал, взял грамматику и большой словарь, за две недели выучил язык настолько, чтобы её перевести, и нашёл в ней мысль, которая сводит общую задачу к последовательности задач из нулей и единиц. Метод он опубликовал в 1955 году и назвал венгерским — в честь Кёнига и Эгервари.

Осенью 1953 года Кун решал вручную задачи 12 × 12 с трёхзначными числами меньше чем за два часа каждую. Его утверждение, что тогда ни одна машина в мире не была запрограммирована на линейные программы такого размера, позже оспорили: задачу 10 × 10 уже решали симплекс-методом на машине SEAC. Но в 1956 году Форд и Фалкерсон сообщали, что на задаче 20 × 20 симплекс-метод работал больше часа, а венгерский — около получаса вручную. Многие считали венгерский метод разновидностью симплекс-метода; Кун выиграл об этом пари у Алана Хоффмана, когда тот признал, что это не так.

В 1957 году Джеймс Манкрес показал, что метод работает за полиномиальное время, — отсюда второе название, алгоритм Куна — Манкреса. Оценку O(n³) с потенциалами и кратчайшими путями получили в начале 1970-х Джек Эдмондс с Ричардом Карпом и независимо Томидзава. А в 2006 году Куну написал Франсуа Оливье: в бумагах Карла Якоби, умершего в 1851 году, нашёлся алгоритм для той же задачи — по словам Куна, по существу тот же венгерский метод, на сто лет раньше.

Задачи

Первая — сама задача о назначениях; в тестах есть таблицы расстояний по улицам Алматы. Во второй сначала нужно сделать как можно короче самую длинную поездку, а потом уже — сумму.