Algoritm maghiar

În matematică , metoda maghiară ^[1] ^[2] , sau algoritmul maghiar , este o metodă de optimizare combinatorie care rezolvă problema de atribuire în timp polinomial . Metoda a fost dezvoltată de Harold Kuhn în 1955 , anticipând metodele dual-primale ^[3] ulterioare, și este numită „maghiară”, deoarece se bazează ^[4] ^[5] pe lucrările lui Dénes König ^[6] și Jenő Egerváry ^{[7] ]} . În 2006, a fost descoperită o lucrare a lui Carl Jacobi , datând din secolul al XIX-lea , care rezolvă aceeași problemă ^[8] . Complexitatea algoritmului a fost $O(n^{4})$ ${\ displaystyle O (n ^ {4})}$ $O (n ^ 4)$ , dar s-a demonstrat că prin modificarea ușoară a algoritmului este posibil să se obțină o complexitate de calcul egală cu $O(n^{3})$ ${\ displaystyle O (n ^ {3})}$ $O (n ^ 3)$ .

Definirea problemei

Același subiect în detaliu: Problema atribuirii .

Problema de atribuire necesită asocierea perechilor de elemente preluate din două seturi diferite. Având în vedere că un cost este asociat fiecărei perechi, dorim să minimizăm costul total. De exemplu: luând în considerare un set de angajați, un set de sarcini care trebuie îndeplinite și timpul pe care fiecare sarcină l-ar necesita dacă este efectuat de un anumit angajat, doriți să asociați fiecare angajat cu o sarcină pentru a minimiza timpul total necesar.

Formal dat o matrice $n\times n$ ${\ displaystyle n \ times n}$ $n \ ori n$ a costurilor $C=(c_{ij})$ ${\ displaystyle C = (c_ {ij})}$ $C = (c_ {ij})$ , vrem să găsim o permutare $\phi$ ${\ displaystyle \ phi}$ $\ phi$ din $\{1,\dots ,n\}$ ${\ displaystyle \ {1, \ dots, n \}}$ $\ {1, \ dots, n \}$ pe care o minimizezi $\sum _{i=1}^{n}c_{i\phi (i)}$ ${\ displaystyle \ sum _ {i = 1} ^ {n} c_ {i \ phi (i)}}$ $\ sum_ {i = 1} ^ n c_ {i \ phi (i)}$ .

Algoritm

Problema este codificată folosind un grafic bipartit , unde vârfurile sunt elementele care trebuie asociate, iar arcele reprezintă posibilele alegeri de perechi. Fiecare arc are un cost asociat. În mod formal, se ia în considerare graficul $G=(U,V;E)$ ${\ displaystyle G = (U, V; E)}$ $G = (U, V; E)$ unde U și V sunt cele două seturi de elemente care trebuie asociate și E este setul de arce.

Algoritmul pleacă de la orice soluție posibilă, chiar parțială, a problemei și încearcă să o îmbunătățească verificând prezența elementelor neatribuite.

La fiecare iterație, algoritmul încearcă să găsească o cale care crește numărul de elemente din soluție. Prima iterație începe de la un element de $u\in U$ ${\ displaystyle u \ in U}$ $u \ in U$ nealocat. Există două posibilități:

există un arc care leagă elementul u de un element $v\in V$ ${\ displaystyle v \ in V}$ $v \ în V$ nu face parte din soluție
există doar arce care conectează elementul u la elementele lui V deja atribuite

În primul caz, atribuirea dintre u și v se adaugă la soluție.

Interpretarea matricială a algoritmului

Dat fiind o matrice pătrată de ordine $n$ ${\ displaystyle n}$ $n$ reprezentând matricea de cost a problemei de atribuire, algoritmul funcționează după cum urmează

Pentru fiecare rând, găsiți minimul și scădeți-l din toate elementele rândului;
Pentru fiecare coloană, găsiți minimul și scădeți-l din toate elementele coloanei;
Acoperiți cu cel mai mic număr de linii toate zerourile care s-au format cu scăderile anterioare;
Dacă numărul minim de linii necesar este egal cu $n$ ${\ displaystyle n}$ $n$ este posibil să se determine o atribuire optimă, altfel se continuă cu pasul 5;
Identificați minimul dintre elementele care nu sunt acoperite de linii, scădeți-l din elementele care nu sunt acoperite și adăugați-l la elementele care sunt intersecții ale două linii. Reveniți la pasul 3.

