Algoritm maghiar

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 4 martie 2020; verificările necesită 6 modificări .

Algoritmul maghiar este un algoritm de optimizare care rezolvă problema de atribuire în timp polinomial (vezi cercetarea operațională ). A fost dezvoltat și publicat de Harold Kuhn în 1955 . Autorul i-a dat numele „Metoda maghiară” datorită faptului că algoritmul se bazează în mare parte pe lucrările anterioare a doi matematicieni maghiari König și Egerváry

James Mancres a observat în 1957 că algoritmul este (strict) polinom. Din acel moment, algoritmul a fost cunoscut și ca algoritmul Kuhn-Mankres sau algoritmul Mankres pentru rezolvarea problemei de atribuire . Complexitatea temporală a algoritmului original a fost, dar Edmonds Karp precum și au arătat că acesta ar putea fi modificat pentru a obține un timp de rulare de. Algoritmul maghiar modificat se numește algoritmul Hopcroft-Karp. Ford și Fulkerson au extins metoda la problemele generale de transport. În 2006, s-a descoperit că Jacobi a găsit o soluție din secolul al XIX-lea la problema misiunii, care a fost publicată în latină într-o colecție postumă din 1890 de lucrări. [1] [2] $O(n^{4})$ $O(n^{3})$

Exemplu

Să presupunem că sunt trei angajați: Ivan, Peter și Andrey. Este necesar să se repartizeze între ele efectuarea a trei tipuri de muncă (pe care le vom numi A, B, C), fiecare muncitor trebuie să efectueze un singur tip de muncă. Cum să o faci în așa fel încât să cheltuiești cea mai mică sumă de bani pe salariile muncitorilor? Mai întâi trebuie să construiți o matrice de costuri .

	A	B	C
Ivan	10.000 de ruble.	20.000 de ruble.	30.000 de ruble.
Petru	30.000 de ruble.	30.000 de ruble.	30.000 de ruble.
Andrew	30.000 de ruble.	30.000 de ruble.	20.000 de ruble.

Algoritmul maghiar aplicat tabelului de mai sus ne va oferi distribuția necesară: Ivan face job A, Peter face job B, Andrey face job C.

Enunțul problemei

Având în vedere o matrice n × n nenegativă , în care elementul din rândul i și din coloana j corespunde costului efectuării celui de al j -lea tip de muncă de către lucrătorul i -lea. Este necesar să se găsească o astfel de corespondență a muncii cu angajații, astfel încât costurile cu forța de muncă să fie cele mai mici. Dacă scopul este găsirea destinației cu cel mai mare cost, atunci soluția se reduce la rezolvarea problemei tocmai formulate prin înlocuirea fiecărui cost C cu diferența dintre costul maxim și C . [3]

Idei principale

Algoritmul se bazează pe două idei:

dacă se scade același număr din toate elementele unui anumit rând sau coloană , costul total va scădea cu , iar soluția optimă nu se va modifica; $y$ $y$
dacă există o soluție cu cost zero, atunci este optimă.

Algoritmul caută valori care trebuie scăzute din toate elementele fiecărui rând și fiecare coloană (diferite pentru diferite rânduri și coloane), astfel încât toate elementele matricei să rămână nenegative, dar apare o soluție zero.

Definiții

Algoritmul este mai ușor de descris dacă problema este formulată folosind un graf bipartit . Având în vedere un graf bipartit complet G=(S, T; E) cu n vârfuri corespunzătoare angajaților ( S ) și n vârfuri corespunzătoare tipurilor de muncă ( T ); costul fiecărei muchii c(i, j) este nenegativ. Este necesar să găsiți o potrivire perfectă sau completă la cel mai mic cost.

Vom numi funcția potențial dacă pentru fiecare . Valoarea potențială este definită ca . Este ușor de observat că costul oricărei potriviri perfecte nu este mai mic decât valoarea oricărui potențial. Metoda maghiară găsește o potrivire deplină și un potențial cu același cost/valoare, ceea ce demonstrează că ambele cantități sunt optime. De fapt, el găsește o potrivire perfectă a muchiilor rigide : se spune că o muchie este rigidă pentru potențialul dacă . Subgraful marginii rigide va fi notat ca . Costul unei potriviri complete în (dacă există) este egal cu . $y\colon (S\cup T)\to \mathbb {R}$ $y(i)+y(j)\leq c(i,j)$ $i\în S,j\în T$ $y=\sum _{v\in S\cup T}y(v)$ $ij$ $y$ $y(i)+y(j)=c(i,j)$ ${\mathbf {G_{y))}$ ${\mathbf {G_{y))}$ $y$

