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

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

Джеймс Манкрес рассмотрел алгоритм в 1957 году и заметил, что он (сильно) полиномиален . ^[4] С тех пор алгоритм также известен как алгоритм Куна–Мункреса или алгоритм назначения Манкреса . Временная сложность исходного алгоритма была , однако Эдмондс и Карп , и независимо Томизава заметили, что его можно модифицировать для достижения времени выполнения. ^[5]^[6]Форд и Фулкерсон распространили метод на общие задачи максимального потока в форме алгоритма Форда–Фулкерсона . $O(n^{4})$ $O(n^{3})$

Проблема

Пример

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

Венгерский метод, примененный к таблице выше, даст минимальную стоимость: это $15, что достигается за счет того, что Алиса убирает ванную, Кэрол подметает полы, а Боб моет окна. Это можно подтвердить с помощью грубой силы:

(не назначенный человек моет окна)

Матричная формулировка

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

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

\min _{P}\operatorname {Tr} (PC)\;,

где P — матрица перестановки . (Эквивалентно, столбцы можно переставлять с помощью CP .)

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

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

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

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

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

Значение потенциала $y равно$ сумме потенциалов по всем вершинам:

\sum _{v\in S\cup T}y(v)

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

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

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

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

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

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

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

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

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

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

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

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

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

Доказательство того, что корректировка потенциалаулистьяМнеизмененный

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

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

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

Алгоритм вО(н3) время

Предположим, что есть задания и работники ( ). Мы описываем, как вычислить для каждого префикса заданий минимальную общую стоимость назначения каждого из этих заданий отдельным работникам. В частности, мы добавляем th задание и обновляем общую стоимость за время , получая общую временную сложность . Обратите внимание, что это лучше, чем когда количество заданий мало относительно количества работников. $J$ $W$ $J\leq W$ $j$ $O(jW)$ $O\left(\sum _{j=1}^{J}jW\right)=O(J^{2}W)$ $O(W^{3})$

Добавление j-й работы вО(jW) время

Мы используем те же обозначения, что и в предыдущем разделе, хотя при необходимости изменяем их определения. Пусть обозначает множество первых рабочих мест, а обозначает множество всех рабочих. $S_{j}$ $j$ $Т$

Перед шагом th алгоритма мы предполагаем, что у нас есть сопоставление на , которое соответствует всем работам в и потенциалы, удовлетворяющие следующему условию: сопоставление является тесным относительно потенциалов, и потенциалы всех несопоставленных работников равны нулю, а потенциалы всех сопоставленных работников неположительны. Обратите внимание, что такие потенциалы подтверждают оптимальность сопоставления. $j$ $S_{j-1}\чашка T$ $S_{j-1}$ $у$

На шаге th мы добавляем th-ю работу в , чтобы сформировать и инициализировать . В любое время каждая вершина в будет достижима из th-й работы в . Пока не содержит работника, которому не назначена работа, пусть $j$ $j$ $S_{j-1}$ $S_{j}$ $Z=\{j\}$ $Z$ $j$ $G_{y}$ $Z$

\Delta :=\min\{c(j,w)-y(j)-y(w):j\in Z\cap S_{j},w\in T\setminus Z\}

и обозначают любой , при котором достигается минимум. После настройки потенциалов способом, описанным в предыдущем разделе, теперь есть узкий край от до . $w_{\text{следующий}}$ $w$ $Z$ $w_{\text{следующий}}$

Если не сопоставлено, то у нас есть увеличивающийся путь в подграфе узких ребер от до . После переключения сопоставления по этому пути мы теперь сопоставили первые задания, и эта процедура завершается. $w_{\text{следующий}}$ $j$ $w_{\text{следующий}}$ $j$
В противном случае мы добавляем и сопоставленную с ним работу к . $w_{\text{следующий}}$ $Z$

Настройка потенциалов требует времени. Пересчет и после изменения потенциалов и также может быть выполнен за время. Случай 1 может произойти в большинстве случаев до того, как произойдет случай 2 и процедура завершится, что дает общую временную сложность . $O(W)$ $\Дельта$ $w_{\text{следующий}}$ $Z$ $O(W)$ $j-1$ $O(jW)$

Реализация на C++

