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

В Венгерский метод это комбинаторная оптимизация алгоритм это решает проблема назначения в полиномиальное время и что ожидалось позже первичные – двойственные методы. Он был разработан и опубликован в 1955 г. Гарольд Кун, который дал название «венгерский метод», потому что алгоритм в значительной степени основан на более ранних работах двух венгерский язык математики: Денес Кёниг и Jen Egerváry.^[1][2]

Джеймс Мункрес рассмотрел алгоритм в 1957 г. и заметил, что он (сильно) полином.^[3] С тех пор алгоритм был известен также как Алгоритм Куна – Манкреса или Алгоритм присваивания Мункреса. В временная сложность оригинального алгоритма был ${\displaystyle O(n^{4})}$, Однако Эдмондс и Карп, и независимо Томидзава заметил, что его можно модифицировать для достижения ${\displaystyle O(n^{3})}$ Продолжительность.^{[4][5][как? ]} Один из самых популярных^{[нужна цитата ]} ${\displaystyle O(n^{3})}$ вариантов - алгоритм Джонкера – Волгенанта.^[6] Форд и Фулкерсон распространил метод на общие задачи о максимальном потоке в виде Алгоритм Форда – Фулкерсона. В 2006 году было обнаружено, что Карл Густав Якоби решила проблему присваивания в 19 веке, и решение было опубликовано посмертно в 1890 году на латыни.^[7]

Проблема

Основная статья: Проблема с присвоением

Пример

В этом простом примере трое рабочих: Пол, Дэйв и Крис. Один из них должен убирать ванную, другой подметать полы, а третий моет окна, но каждый из них требует разной оплаты за выполнение различных задач. Проблема в том, чтобы найти самый дешевый способ распределения рабочих мест. Проблема может быть представлена ​​в виде матрица затрат рабочих, выполняющих работу. Например:

	Чистая ванная	Подметать полы	Вымойте окна
Павел	$2	$3	$3
Дэйв	$3	$2	$3
Крис	$3	$3	$2

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

Формулировка матрицы

В матричной формулировке задана неотрицательная п×п матрица, где элемент в я-й ряд и j-й столбец представляет стоимость присвоения j-я работа я-й рабочий. Мы должны найти назначение рабочих мест работникам, так что каждое задание назначается одному работнику, а каждому работнику назначается одно задание, так что общая стоимость назначения будет минимальной.

Это можно выразить как перестановку строк и столбцов матрицы затрат. C чтобы минимизировать след матрицы:

${\displaystyle \min _{L,R}{\rm {Tr}}(LCR)}$

где L и р находятся матрицы перестановок.

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

Формулировка двудольного графа

Алгоритм проще описать, если сформулировать задачу с помощью двудольного графа. У нас есть полный двудольный граф ${\displaystyle G=(S,T;E)}$ с участием ${\displaystyle n}$ рабочие вершины (${\displaystyle S}$) и ${\displaystyle n}$ вершины работы (${\displaystyle T}$), и каждое ребро имеет неотрицательную стоимость ${\displaystyle c(i,j)}$. Мы хотим найти идеальное соответствие с минимальной общей стоимостью.

Алгоритм в терминах двудольных графов

Назовем функцию ${\displaystyle y:(S\cup T)\to \mathbb {R} }$ а потенциал если ${\displaystyle y(i)+y(j)\leq c(i,j)}$ для каждого ${\displaystyle i\in S,j\in T}$. В ценить потенциала ${\displaystyle y}$ - сумма потенциала по всем вершинам: ${\displaystyle \sum _{v\in S\cup T}y(v)}$.

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

Венгерский метод находит идеальное соответствие и такой потенциал, при котором стоимость сопоставления равна потенциальной стоимости. Это доказывает, что оба они оптимальны. Фактически, венгерский метод находит идеальное соответствие узкие края: край ${\displaystyle ij}$ называется плотным из-за потенциального ${\displaystyle y}$ если ${\displaystyle y(i)+y(j)=c(i,j)}$. Обозначим подграф узких краев ${\displaystyle G_{y}}$. Стоимость идеального соответствия в ${\displaystyle G_{y}}$ (если он есть) равен значению ${\displaystyle y}$.

