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

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

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

Проблема [ править ]

Пример [ править ]

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

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

Формулировка матрицы [ править ]

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

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

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

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

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

Формулировка двудольного графа [ править ]

Алгоритм легче описать, если сформулировать задачу с помощью двудольного графа. У нас есть полный двудольный граф с рабочими вершинами ( ) и рабочими вершинами ( ), и каждое ребро имеет неотрицательную стоимость . Мы хотим найти идеальное соответствие с минимальной общей стоимостью.${\ Displaystyle G = (S, T; E)}$${\ displaystyle n}$${\ displaystyle S}$${\ displaystyle n}$${\ displaystyle T}$${\ Displaystyle с (я, 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)}$

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

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

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

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

Если пусто, то пусть${\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 ij}$${\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})}$

Доказательство прогресса алгоритма [ править ]

Мы должны показать, что до тех пор, пока соответствие не имеет максимально возможного размера, алгоритм всегда может добиться прогресса, то есть либо увеличить количество совпадающих ребер, либо сузить хотя бы одно ребро. Достаточно показать, что на каждом шаге выполняется хотя бы одно из следующего:

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

Если максимально возможный размер, мы, конечно, закончили. В противном случае по лемме Берге должен существовать увеличивающий путь по отношению к в нижележащем графе . Однако этот путь может не существовать в : Хотя каждое ребро с четным номером является узким по определению , ребра с нечетным номером могут быть свободными и, следовательно, отсутствовать в . Одна конечная точка находится внутри , другая - внутри ; wlog, предположим, что он начинается в . Если все ребра натянуты, то это остается дополнительным путем, и все готово. В противном случае позвольте быть первым свободным краем . Если${\displaystyle M}$${\displaystyle P}$${\displaystyle M}$${\displaystyle G}$${\displaystyle G_{y}}$${\displaystyle P}$${\displaystyle M}$${\displaystyle G_{y}}$${\displaystyle P}$${\displaystyle R_{S}}$${\displaystyle R_{T}}$${\displaystyle R_{S}}$${\displaystyle P}$${\displaystyle G_{y}}$${\displaystyle uv}$${\displaystyle P}$${\displaystyle v\notin Z}$тогда мы нашли путь с расплывчатым хвостом, и все готово. В противном случае достижимо по некоторому другому пути узких ребер из вершины в . Пусть будет подпуть от начала в и продолжения до конца, и пусть будет путь, образованный движением вдоль, пока не будет достигнута вершина , а затем продолжением до конца . Заметьте, что это увеличивающий путь с по крайней мере одним свободным краем меньше, чем . может быть заменен на, и этот процесс рассуждений повторяется (формально с использованием индукции по количеству свободных ребер) до тех пор, пока не будет найден либо увеличивающий путь, либо путь со свободным хвостом .${\displaystyle v}$${\displaystyle Q}$${\displaystyle R_{S}}$${\displaystyle P_{v}}$${\displaystyle P}$${\displaystyle v}$${\displaystyle P'}$${\displaystyle Q}$${\displaystyle P_{v}}$${\displaystyle P_{v}}$${\displaystyle P'}$${\displaystyle G}$${\displaystyle P}$${\displaystyle P}$${\displaystyle P'}$${\displaystyle G_{y}}$${\displaystyle G}$

Доказательство того, что регулировка потенциала y оставляет M неизменным [ править ]

Чтобы показать, что каждое ребро in остается после настройки , достаточно показать, что для произвольного ребра in либо обе его конечные точки, либо ни одна из них не находятся внутри . Для этого позвольте быть ребром от до . Легко видеть, что если внутри, то должно быть тоже, так как каждый край внутри тугой. Теперь предположим в сторону противоречия, что « но» . сам по себе не может быть в потому что она является конечной точкой согласованной кромки, так что должен быть некоторый путь направлен узких ребер из вершины в с . Этого пути следует избегать , поскольку он по предположению не находится в , поэтому вершина, непосредственно предшествующая${\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}$

Интерпретация матрицы [ править ]

Эта статья может сбивать с толку или непонятна читателям . В частности, это выполняет алгоритм на примере, но фактический алгоритм для матриц никогда ранее не обсуждался и не предоставляет подробностей о реальном алгоритме, а также полагается на расплывчатые подходы, такие как "рисование" минимального покрытия. Пожалуйста, помогите уточнить статью . На странице обсуждения может быть обсуждение этого вопроса . ( Ноябрь 2019 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

Учитывая работников и задачи, а также матрицу ×, содержащую стоимость назначения каждого работника задаче, найдите назначение, минимизирующее затраты.${\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

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

Поскольку есть рабочие и задачи, добавление или вычитание фиксированного числа для каждого элемента в строке или столбце изменит стоимость задания только на эту сумму; но присвоение минимальной стоимости при старых весах останется назначением минимальной стоимости при новых весах. ${\displaystyle n}$${\displaystyle n}$

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

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, пока не станет возможным назначение; это когда минимальное количество строк, используемых для покрытия всех нулей, равно max (количество людей, количество назначений), предполагая, что фиктивные переменные (обычно максимальная стоимость) используются для заполнения, когда количество людей больше, чем количество заданий.

Согласно теореме Кёнига ^[8] минимальное количество строк (минимальное покрытие вершин ^[9] ) будет (размер максимального сопоставления ^[10] ). Таким образом, когда требуются строки, назначение минимальной стоимости можно найти, глядя только на нули в матрице.${\displaystyle n}$${\displaystyle n}$

Библиография [ править ]

• RE Burkard, M. Dell'Amico, S. Martello: Assignment Problems (переработанная перепечатка). SIAM, Филадельфия (Пенсильвания), 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 г.

Ссылки [ править ]

Внешние ссылки [ править ]

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

Реализации [ править ]

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

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