Для удобства реализации код ниже добавляет дополнительного работника , который сохраняет отрицание суммы всех вычисленных до сих пор. После добавления th-го задания и обновления сопоставления стоимость текущего сопоставления становится равной сумме всех вычисленных до сих пор, или . $w_{W}$ $y(w_{W})$ $\Дельта$ $j$ $\Дельта$ $-y(w_{W})$

Этот код адаптирован из e-maxx :: algo. ^[7]

/*** Решение https://open.kattis.com/problems/cordonbleu с использованием венгерского языка* алгоритм.*/#include <кассета> #include <iostream> #include <лимиты> #включить <вектор> с использованием пространства имен std ;  /*** Устанавливает a = min(a, b)* @return true, если b < a*/шаблон < класс T > bool ckmin ( T & a , const T & b ) { return b < a ? a = b , 1 : 0 ; }                     /*** При наличии J рабочих мест и W работников (J <= W) вычисляется минимальная стоимость назначения каждого* префикс рабочих мест для отдельных работников.** @tparam T — тип, достаточно большой для представления целых чисел порядка J ** макс(|С|)* @param C — матрица размерностей JxW, такая что C[j][w] = стоимость назначения j-го* работа для работника (возможно отрицательно)** @return вектор длины J, где j-й элемент равен минимальной стоимости* назначить первые (j+1) рабочих мест отдельным работникам*/шаблон < класс T > вектор < T > венгерский ( const вектор < вектор < T >> & C ) {        const int J = ( int ) размер ( C ), W = ( int ) размер ( C [ 0 ]);        утверждение ( J <= W );   // job[w] = задание, назначенное w-му работнику, или -1, если задание не назначено // примечание: W-й работник был добавлен для удобства вектор < int > задание ( W + 1 , -1 );     вектор < T > ys ( J ), yt ( W + 1 ); // потенциалы      // -yt[W] будет равен сумме всех дельт вектор < T > ответы ;  const T inf = numeric_limits < T >:: max ();     for ( int j_cur = 0 ; j_cur < J ; ++ j_cur ) { // назначаем j_cur-ое задание           int w_cur = W ;    задание [ w_cur ] = j_cur ;   // минимальное снижение стоимости по ребрам от Z до рабочего w вектор < T > min_to ( W + 1 , inf );     vector < int > prv ( W + 1 , -1 ); // предыдущий рабочий на альтернативном пути      vector < bool > in_Z ( W + 1 ); // находится ли работник в Z     while ( job [ w_cur ] != -1 ) { // выполняется максимум j_cur + 1 раз      in_Z [ w_cur ] = true ;   const int j = job [ w_cur ];     Т дельта = инф ;    int w_next ;  для ( int w = 0 ; w < W ; ++ w ) {          если ( ! in_Z [ w ]) {   если ( ckmin ( min_to [ w ], C [ j ][ w ] - ys [ j ] - yt [ w ]))       prv [ w ] = w_cur ;   если ( ckmin ( delta , min_to [ w ])) w_next = w ;      } } // дельта всегда будет неотрицательной, // за исключением, возможно, первого раза, когда этот цикл выполняется // если какие-либо записи C[j_cur] отрицательны для ( int w = 0 ; w <= W ; ++ w ) {          если ( in_Z [ w ]) ys [ job [ w ]] += delta , yt [ w ] -= delta ;        иначе min_to [ w ] -= delta ;    } w_cur = w_next ;   } // обновить назначения по альтернативному пути для ( int w ; w_cur != W ; w_cur = w ) задание [ w_cur ] = задание [ w = prv [ w_cur ]];              ответы . push_back ( - yt [ W ]); } верните ответы ; }/*** Проверка работоспособности: https://en.wikipedia.org/wiki/Hungarian_algorithm/Hungarian_algorithm#Example* Первая работа (5):* чистая ванная комната: Боб -> 5* Первая + вторая работа (9):* чистая ванная комната: Боб -> 5* подметать полы: Алиса -> 4* Первая + вторая + третья работа (15):* чистая ванная комната: Элис -> 8* подметать полы: Кэрол -> 4* мытье окон: Боб -> 3*/void sanity_check_hungarian () {   вектор < вектор < int >> стоит {{ 8 , 5 , 9 }, { 4 , 2 , 4 }, { 7 , 3 , 8 }};          assert (( венгерский ( затраты ) == вектор < int > { 5 , 9 , 15 }));     cerr << "Проверка на работоспособность пройдена. \n " ;  }// решает https://open.kattis.com/problems/cordonbleuvoid cordon_bleu () {   целые N , M ;   cin >> N >> M ;     вектор < пара < целое , целое >> B ( N ), C ( M );    вектор < пара < целое , целое >> бутылки ( N ), курьеры ( M );    для ( auto & b : bottles ) cin >> b . first >> b . second ;          для ( auto & c : couriers ) cin >> c . first >> c . second ;          пара < целое , целое > остаток ;   cin >> rest . первый >> rest . второй ;     вектор < вектор < int >> затраты ( N , вектор < int > ( N + M - 1 ));       auto dist = [ & ]( пара < целое , целое > x , пара < целое , целое > y ) {          вернуть abs ( x.first - y.first ) + abs ( x.second - y.second ) ;        }; для ( int b = 0 ; b < N ; ++ b ) {          for ( int c = 0 ; c < M ; ++ c ) { // курьер -> бутылка -> ресторан           затраты [ б ][ с ] =  dist ( курьеры [ c ], бутылки [ b ]) + dist ( бутылки [ b ], остальное );     } for ( int _ = 0 ; _ < N - 1 ; ++ _ ) { // ресторан -> бутылка -> ресторан             затраты [ b ][ _ + M ] = 2 * расст ( бутылки [ b ], остальное );        } } cout << венгерский ( стоимость ). назад () << " \n " ;    }инт мейн () {   проверка_здравоохранения_венгерский (); cordon_bleu ();}