Algoritm în termeni de grafice bipartite

Algoritmul stochează în memorie potențialul și orientarea (setarea direcției) fiecărei muchii rigide, care are proprietatea ca muchiile direcționate să formeze o potrivire, pe care o notăm cu . Un grafic dirijat format din muchii rigide cu o orientare dată este notat cu . Astfel, în orice moment există trei tipuri de muchii: $y\$ $T\$ $S\$ $M$ $\mathbf {{\overrightarrow {G}}_{y}}$

non-rigid (și nu aparținând ) $M\$
dur, dar nu aparținător $M\$
tare și deținută $M\$

Inițial , peste tot este 0 și toate marginile sunt direcționate de la la (astfel, goale). La fiecare pas, fie se modifică astfel încât setul de vârfuri , definit în paragraful următor, să fie mărit, fie se modifică orientarea pentru a obține o potrivire cu un număr mai mare de muchii; rămâne întotdeauna adevărat că toate marginile sunt rigide. Procesul se termină dacă este o potrivire perfectă. $y\$ $S\$ $T\$ $M\$ $y\$ $Z\$ $M\$ $M\$

Fie la fiecare pas și mulțimea de vârfuri care nu sunt incidente cu muchiile din (adică , mulțimea de vârfuri din , care nu includ nicio muchie, ci mulțimea de vârfuri din , din care nu iese nicio muchie). Indicați prin setul de vârfuri accesibile de la până la (poate fi găsit prin căutarea pe lățimea întâi ). $R_{S}\subseteq S$ $R_{T}\subseteq T$ $M\$ $R_{S}\$ $S$ $R_{T}\$ $T$ $Z\$ $R_{S}\$ $\mathbf {{\overrightarrow {G}}_{y}}$

Dacă nu este gol, înseamnă că există cel puțin o cale către de la la . Alegem oricare dintre aceste căi și schimbăm orientarea tuturor marginilor sale în sens invers. Dimensiunea potrivirii va crește cu 1. $R_{T}\cap Z$ $\mathbf {{\overrightarrow {G}}_{y}}$ $R_{S}\$ $R_{T}\$

Pentru dovadă, notăm două fapte evidente:

Pe calea aleasă, muchiile de la până alternează cu muchiile de la până la . Aceasta rezultă din graficul bipartit. $S\$ $T\$ $T\$ $S\$
Primul vârf al căii aparține lui , iar ultimul vârf aparține lui . Prin urmare, prima și ultima margine sunt direcționate de la la . $S\$ $T\$ $S\$ $T\$

Prin definiție , rezultă că pe calea aleasă se alternează muchiile aparținând și neapartinând, iar prima și ultima muchie nu aparțin lui , adică drumul este ridicător, din care rezultă afirmația care se dovedește. $\mathbf {{\overrightarrow {G}}_{y}}$ $M\$ $M\$

Dacă este gol, puneți . este pozitiv deoarece nu există margini dure între și . $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$

Într-adevăr, să existe o astfel de muchie (i, j). Deoarece , dar , vârful este accesibil de la până la , dar vârful este inaccesibil. $i\în Z$ $j\notin Z$ $eu\$ $R_{S}\$ $\mathbf {{\overrightarrow {G}}_{y}}$ $j\$

Prin urmare, nu poate conține margini (i, j). Prin urmare , de unde . Deoarece este accesibil de la până la , există o cale către de la un vârf aparținând lui . Luați în considerare ultima margine a acestei căi. Notează-l (k, i). Deoarece este accesibil de la până la , dar inaccesibil, . Din moment ce , . Prin urmare, este incident la două muchii de la : și , ceea ce este imposibil, deoarece este o potrivire. Contradicţie. $\mathbf {{\overrightarrow {G}}_{y}}$ $(i,j)\în M$ $eu\nu în R_{S}$ $eu\$ $R_{S}\$ $\mathbf {{\overrightarrow {G}}_{y}}$ $eu\$ $R_{S}\$ $k\$ $R_{S}\$ $\mathbf {{\overrightarrow {G}}_{y}}$ $j\$ $k\neq j$ $(k,i)\in \mathbf {{\overrightarrow {G}}_{y}}$ $(i,k)\în M$ $eu\$ $M\$ $(i,j)\$ $(i,k)\$ $M\$

Să creștem cu pe vârfurile de la și să scădem cu la vârfurile incluse în . Cel nou rămâne potențial. $y\$ $\Delta$ $Z\cap S$ $y\$ $\Delta$ $Z\cap T$ $y\$

Într-adevăr, pentru orice muchie (i, j), , : $i\în S$ $j\în T$