В процессе работы алгоритма мы поддерживаем потенциал ${\displaystyle y}$ и ориентация из ${\displaystyle G_{y}}$ (обозначается ${\displaystyle {\overrightarrow {G_{y}}}}$), которая обладает тем свойством, что ребра, ориентированные из ${\displaystyle T}$ к ${\displaystyle S}$ сформировать соответствие ${\displaystyle M}$. Первоначально, ${\displaystyle y}$ везде 0, а все ребра ориентированы из ${\displaystyle S}$ к ${\displaystyle T}$ (так ${\displaystyle M}$ пусто). На каждом шаге мы либо изменяем ${\displaystyle y}$ так, чтобы его значение увеличилось, или измените ориентацию, чтобы получить совпадение с большим количеством краев. Мы сохраняем инвариант, что все ребра ${\displaystyle M}$ тугие. Мы закончили, если ${\displaystyle M}$ идеальное соответствие.

На общем этапе пусть ${\displaystyle R_{S}\subseteq S}$ и ${\displaystyle R_{T}\subseteq T}$ быть вершинами, не покрытыми ${\displaystyle M}$ (так ${\displaystyle R_{S}}$ состоит из вершин в ${\displaystyle S}$ без входящего края и ${\displaystyle R_{T}}$ состоит из вершин в ${\displaystyle T}$ без выходящего края). Позволять ${\displaystyle Z}$ - множество вершин, достижимых в ${\displaystyle {\overrightarrow {G_{y}}}}$ из ${\displaystyle R_{S}}$ направленным путем, только следуя плотным кромкам. Это можно вычислить с помощью поиск в ширину.

Если ${\displaystyle R_{T}\cap Z}$ непусто, то поменяем ориентацию ориентированного пути в ${\displaystyle {\overrightarrow {G_{y}}}}$ из ${\displaystyle R_{S}}$ к ${\displaystyle R_{T}}$. Таким образом, размер соответствующего соответствия увеличивается на 1.

Если ${\displaystyle R_{T}\cap Z}$ пусто, тогда пусть

${\displaystyle \Delta :=\min\{c(i,j)-y(i)-y(j):i\in Z\cap S,j\in T\setminus Z\}.}$

${\displaystyle \Delta }$ положительный, потому что между ${\displaystyle Z\cap S}$ и ${\displaystyle T\setminus Z}$. Увеличивать ${\displaystyle y}$ от ${\displaystyle \Delta }$ на вершинах ${\displaystyle Z\cap S}$ и уменьшить ${\displaystyle y}$ от ${\displaystyle \Delta }$ на вершинах ${\displaystyle Z\cap T}$. Результирующий ${\displaystyle y}$ все еще есть потенциал, и хотя график ${\displaystyle G_{y}}$ изменения, он все еще содержит ${\displaystyle M}$ (см. следующие подразделы). Ориентируем новые края от ${\displaystyle S}$ к ${\displaystyle T}$. По определению ${\displaystyle \Delta }$ набор ${\displaystyle Z}$ вершин достижимых из ${\displaystyle R_{S}}$ увеличивается (обратите внимание, что количество узких кромок не обязательно увеличивается).

Повторяем эти шаги до тех пор, пока ${\displaystyle M}$ - идеальное соответствие, и в этом случае оно дает минимальную стоимость. Время работы этой версии метода составляет ${\displaystyle O(n^{4})}$: ${\displaystyle M}$ дополняется ${\displaystyle n}$ раз, и в фазе, где ${\displaystyle M}$ без изменений, есть не более ${\displaystyle n}$ возможные изменения (поскольку ${\displaystyle Z}$ увеличивается каждый раз). Время, достаточное для возможного изменения, равно ${\displaystyle O(n^{2})}$.

Доказательство того, что корректировка потенциала у уходит M без изменений