Pentru a determina cel mai mic număr de linii necesare pentru a acoperi toate zerourile formate (pasul 3) se poate utiliza următorul algoritm:

Determinați o sarcină (chiar incompletă, adică o sarcină în care poate exista un rând care nu este atribuit niciunei coloane);
Marcați liniile neatribuite;
Pentru fiecare rând marcat neexaminat încă, marcați coloanele care au un zero pe acel rând;
Pentru fiecare coloană nemarcată, marcați rândurile care au o alocare acelor coloane;
Repetați de la pasul 3 până când toate liniile marcate care nu au fost încă vizitate sunt epuizate;
Numărul minim de linii se obține selectând coloane marcate și linii nemarcate.

Exemplu

Având în vedere următoarea matrice de costuri

$C_{0}={\begin{bmatrix}30&18&9&39&97\\30&3&56&9&3\\86&94&13&31&34\\24&72&59&30&4\\10&87&25&57&29\\\end{bmatrix}}$ ${\ displaystyle C_ {0} = {\ begin {bmatrix} 30 & 18 & 9 & 39 & 97 \\ 30 & 3 & 56 & 9 & 3 \\ 86 & 94 & 13 & 31 & 34 \\ 24 & 72 & 59 & 30 & 4 \\ 10 & 87 & 25 & 57 & 29 \\\ end {bmatrix}}}$ ${\ displaystyle C_ {0} = {\ begin {bmatrix} 30 & 18 & 9 & 39 & 97 \\ 30 & 3 & 56 & 9 & 3 \\ 86 & 94 & 13 & 31 & 34 \\ 24 & 72 & 59 & 30 & 4 \\ 10 & 87 & 25 & 57 & 29 \\\ end {bmatrix}}}$

Minimele rândurilor sunt (de sus în jos): 9, 3, 13, 4, 10. Scăzându-le din rândurile respective obținem următoarea matrice:

$C_{1}={\begin{bmatrix}21&9&0&30&88\\27&0&53&6&0\\73&81&0&18&21\\20&68&55&26&0\\0&77&15&47&19\\\end{bmatrix}}$ ${\ displaystyle C_ {1} = {\ begin {bmatrix} 21 & 9 & 0 & 30 & 88 \\ 27 & 0 & 53 & 6 & 0 \\ 73 & 81 & 0 & 18 & 21 \\ 20 & 68 & 55 & 26 & 0 \\ 0 & 77 & 15 & 47 & 19 \\\ end {bmatrix}}}$ ${\ displaystyle C_ {1} = {\ begin {bmatrix} 21 & 9 & 0 & 30 & 88 \\ 27 & 0 & 53 & 6 & 0 \\ 73 & 81 & 0 & 18 & 21 \\ 20 & 68 & 55 & 26 & 0 \\ 0 & 77 & 15 & 47 & 19 \\\ end {bmatrix}}}$

Minimele coloanei sunt (de la stânga la dreapta): 0, 0, 0, 6, 0. Scăzându-le din coloanele respective obținem:

$C_{2}={\begin{bmatrix}21&9&0&24&88\\27&0&53&0&0\\73&81&0&12&21\\20&68&55&20&0\\0&77&15&41&19\\\end{bmatrix}}$ ${\ displaystyle C_ {2} = {\ begin {bmatrix} 21 & 9 & 0 & 24 & 88 \\ 27 & 0 & 53 & 0 & 0 \\ 73 & 81 & 0 & 12 & 21 \\ 20 & 68 & 55 & 20 & 0 \\ 0 & 77 & 15 & 41 & 19 \\\ end {bmatrix}}}$ ${\ displaystyle C_ {2} = {\ begin {bmatrix} 21 & 9 & 0 & 24 & 88 \\ 27 & 0 & 53 & 0 & 0 \\ 73 & 81 & 0 & 12 & 21 \\ 20 & 68 & 55 & 20 & 0 \\ 0 & 77 & 15 & 41 & 19 \\\ end {bmatrix}}}$