dacă , , atunci c(i, j)-y(i)-y(j) nu se modifică deoarece nici y(i) nici y(j) $eu\nu în Z$ $j\notin Z$
dacă , , atunci c(i, j)-y(i)-y(j) nu se modifică, deoarece y(i) crește cu , iar y(j) scade cu aceeași cantitate $i\în Z$ $j\în Z$ $\Delta$
dacă , , diferența c(i, j)-y(i)-y(j) crește cu , deci rămâne nenegativă $eu\nu în Z$ $j\în Z$ $\Delta$
dacă , , diferența c(i, j)-y(i)-y(j) scade cu , dar rămâne totuși nenegativă, deoarece este cea mai mică dintre aceste diferențe. $i\în Z$ $j\notin Z$ $\Delta$ $\Delta$

Graficul se modifică, dar, în ciuda acestui fapt, conține . $\mathbf {{\overrightarrow {G}}_{y}}$ $M\$

Într-adevăr, pentru a exclude de la o muchie (i, j), , , este necesar să o facem nerigidă, adică să mărim diferența c(i, j)-y(i)-y(j) . După cum am văzut, diferența crește numai dacă , , cu alte cuvinte, este de neatins de la , dar este realizabilă. Dar în acest caz, muchia (j, i) nu poate aparține lui , prin urmare, muchia nu aparține lui . $\mathbf {{\overrightarrow {G}}_{y}}$ $i\în S$ $j\în T$ $eu\nu în Z$ $j\în Z$ $i$ $R_{S}$ $j$ $\mathbf {{\overrightarrow {G}}_{y}}$ $M$

Orientați noile margini de la la . Prin definiție , setul de vârfuri accesibile de la va crește (și numărul de muchii rigide nu crește neapărat). $S\$ $T\$ $\Delta$ $Z\$ $R_{S}$

Pentru a demonstra această afirmație, demonstrăm mai întâi că niciun vârf nu dispare din Z. Fie . Apoi există o cale de la un vârf care aparține de la V la V. Toate vârfurile de pe această cale sunt accesibile de la , adică aparțin lui Z. Fiecare muchie de pe această cale este incidentă cu două vârfuri de la Z. După cum am văzut mai sus, pentru astfel de muchii diferența c(i, j )-y(i)-y(j) nu se modifică. Aceasta înseamnă că toate marginile căii vor rămâne rigide, iar V va fi încă accesibil din . Acum să demonstrăm că la Z i se adaugă cel puțin un vârf. Luați în considerare muchia la care este atins minimul . Pentru această muchie, diferența c(i, j)-y(i)-y(j) va fi zero, prin urmare, va deveni rigidă și va fi direcționată de la S la T, adică de la i la j. Deoarece , j va deveni accesibil și de la , adică va fi adăugat la Z. $V\în Z$ $R_{S}$ $R_{S}$ $R_{S}$ $\min\{c(i,j)-y(i)-y(j):i\in Z\cap S,j\in T\setminus Z\}$ $i\în Z$ $R_{S}$

Repetăm acești pași până când devine o potrivire perfectă; în acest caz, dă misiunea cu cel mai mic cost. Timpul de execuție al acestei versiuni a algoritmului este : se adaugă o dată, iar în stadiul în care nu se modifică, nu mai pot exista modificări potențiale (deoarece crește de fiecare dată). Timpul necesar pentru schimbarea potențialului este de . $M\$ $O(n^{4})$ $M\$ $n\$ $M\$ $n\$ $Z\$ $O(n^{2})$

Interpretarea matricei

Pentru lucrători și locuri de muncă, având în vedere o matrice n × n care specifică costul fiecărui loc de muncă pentru fiecare lucrător. Găsiți costul minim pentru a face o muncă astfel încât fiecare muncitor să facă exact o muncă și fiecare muncă să fie făcută de exact un muncitor. $n$

În cele ce urmează, prin atribuire înțelegem corespondența dintre muncitori și locuri de muncă, care are cost zero după ce am făcut transformări care afectează doar costul total al locurilor de muncă.

Mai întâi de toate, să scriem problema sub formă de matrice:

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

unde a, b, c, d sunt lucrători care trebuie să îndeplinească locurile de muncă 1, 2, 3, 4. Coeficienții a1, a2, a3, a4 denotă costul îndeplinirii locurilor de muncă 1, 2, 3, 4 de către angajat „a”, respectiv. Alte simboluri au o semnificație similară. Matricea este pătrată, astfel încât fiecare muncitor poate face o singură lucrare.

Pasul 1