Чтобы показать, что каждый край в ${\displaystyle M}$ остается после корректировки ${\displaystyle y}$, достаточно показать, что для произвольного ребра из ${\displaystyle M}$, либо обе его конечные точки, либо ни одна из них не находится в ${\displaystyle Z}$. С этой целью пусть ${\displaystyle vu}$ быть преимуществом в ${\displaystyle M}$ из ${\displaystyle T}$ к ${\displaystyle S}$. Легко видеть, что если ${\displaystyle v}$ в ${\displaystyle Z}$ тогда ${\displaystyle u}$ должно быть тоже, так как каждый край в ${\displaystyle M}$ туго. Теперь предположим, в сторону противоречия, что ${\displaystyle u\in Z}$ но ${\displaystyle v\notin Z}$. ${\displaystyle u}$ сам не может быть в ${\displaystyle R_{S}}$ потому что это конечная точка совпадающего ребра, поэтому должен быть некоторый направленный путь узких ребер из вершины в ${\displaystyle R_{S}}$ к ${\displaystyle u}$. Этот путь должен избегать ${\displaystyle v}$, так как это по предположению не в ${\displaystyle Z}$, поэтому вершина, непосредственно предшествующая ${\displaystyle u}$ на этом пути есть другая вершина ${\displaystyle v'\in T}$. ${\displaystyle v'u}$ это острый край от ${\displaystyle T}$ к ${\displaystyle S}$ и поэтому находится в ${\displaystyle M}$. Но потом ${\displaystyle M}$ содержит два ребра, которые имеют общую вершину ${\displaystyle u}$, что противоречит тому, что ${\displaystyle M}$ соответствует. Таким образом, каждое ребро в ${\displaystyle M}$ имеет либо обе конечные точки, либо ни одну конечную точку в ${\displaystyle Z}$.

Доказательство того, что ${\displaystyle y}$ остается потенциальным

Чтобы показать это ${\displaystyle y}$ остается потенциальным после корректировки, достаточно показать, что ни у одного края общий потенциал не превысил его стоимость. Это уже установлено для ребер в ${\displaystyle M}$ по предыдущему абзацу, поэтому рассмотрим произвольное ребро ${\displaystyle uv}$ из ${\displaystyle S}$ к ${\displaystyle T}$. Если ${\displaystyle y(u)}$ увеличивается на ${\displaystyle \Delta }$, то либо ${\displaystyle v\in Z\cap T}$, в таком случае ${\displaystyle y(v)}$ уменьшается на ${\displaystyle \Delta }$, оставляя общий потенциал края неизменным, или ${\displaystyle v\in T\setminus Z}$, в этом случае определение ${\displaystyle \Delta }$ гарантирует, что ${\displaystyle y(u)+y(v)+\Delta \leq c(u,v)}$. Таким образом ${\displaystyle y}$ остается потенциал.

Матричная интерпретация

Данный ${\displaystyle n}$ рабочих и задач, а также ${\displaystyle n}$×${\displaystyle n}$ матрица, содержащая стоимость назначения каждого работника задаче, найдите задание, минимизирующее затраты.

Сначала задача записывается в виде матрицы, как показано ниже.

а1	а2	а3	а4
b1	Би 2	b3	b4
c1	c2	c3	c4
d1	d2	d3	d4

где a, b, c и d - работники, которые должны выполнять задачи 1, 2, 3 и 4. a1, a2, a3, a4 обозначают штрафы, понесенные, когда работник «a» выполняет задачи 1, 2, 3, 4 соответственно. . То же самое верно и для других символов. Матрица квадратная, поэтому каждый работник может выполнить только одну задачу.

Шаг 1

Затем мы выполняем строковые операции над матрицей. Для этого самый низкий из всех а_я (i принадлежит 1-4) берется и вычитается из каждого элемента в этой строке. Это приведет как минимум к одному нулю в этой строке (мы получаем несколько нулей, когда есть два равных элемента, которые также оказываются самыми низкими в этой строке). Эта процедура повторяется для всех строк. Теперь у нас есть матрица по крайней мере с одним нулем в строке. Теперь мы пытаемся назначить задачи агентам так, чтобы каждый агент выполнял только одну задачу, а штраф, понесенный в каждом случае, был равен нулю. Это проиллюстрировано ниже.