O atribuire (incompletă) este determinată prin derularea rândurilor și atribuirea acestora la prima coloană posibilă. Adică, se determină următoarea atribuire (elementele atribuite sunt cu caractere aldine):

$A_{1}={\begin{bmatrix}21&9&\mathbf {0} &24&88\\27&\mathbf {0} &53&0&0\\73&81&0&12&21\\20&68&55&20&\mathbf {0} \\\mathbf {0} &77&15&41&19\\\end{bmatrix}}$ ${\ displaystyle A_ {1} = {\ begin {bmatrix} 21 & 9 & \ mathbf {0} & 24 & 88 \\ 27 & \ mathbf {0} & 53 & 0 & 0 \\ 73 & 81 & 0 & 12 & 21 \\ 20 & 68 & 55 & 20 & \ mathbf {0} \\\ mathbf {0} & 77 & 15 & 41 & 19 \\ end {bmatrix}}}$ ${\ displaystyle A_ {1} = {\ begin {bmatrix} 21 & 9 & \ mathbf {0} & 24 & 88 \\ 27 & \ mathbf {0} & 53 & 0 & 0 \\ 73 & 81 & 0 & 12 & 21 \\ 20 & 68 & 55 & 20 & \ mathbf {0} \\\ mathbf {0} & 77 & 15 & 41 & 19 \\ end {bmatrix}}}$

Acum continuăm cu determinarea numărului minim de linii pentru a acoperi elementele nule ale matricei. Linia 3 care nu este atribuită este marcată. Acest rând are un zero în coloana 3 (care este marcată). Această coloană are o atribuire pentru rândul 1 (care este marcat). Rândul 1 (care a fost marcat în iterația anterioară) este acum examinat. Acest rând are un zero în coloana 3 care este deja marcat. Nu există alte coloane marcate neexaminate și rânduri marcate neexaminate. Numărul minim de linii este dat de coloanele marcate (coloana 3) și liniile nemarcate (liniile 2, 4, 5) $4<5=n$ ${\ displaystyle 4 <5 = n}$ ${\ displaystyle 4 <5 = n}$ linii. Nu este posibil să se determine o sarcină completă și să se treacă la pasul 5.

Se determină minimul dintre elementele care nu sunt acoperite de linii, adică minimul următoarei matrice obținut prin eliminarea elementelor acoperite de linii:

${\hat {C}}_{0}={\begin{bmatrix}21&9&24&88\\73&81&12&21\\\end{bmatrix}}$ ${\ displaystyle {\ hat {C}} _ {0} = {\ begin {bmatrix} 21 & 9 & 24 & 88 \\ 73 & 81 & 12 & 21 \\\ end {bmatrix}}}$ ${\ displaystyle {\ hat {C}} _ {0} = {\ begin {bmatrix} 21 & 9 & 24 & 88 \\ 73 & 81 & 12 & 21 \\\ end {bmatrix}}}$

care este 9. Această valoare trebuie scăzută din elementele care nu sunt acoperite de linii și adăugată elementelor de trecere a două linii. Cu alte cuvinte, obținem:

$C_{3}={\begin{bmatrix}12&0&0&15&79\\27&0&62&0&0\\64&72&0&3&12\\20&68&64&20&0\\0&77&24&41&19\\\end{bmatrix}}$ ${\ displaystyle C_ {3} = {\ begin {bmatrix} 12 & 0 & 0 & 15 & 79 \\ 27 & 0 & 62 & 0 & 0 \\ 64 & 72 & 0 & 3 & 12 \\ 20 & 68 & 64 & 20 & 0 \\ 0 & 77 & 24 & 41 & 19 \\\ end {bmatrix}}}$ ${\ displaystyle C_ {3} = {\ begin {bmatrix} 12 & 0 & 0 & 15 & 79 \\ 27 & 0 & 62 & 0 & 0 \\ 64 & 72 & 0 & 3 & 12 \\ 20 & 68 & 64 & 20 & 0 \\ 0 & 77 & 24 & 41 & 19 \\\ end {bmatrix}}}$

O atribuire (posibil incompletă) este acum determinată prin derularea rândurilor și atribuirea primei coloane posibile. Se obține