Reducem elementele linie cu linie. Găsim cel mai mic dintre elementele primului rând (a1, a2, a3, a4) și îl scădem din toate elementele primului rând. În acest caz, cel puțin unul dintre elementele primului rând va fi setat la zero. Facem același lucru pentru toate celelalte linii. Acum fiecare rând al matricei are cel puțin un zero. Uneori, zerourile sunt deja suficiente pentru a găsi destinația. Un exemplu este prezentat în tabel. Zerourile roșii indică locurile de muncă alocate.

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

Cu un număr mare de zerouri, pentru a găsi destinația (cost zero), puteți utiliza un algoritm pentru a găsi potrivirea maximă a graficelor bipartite, de exemplu, algoritmul Hopcroft-Karp . De asemenea, dacă cel puțin o coloană nu are elemente nule, atunci alocarea nu este posibilă.

Pasul 2

Adesea, nu există nicio atribuire în primul pas, ca în următorul caz:

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

Sarcina 1 poate fi realizată eficient (la cost zero) atât de către lucrătorul a, cât și de către lucrătorul c, dar sarcina 3 nu poate fi realizată eficient de către nimeni.

În astfel de cazuri, repetăm pasul 1 pentru coloane și verificăm din nou dacă atribuirea este posibilă.

Pasul 3

În multe cazuri, vom obține rezultatul dorit după pasul 2. Dar uneori nu este cazul, de exemplu:

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

Dacă lucrătorul d face treaba 2, nu există nimeni care să facă treaba 3 și invers.

În astfel de cazuri, vom urma procedura descrisă mai jos.

În primul rând, folosind orice algoritm pentru găsirea potrivirii maxime într-un grafic bipartit, atribuim cât mai multe locuri de muncă posibil acelor lucrători care le pot efectua la cost zero. Un exemplu este prezentat în tabel, joburile alocate sunt evidențiate cu roșu.

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

Notați toate rândurile fără atribuiri (linia 1). Notați toate coloanele cu zerouri din aceste rânduri (coloana 1). Notați toate rândurile cu zerouri „roșii” în aceste coloane (linia 3). Continuăm până când rândurile și coloanele noi nu mai sunt marcate.

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

Acum trasăm linii prin toate coloanele marcate și rândurile nemarcate .

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

Toate aceste acțiuni au urmărit un singur scop: să traseze cel mai mic număr de linii (verticale și orizontale) astfel încât să acopere toate zerourile. Puteți folosi orice altă metodă în locul celei descrise.

Pasul 4

Dintre elementele matricei care nu sunt acoperite de linii (în acest caz, acestea sunt a2', a3', a4', c2', c3', c4'), găsiţi cel mai mic. Scădeți-l din toate rândurile nemarcate și adăugați-l la toate intersecțiile rândurilor și coloanelor marcate. Deci, de exemplu, dacă cel mai mic element din listat este a2', obținem

×
0	0	a3'-a2'	a4'-a2'	×
b1'+a2'	b2'	b3'	0
0	c2'-a2'	c3'-a2'	c4'-а2'	×
d1'+a2'	0	0	d4'

Repetați procedura (pașii 1-4) până când numirea este posibilă.

Bibliografie

R. E. Burkard, M. Dell'Amico, S. Martello: Probleme de atribuire . SIAM, Philadelphia (PA.) 2009. ISBN 978-0-89871-663-4
Harold W. Kuhn, „The Hungarian Method for the assignment problem”, Naval Research Logistics Quarterly , 2 :83-97, 1955. Publicația originală a lui Kuhn.
Harold W. Kuhn, „Variants of the Hungarian method for assignment problems”, Naval Research Logistics Quarterly , 3 : 253-258, 1956.
J. Munkres, „Algoritmi pentru problemele de atribuire și transport”, Jurnalul Societății de Matematică Industrială și Aplicată , 5 (1):32-38, martie 1957.
M. Fischetti, Lezioni di Ricerca Operativa, Edizioni Libreria Progetto Padova, Italia, 1995.
R. Ahuja, T. Magnanti, J. Orlin, Network Flows, Prentice Hall, 1993.

Note

↑ Jacobi C. De investigando ordine systematis aequationum differentialum vulgarium cujuscunque, CGJ Jacobi's gesammelte Werke, fünfter Band, herausgegeben von K. Weierstrass. - 1890.
↑ (link indisponibil) politechnique.fr Arhivat 29 ianuarie 2020 la Wayback Machine
↑ Copie arhivată (link nu este disponibil) . Consultat la 11 februarie 2010. Arhivat din original pe 19 iulie 2011. (nedefinit)