0	a2 '	a3 '	а4 '
b1 '	Би 2'	b3 '	0
c1 '	0	c3 '	c4 '
d1 '	d2 '	0	d4 '

Нули, обозначенные как 0, являются назначенными задачами.

Шаг 2

Иногда может оказаться, что матрица на этом этапе не может быть использована для назначения, как в случае с матрицей ниже.

0	a2 '	a3 '	а4 '
b1 '	Би 2'	b3 '	0
0	c2 '	c3 '	c4 '
d1 '	0	d3 '	d4 '

В приведенном выше случае назначение невозможно. Обратите внимание, что задача 1 эффективно выполняется как агентами a, так и c. Обоим нельзя назначить одну и ту же задачу. Также обратите внимание, что никто не выполняет задачу 3 эффективно. Чтобы преодолеть это, мы повторяем описанную выше процедуру для всех столбцов (т.е. минимальный элемент в каждом столбце вычитается из всех элементов в этом столбце), а затем проверяем, возможно ли присвоение.

В большинстве случаев это даст результат, но если это все еще невозможно, нам нужно продолжать.

Шаг 3

Все нули в матрице должны быть покрыты маркировкой как можно меньшего количества строк и / или столбцов. Следующая процедура - один из способов добиться этого:

Во-первых, назначьте как можно больше задач.

• В строке 1 один ноль, поэтому он назначен. 0 в строке 3 зачеркнут, потому что он находится в том же столбце.
• В строке 2 один ноль, поэтому он присваивается.
• Единственный ноль в строке 3 вычеркнут, поэтому ничего не присваивается.
• В строке 4 два неперечеркнутых нуля. Любой из них может быть назначен, а другой ноль зачеркнут.

В качестве альтернативы можно присвоить 0 в строке 3, в результате чего вместо этого будет перечеркнут 0 в строке 1.

0'	a2 '	a3 '	а4 '
b1 '	Би 2'	b3 '	0'
0	c2 '	c3 '	c4 '
d1 '	0'	0	d4 '

Теперь к рисованию.

• Отметьте все строки, не имеющие назначений (строка 3).
• Отметьте все столбцы с нулями во вновь отмеченных строках (столбец 1).
• Отметьте все строки, имеющие назначения, во вновь отмеченных столбцах (строка 1).
• Повторяйте шаги, описанные в предыдущих двух пунктах, пока не перестанут отмечаться новые строки или столбцы.

×
0'	a2 '	a3 '	а4 '	×
b1 '	Би 2'	b3 '	0'
0	c2 '	c3 '	c4 '	×
d1 '	0'	0	d4 '

Теперь проведите линии через все отмеченные столбцы и немаркированный ряды.

×
0'	a2 '	a3 '	а4 '	×
b1 '	Би 2'	b3 '	0'
0	c2 '	c3 '	c4 '	×
d1 '	0'	0	d4 '

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

Шаг 4

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

Повторяйте шаги 3–4, пока не станет возможным назначение; это когда минимальное количество строк, используемых для покрытия всех 0, равно max (количество людей, количество назначений), предполагая, что фиктивные переменные (обычно максимальная стоимость) используются для заполнения, когда количество людей больше, чем количество заданий.

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

Библиография

• R.E. Буркард, М. Делль'Амико, С. Мартелло: Проблемы с назначением (Доработанная перепечатка). СИАМ, Филадельфия (Пенсильвания), 2012 г. ISBN  978-1-61197-222-1
• М. Фишетти, "Lezioni di Ricerca Operativa", Edizioni Libreria Progetto Padova, Италия, 1995.
• Р. Ахуджа, Т. Маньянти, Дж. Орлин, "Сетевые потоки", Прентис Холл, 1993.
• С. Мартелло, «Йено Эгервари: от истоков венгерского алгоритма до спутниковой связи». Central European Journal of Operational Research 18, 47–58, 2010 г.

Рекомендации