Соединение с последовательными кратчайшими путями

Венгерский алгоритм можно рассматривать как эквивалент последовательного алгоритма кратчайшего пути для потока минимальной стоимости, ^[8]^[9] , где метод перевеса из алгоритма Джонсона используется для поиска кратчайших путей. Реализация из предыдущего раздела переписывается ниже таким образом, чтобы подчеркнуть эту связь; можно проверить, что потенциалы для рабочих равны потенциалам из предыдущего решения с точностью до постоянного смещения. Когда граф разрежен (есть только разрешенные пары работа, рабочий), можно оптимизировать этот алгоритм для выполнения во времени, используя кучу Фибоначчи для определения вместо итерации по всем рабочим, чтобы найти тот, который имеет минимальное расстояние (упоминается здесь ). $ч$ $0\точки W-1$ $у$ $М$ $O(JM+J^{2}\log W)$ $w_{\text{следующий}}$ $W$

шаблон < класс T > вектор < T > венгерский ( const вектор < вектор < T >> & C ) {        const int J = ( int ) размер ( C ), W = ( int ) размер ( C [ 0 ]);        утверждение ( J <= W );   // job[w] = задание, назначенное w-му работнику, или -1, если задание не назначено // примечание: W-й работник был добавлен для удобства вектор < int > задание ( W + 1 , -1 );     вектор < T > h ( W ); // потенциалы Джонсона   вектор < T > ответы ;  T ans_cur = 0 ;    const T inf = numeric_limits < T >:: max ();     // назначить j_cur-th задание, используя Дейкстру с потенциалами для ( int j_cur = 0 ; j_cur < J ; ++ j_cur ) {          int w_cur = W ; // не посещенный работник с минимальным расстоянием     задание [ w_cur ] = j_cur ;   вектор < T > dist ( W + 1 , inf ); // Джонсон-редуцированные расстояния      расст [ Вт ] = 0 ;   вектор < bool > vis ( W + 1 ); // посещались ли уже     vector < int > prv ( W + 1 , -1 ); // предыдущий рабочий на кратчайшем пути      while ( job [ w_cur ] != -1 ) { // Шаг Дейкстры: извлечь минимальный рабочий процесс из кучи      T min_dist = инф ;    vis [ w_cur ] = true ;   int w_next = -1 ; // следующий не посещенный работник с минимальным расстоянием     // рассмотрим расширение кратчайшего пути с помощью w_cur -> job[w_cur] -> w для ( int w = 0 ; w < W ; ++ w ) {          если ( ! вис [ w ]) {   // сумма приведенных весов ребер w_cur -> job[w_cur] -> w T edge = C [ job [ w_cur ]][ w ] - h [ w ];      если ( w_cur != W ) {     edge -= C [ job [ w_cur ]][ w_cur ] - h [ w_cur ];     assert ( edge >= 0 ); // следствие потенциалов Джонсона    } если ( ckmin ( dist [ w ], dist [ w_cur ] + edge )) prv [ w ] = w_cur ;        если ( ckmin ( min_dist , dist [ w ])) w_next = w ;      } } w_cur = w_next ;   } for ( int w = 0 ; w < W ; ++ w ) { // обновить потенциалы           ckmin ( dist [ w ], dist [ w_cur ]);  ч [ ш ] += расст [ ш ];   } ans_cur += h [ w_cur ];   для ( int w ; w_cur != W ; w_cur = w ) задание [ w_cur ] = задание [ w = prv [ w_cur ]];              ответы . push_back ( ans_cur ); } верните ответы ; }

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

Этот вариант алгоритма следует формулировке, данной Флудом ^[10], и позднее более подробно описанной Манкресом, который доказал, что он работает во времени. ^[4] Вместо того, чтобы отслеживать потенциалы вершин, алгоритм работает только с матрицей: ${\mathcal {O}}(n^{4})$

a_{ij}:=c(i,j)-y(i)-y(j)

где — исходная матрица стоимости, а — потенциалы из интерпретации графика. Изменение потенциалов соответствует добавлению или вычитанию из строк или столбцов этой матрицы. Алгоритм начинается с . Таким образом, его можно рассматривать как взятие исходной матрицы стоимости и ее изменение. $c(i,j)$ $y(i),y(j)$ $a_{ij}=c(i,j)$

При наличии $n$ работников и задач задача записывается в виде матрицы затрат $n$ × $n .$

где a, b, c и d — работники, которые должны выполнить задачи 1, 2, 3 и 4. a ₁ , a ₂ , a ₃ и a ₄ обозначают штрафы, возникающие, когда работник «a» выполняет задачи 1, 2, 3 и 4 соответственно.

Проблема эквивалентна назначению каждому работнику уникальной задачи таким образом, чтобы общий штраф был минимизирован. Обратите внимание, что над каждой задачей может работать только один работник.

Шаг 1

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

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

Нули выше — это назначенные задачи.

В худшем случае есть $n$ ! комбинаций, которые нужно попробовать, поскольку несколько нулей могут появиться в строке, если несколько элементов являются минимальными. Поэтому в какой-то момент этот наивный алгоритм должен быть сокращен.

Шаг 2

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

Чтобы преодолеть это, мы повторяем описанную выше процедуру для всех столбцов (т.е. минимальный элемент в каждом столбце вычитается из всех элементов в этом столбце ), а затем проверяем, возможно ли назначение со штрафом 0.

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

Шаг 3

Все нули в матрице должны быть покрыты путем маркировки как можно меньшего количества строк и/или столбцов. Шаги 3 и 4 образуют один из способов достижения этого.

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

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

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

Шаг 4

Охватите все столбцы, содержащие (отмеченный звездочкой) ноль.

Найдите не покрытый ноль и сделайте его штрихом (отметьте его символом штриха ). Если такой ноль не найден, то есть все нули покрыты, перейдите к шагу 5.

Если ноль находится в той же строке, что и отмеченный звездочкой ноль, закройте соответствующую строку и откройте столбец отмеченного звездочкой нуля.
Затем перейдите к пункту «Найти незакрытый ноль и приравнять его».
- Здесь второй ноль строки 1 открыт. Поскольку в строке 1 есть еще один отмеченный звездочкой ноль, мы закрываем строку 1 и открываем столбец 1.
- Затем открывается второй ноль строки 2. Закрываем строку 2 и открываем столбец 2.

В противном случае непокрытый ноль не имеет назначенного нуля в своей строке. Мы создаем путь, начинающийся с нуля, выполняя следующие шаги:
1. Подшаг 1: Найдите отмеченный звездочкой ноль в соответствующем столбце. Если он есть, перейдите к Подшагу 2, иначе остановитесь.
2. Подшаг 2: Найдите штрихованный ноль в соответствующей строке (он всегда должен быть). Перейти к подшагу 1.

Ноль в строке 3 не закрыт. Добавляем к пути первый ноль строки 1, затем второй ноль строки 1, и все готово.

(Иначе ветвь продолжается) Для всех нулей, встречающихся на пути, звездочкой помечаются нули и звездочкой не помечаются нули.
- Так как путь начинается и заканчивается штрихованным нулем, при перестановке звездчатых нулей мы присваиваем еще один ноль.

(Иначе ветвь продолжается) Убрать штриховку со всех штрихованных нулей и раскрыть все линии.
Повторите предыдущие шаги (продолжайте цикл, пока не достигнете указанного выше «перехода к шагу 5»).
- Закрываем столбцы 1, 2 и 3. Второй ноль в строке 2 не закрыт, поэтому закрываем строку 2 и открываем столбец 2:

Все нули теперь покрыты минимальным количеством строк и столбцов.

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

Шаг 5

Если количество отмеченных нулей равно $n$ (или в общем случае , где $n$ — количество людей, а $m$ — количество рабочих мест), алгоритм завершается. См. подраздел Результат ниже о том, как интерпретировать результаты. $мин(н,м)$

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

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

Результат

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

Из теоремы Кёнига ^[11] минимальное количество линий (минимальное вершинное покрытие ^[12] ) будет равно $n$ (размер максимального паросочетания ^[13] ). Таким образом, когда требуется $n$ линий, назначение минимальной стоимости можно найти, рассматривая только нули в матрице.

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

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

Ссылки

↑ Гарольд В. Кун, «Венгерский метод решения задачи о назначениях», Naval Research Logistics Quarterly , 2 : 83–97, 1955. Оригинальная публикация Куна.
↑ Гарольд В. Кун, «Варианты венгерского метода для задач о назначениях», Naval Research Logistics Quarterly , 3 : 253–258, 1956.
^ "Презентация". Архивировано из оригинала 16 октября 2015 года.
^ ab J. Munkres, «Алгоритмы для задач назначения и транспортировки», Журнал Общества промышленной и прикладной математики , 5 (1):32–38, март 1957 г.
^ Эдмондс, Джек; Карп, Ричард М. (1 апреля 1972 г.). «Теоретические улучшения в алгоритмической эффективности для проблем сетевых потоков». Журнал ACM . 19 (2): 248–264. doi : 10.1145/321694.321699 . S2CID 6375478.
^ Томизава, Н. (1971). «О некоторых методах, полезных для решения проблем транспортных сетей». Networks . 1 (2): 173–194. doi :10.1002/net.3230010206. ISSN 1097-0037.
^ "Венгерский алгоритм решения задачи о назначениях". e-maxx :: algo . 23 августа 2012 г. Получено 13 мая 2023 г.
^ Якоб Коглер (20 декабря 2022 г.). "Поток минимальной стоимости - Последовательный алгоритм кратчайшего пути". Алгоритмы для соревновательного программирования . Получено 14 мая 2023 г.
^ "Решение задачи назначения с использованием потока минимальной стоимости". Алгоритмы для соревновательного программирования . 17 июля 2022 г. Получено 14 мая 2023 г.
^ Флуд, Меррилл М. (1956). «Проблема коммивояжера». Исследование операций . 4 (1): 61–75. doi :10.1287/opre.4.1.61. ISSN 0030-364X.
^ Теорема Кёнига (теория графов) Теорема Кёнига
^ Покрытие вершин минимальное покрытие вершин
^ Сопоставление (теория графов) сопоставление

Внешние ссылки

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

Реализации

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

Версии кода RA Pilgrim на Lua и Python (заявляющие сложность O ( n 3 ) {\displaystyle O(n^{3})})
Реализация Джулии
Реализация C, требующая O ( n 3 ) {\displaystyle O(n^{3})} временной сложности
Реализация Java, заявляющая сложность 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})} ) Архивировано 30 декабря 2019 г. на Wayback Machine
Онлайн интерактивная реализация
Последовательные и параллельные реализации.
Matlab и C Архивировано 3 мая 2008 г. на Wayback Machine
Реализация Perl
Реализация на С++
Реализация C++, заявляющая сложность по времени O ( n 3 ) {\displaystyle O(n^{3})} (с открытым исходным кодом в стиле BSD)
Реализация MATLAB
Реализация на языке С
Реализация JavaScript с модульными тестами (порт версии Java, заявляющей сложность O ( n 3 ) {\displaystyle O(n^{3})})
Пакет Clue R предлагает реализацию, resolve_LSAP
Реализация Node.js на GitHub
Реализация Python в пакете scipy