$A_{2}={\begin{bmatrix}12&\mathbf {0} &0&15&79\\27&0&62&\mathbf {0} &0\\64&72&\mathbf {0} &3&12\\20&68&64&20&\mathbf {0} \\\mathbf {0} &77&24&41&19\\\end{bmatrix}}$ ${\ displaystyle A_ {2} = {\ begin {bmatrix} 12 & \ mathbf {0} & 0 & 15 & 79 \\ 27 & 0 & 62 & \ mathbf {0} & 0 \\ 64 & 72 & \ mathbf {0} & 3 & 12 \\ 20 & 68 & 64 & 20 & \ mathbf {0} \\\ mathbf {0} & 77 & 24 & 41 & 19 \\\ end {bmatrix}}}$ ${\ displaystyle A_ {2} = {\ begin {bmatrix} 12 & \ mathbf {0} & 0 & 15 & 79 \\ 27 & 0 & 62 & \ mathbf {0} & 0 \\ 64 & 72 & \ mathbf {0} & 3 & 12 \\ 20 & 68 & 64 & 20 & \ mathbf {0} \\\ mathbf {0} & 77 & 24 & 41 & 19 \\\ end {bmatrix}}}$

Toate liniile sunt atribuite, deci nu sunt marcate linii. Liniile necesare pentru a acoperi toate elementele nule sunt date de coloanele marcate (niciuna) și liniile nemarcate (toate) și sunt $5=n$ ${\ displaystyle 5 = n}$ ${\ displaystyle 5 = n}$ este deci posibil să atribuiți toate liniile și atribuirea este dată de $A_{2}$ ${\ displaystyle A_ {2}}$ $A_2$ .

Bibliografie

( LA ) Jacobi, CGJ și Borchardt, CW , De investigandoorder systematis aequationum Differentialium vulgarium cujuscunque , în Jurnalul lui Crelle , vol. 64, 1865, pp. 297-320. Adus pe 19 noiembrie 2013 .
( DE ) Dénes König, Theorie der endlichen und unendlichen graphen , Leipzig, Akademische Verlagsgesellschaft MBH, 1936.
( HU ) Egerváry, Jenő, Matrixok kombinatorius tulajdonságairól , în Matematikai és Fizikai Lapok , vol. 38, 1931, pp. 16-28.
- tradus în ( EN ) Kuhn, Harold W., Despre proprietățile combinatorii ale matricilor , în Logistics Papers , vol. 11, n. 4, 1955, pp. 1-11.
( EN ) Kuhn, HW, Metoda maghiară pentru problema atribuirii , în jurnalul de rezoluție navală. Quart. , vol. 2, 1955, pp. 83-97.
( EN ) Kuhn, HW, Variante ale metodei maghiare pentru problema atribuirii , în Naval Res. Log. Quart. , vol. 3, 1956, pp. 253-258.
( EN ) GB Dantzig, LR Ford și DR Fulkerson,Un algoritm primal-dual pentru programe liniare , în HW Kuhn, AW. Tucker (eds), Inegalități liniare și sisteme conexe , Princeton, Princeton University Press, 1956, pp. 171 -181.
( EN ) HW Kuhn, Despre originea metodei maghiare pentru problema atribuirii , în JK Lenstra, AHG Rinnooy Kan, A. Schrijver (ed.), History of Mathematical Programming , Amsterdam, North-Holland, 1991, pp. 77-81, ISBN 0-444-88818-7 .
( EN ) Rainer Burkard, Mauro Dell'Amico și Silvano Martello, Linear sum assignment problem ( PDF ), în Assignment Problems - Revised Reprint , Philadelphia, Society for Industrial and Applied Mathematics, 2012, p. 79, ISBN 978-1-61197-222-1 .
S. Martello, „Jeno Egerváry: de la originile algoritmului maghiar la comunicarea prin satelit”, Central European Journal of Operations Research 18, 47–58, 2010

Portalul de matematică : accesați intrările Wikipedia care se ocupă cu matematica

[1] Kuhn

[2] Kuhn

[3] Dantzig, Ford, Fulkerson

[4] Burkard și colab.

[5] Kuhn

[6] König

[7] Egerváry .

[8] Jacobi

[1]

[2]

[3]

[4]

[5]

[6]

[7] ]

[8]