1. Гарольд В. Кун, "Венгерский метод решения задачи о назначении", Ежеквартально по логистике военно-морских исследований, 2: 83–97, 1955. Оригинальная публикация Куна.
2. Гарольд В. Кун, "Варианты венгерского метода решения задач о назначениях", Ежеквартально по логистике военно-морских исследований, 3: 253–258, 1956.
3. Дж. Мункрес, "Алгоритмы решения задач назначения и транспортировки", Журнал Общества промышленной и прикладной математики, 5(1): 32–38, март 1957 г.
4. ЭдмондсДжек; М., Карп Ричард (1 апреля 1972 г.). «Теоретические улучшения алгоритмической эффективности для задач сетевого потока». Журнал ACM. 19 (2): 248–264. Дои:10.1145/321694.321699.
5. Томизава, Н. (1971). «О некоторых приемах, полезных для решения проблем транспортной сети». Сети. 1 (2): 173–194. Дои:10.1002 / нетто.3230010206. ISSN  1097-0037.
6. Jonker, R .; Волгенант А. (декабрь 1987 г.). «Кратчайший алгоритм увеличения пути для плотных и разреженных задач линейного назначения». Вычисление. 38 (4): 325–340. Дои:10.1007 / BF02278710.
7. http://www.lix.polytechnique.fr/~ollivier/JACOBI/presentationlEngl.htm

внешняя ссылка

• Брюфф, Дерек, Проблема присвоения и венгерский метод (матричный формализм).
• Мордехай Дж. Голин, Двудольное сопоставление и венгерский метод (формализм биграфа), Курсовые заметки, Гонконгский университет науки и технологий.
• Венгерский алгоритм максимального соответствия (оба формализма) на сайте Brilliant.
• Р. А. Пилигрим, Алгоритм присваивания Мункреса. Изменено для прямоугольных матриц, Примечания к курсу, Государственный университет Мюррея.
• Майк Доус, Задача оптимального назначения, Примечания к курсу, Университет Западного Онтарио.
• По венгерскому методу Куна - дань уважения Венгрии, Андраш Франк, Egervary Research Group, Pazmany P. setany 1 / C, H1117, Будапешт, Венгрия.
• Лекция: Основы исследования операций - Задача о назначении - Венгерский алгоритм, Профессор Г. Сринивасан, Департамент исследований менеджмента, IIT Madras.
• Расширение: Анализ чувствительности присвоения (с временной сложностью O (n ^ 4)), Лю, Shell.
• Решайте любые проблемы с заданиями онлайн, дает пошаговое объяснение венгерского алгоритма.

Реализации

Обратите внимание, что не все из них удовлетворяют ${\displaystyle O(n^{3})}$ временная сложность, даже если они так утверждают. Некоторые могут содержать ошибки, реализовывать медленнее ${\displaystyle O(n^{4})}$ алгоритм или другие недостатки. В худшем случае пример кода, связанный с Википедией, впоследствии может быть изменен, чтобы включить код эксплойта. При использовании таких примеров кода от неизвестных авторов необходима проверка и тестирование.

• Реализация C требует ${\displaystyle O(n^{3})}$ временная сложность
• Заявление о реализации Java ${\displaystyle O(n^{3})}$ временная сложность
• Утверждение реализации Matlab ${\displaystyle O(n^{3})}$ временная сложность (всеобщее достояние)
• Реализация Python
• Реализация Ruby с модульными тестами
• Заявление о реализации C # ${\displaystyle O(n^{3})}$ временная сложность
• D с модульными тестами (порт версии Java, требующей ${\displaystyle O(n^{3})}$)
• Интерактивная реализация онлайн
• Последовательные и параллельные реализации.
• Matlab и C
• Реализация Perl
• Реализация на C ++
• Реализация C ++ требует ${\displaystyle O(n^{3})}$ временная сложность (Лицензия с открытым исходным кодом в стиле BSD)
• Реализация MATLAB
• C реализация
• Реализация JavaScript с модульными тестами (порт версии Java, требующей ${\displaystyle O(n^{3})}$ временная сложность)
• Пакет Clue R предлагает реализацию, resolve_LSAP
• Реализация Node.js на GitHub
• Реализация Python в пакете scipy