Мађарски алгоритам

Мађарски алгоритам је комбинаторијални оптимизациони алгоритам који решава проблем доделе који има сложеност субекспоненцијално времена и који ишчекује касније примал-дуал методе. Развио га је и објавио 1955. године Харолд Кан, који га је назвао Мађарски алгоритам јер је он свој рад засновао на раду двојице мађарских математичара: Dénes Kőnig and Jenő Egerváry.

Џејмс Манкрес је процени о алоритам 1957. и увидео да је временса сложеност субекспоненцијално време. Од тада је алгоритам познат и као Кан-Манкресов алгоритам или Манкресов алгоритам доделе. Теорија комплексности овог алгоритам је била О(n^4), али су Едмондс и Карп, и одвојено од њих Томицава увидели да може да достигне и кубну сложеност. Форд и Фалкерсон су унапредили методу до општег проблема транспортације. 2006. откривено је да је Карл Густав Џакоби решио тај проблем у 19. веку, и да је решење објављено 1890. на латинском језику.

Једноставно објашњење проблема доделе

У овом примеру постоје тру радника: Пера, Мика и Жика. Један од њих мора да очисти тоалет, један да брише подове, и један да пере прозоре, али сва тројица траже различиту плату за различите проблеме. Проблем је наћи најјефтинији начин да се расподели посао. Проблем може да се представи матрицом цена. На пример:

	Брисање тоалета	Брисање подова	Брисање прозора
Пера	$2	$3	$3
Мика	$3	$2	$3
Жика	$3	$3	$2

Мађарска метода, када се примени на табелу изнад, даје минималну цену, која би била 6$ тако што би Пера прао тоалет, Мика брисао подове, а Жика прозоре.

Подешавање

Узимамо ненегативну квадратну матрицу, где је елемент у i-тој колони и ј-том реду представља цену доделе ј-тог посла i-том раднику. Морамо да нађемо посао радницима који ће нас најмање коштати. 

Алгоритам се може једноставније објаснити ако формулишемо проблем помоћу бипартитивног графа. Ако имамо потпуни бипартитивни граф G = (S, T, E) са n радника грана (S) и n послова грана (T), где свака грана има ненегативну цену c(i, j). Хоћемо да нађемо најбоље поклапање са минималном ценом.

Сада позивамо функцију y: (S U T) -> R чији је потенцијал y(i) + y(j) <= c(i, j) за свако i које припада S, j који припадају T. Може се приметити да је цена савршеног поклапања  бар вредност сваког потенцијала. Мађарска метода налази савршено поклапање и потенцијал са једнаким ценама који доказује оптималност.

Алгоритам представљен преко бипартитивног графа

Током рада алгоритма чувамо потенцијал y и оријентацију Gy која има особину да су све гране оријентисане од Т до S чине поклапање М. Иницијано y је 0 свуда, и све гране су оријентисане од S до Т, а М је празно. У сваком корак уили мењамо y тако што му вредност повећавамо или мењамо оријантацију да бисмо постигли поклапање са више грана. Завршили смо ако је М савршено поклапање.

У генералном кораку, нека су $R_{S}\subseteq S$ and $R_{T}\subseteq T$ чворови који нису пређени са M (тако се $R_{S}$ састоји од чворова у S без улазних грана и $R_{T}$ који се садржи од чворова из T без излазних грана). Нека је $Z$ сет чворова који могу да се дохвате у  ${\overrightarrow {G_{y}}}$ од $R_{S}$ помоћу усмерене путање која прати само гране које су збијене. Ово може да се израчуна помоћу претраге у дубину.

Ако је $R_{T}\cap Z$ непразан, онда окрени оријентацију путање усмереног графа  ${\overrightarrow {G_{y}}}$ од $R_{S}$ до $R_{T}$. Тако је величина одговарајућих поклапања повећана за 1.

Ако је $R_{T}\cap Z$ празан, онда нека је$\Delta :=\min\{c(i,j)-y(i)-y(j):i\in Z\cap S,j\in T\setminus Z\}$. $\Delta$ позитиван јер нема збијених грана у $Z\cap S$ и  $T\setminus Z$. Повећај y by $\Delta$ на чворовима $Z\cap S$ и смањи y за $\Delta$ на чвороима $Z\cap T$. Резултујуће y је и даље потенцијал. Граф $G_{y}$ се мења, али и даље садржи M. Оријентишемо нове гране од S до T. По дефиницији $\Delta$ сет Z чворова који могу да се дохвате од $R_{S}$ се повећава (напомена је да се број збијених грана не мора повећати).

Понављамо ове кораке све док М јесте савршено поклапање, и том случају добијамо минималну цену за доделу. Сложеност ове верзије је О(n^4): М се повећава n пута, а у фази где је М непромењено, постоји највише n потенцијалних промена. Време које је потребно за потенцијалну промену је О(n^2).

Интерпретација алгоритма преко матрица

Ако имамо n радника и задатака, и nxn матрицу која садржи цене доделе неког посла сваком раднику, тражимо најбољу варијанту.

Прво се проблем задаје као матрица испод:

${\begin{bmatrix}a1&a2&a3&a4\\b1&b2&b3&b4\\c1&c2&c3&c4\\d1&d2&d3&d4\end{bmatrix}}$

где су a, b, c, и d радници који морају да раде послове 1, 2, 3, 4. а1, а2, а3, и а4 обележавају шта би се десило кад би радник а, радио одређене задатке. Исто важи и за остале симболе такође. Матрица је квадратна, тако да сваки радник може да обавља један посао.

Корак 1

Онда радимо операције са колонама. Да бисмо извели то, најмањи од аи се умањујеод всаког елемент ау том реду. То ће довести до бар једне нуле у том реду. Ова радња се обавља за све колоне. Сада имамо матрицу са најмање једном нулом по једном реду. Сада покушавамо да доделимо послове агентима тако да сваки агент ради само један посао. Ово је илустровано испод:

0	a2'	a3'	a4'
b1'	b2'	b3'	0
c1'	0	c3'	c4'
d1'	d2'	0	d4'

Нуле које су описане као 0’ су додељени послови

Корак 2

Понекад се може испоставити да је матрицу у овој гази неупотребљива за операцију доделе, као што је приказано у примеру испод.

0	a2'	a3'	a4'
b1'	b2'	b3'	0
0	c2'	c3'	c4'
d1'	0	d3'	d4'

У случају изнад, ниједна додела не може да се изврши. Напомена је да се у задатак 1 ефикасно одрадио за агента а и c. Не могу обојица да добију исти задатак. Такође треба напоменути да нико не обавља задатак 3 ефикасно. Да би се ово превазишло, понављамо процедуру изнас по свим колонама, и онда опет гледамо да ли су доделе могуће.

У већини случајева ће ово да да резултат, али ако не, процес се опет понавља итд.

Корак 3

Све нуле у матрици морају да буду прођене тако што ћемо маркирати што мање колона и редова је могуће. Следећа процедура обавља то:

Прво, додељујемо што више задатака је могуће.

• Ред 1 има једну нулу, значи да је додељен. Нула у реду 3 је прецртана јер је у истој колони 
• Ред 2 има једну нулу, и онда је додељена 
• Једина нула у реду 3 је прецртана, тако да ништа није додељено 
• Ред 4 има две непрецртане нуле. Било која од њих може бити додељена, а друга нула ће бити прецртана 

Алтерантивно, нула у реду 3 може бити додељена, што би проузроковало нулу у првом реду да буде прецртана.

0'	a2'	a3'	a4'
b1'	b2'	b3'	0'
0	c2'	c3'	c4'
d1'	0'	0	d4'

А сад део са цртањем:

• Обележимо све редове који немају доделе 
• Обележимо све неозначене колоне које имају нуле у новообележеним редовима 
• Обележимо све редове које имају колоне са претходне тачке 
• Понављамо за све неозначене редове 

×
0'	a2'	a3'	a4'	×
b1'	b2'	b3'	0'
0	c2'	c3'	c4'	×
d1'	0'	0	d4'

Сада цртамо линије кроз све обележене колоне и необележене редове

×
0'	a2'	a3'	a4'	×
b1'	b2'	b3'	0'
0	c2'	c3'	c4'	×
d1'	0'	0	d4'

Ово је само један начин за цртање матрице. Постоји још неколико доказаних и проверених начина са истим исходом

Корак 4

Сада уклањамо обележене редове и колоне. Онда ће матрица изгледати овако.

${\begin{bmatrix}a2&a3&a4\\c2&c3&c4\end{bmatrix}}$

Вратимо се на корак 1 и понаљавмо процес док матрица није празна.

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

• R.E. Burkard, M. Dell'Amico, S. Martello: Assignment Problems (Revised reprint). SIAM, Philadelphia (PA.). 2012. ISBN 978-1-61197-222-1.
• M. Fischetti, "Lezioni di Ricerca Operativa", Edizioni Libreria Progetto Padova, Italia, 1995.
• R. Ahuja, T. Magnanti, J. Orlin, "Network Flows", Prentice Hall, 1993.
• S. Martello, "Jeno Egerváry: from the origins of the Hungarian algorithm to satellite communication". Central European Journal of Operations Research 18, 47–58, 2010

Спољашње везе

• Bruff, Derek, "The Assignment Problem and the Hungarian Method", [1] Архивирано на сајту Wayback Machine (5. јануар 2012)
• Mordecai J. Golin, Bipartite Matching and the Hungarian Method, Course Notes, Hong Kong University of Science and Technology.
• R. A. Pilgrim, Munkres' Assignment Algorithm.Modified for Rectangular Matrices Архивирано на сајту Wayback Machine (27. март 2007), Course notes, Murray State University.
• Mike Dawes, The Optimal Assignment Problem, Course notes, University of Western Ontario.
• On Kuhn's Hungarian Method – A tribute from Hungary Архивирано на сајту Wayback Machine (9. август 2017), András Frank, Egervary Research Group, Pazmany P. setany 1/C, H1117, Budapest, Hungary.
• Lecture: Fundamentals of Operations Research - Assignment Problem - Hungarian Algorithm, Prof. G. Srinivasan, Department of Management Studies, IIT Madras.
• Extension: Assignment sensitivity analysis (with O(n^4) time complexity), Liu, Shell.
• Solve any Assignment Problem online, provides a step by step explanation of the Hungarian Algorithm.

Имплементације

(Напомена: неће сви алгоритми испод да задовоље  O(n^3) сложеност)

• C implementation with $O(n^{3})$ time complexity
• Java implementation of $O(n^{3})$ time variant
• Python implementation (see also here)
• Ruby implementation with unit tests
• C# implementation
• D implementation with unit tests (port of the Java $O(n^{3})$ version) Архивирано на сајту Wayback Machine (30. децембар 2019)
• Online interactive implementation Please note that this implements a variant of the algorithm as described above.
• Graphical implementation with options (Java applet)
• Serial and parallel implementations.
• Implementation in Matlab and C Архивирано на сајту Wayback Machine (3. мај 2008)
• Perl implementation
• Lisp implementation
• C++ (STL) implementation (multi-functional bipartite graph version) Архивирано на сајту Wayback Machine (16. фебруар 2020)
• C++ implementation
• C++ implementation of the $O(n^{3})$ algorithm (BSD style open source licensed)
• Another C++ implementation with unit tests
• MATLAB implementation
• C implementation
• Javascript implementation
• The clue R package proposes an implementation, solve_LSAP