Algoritmo ungherese

In matematica, il metodo ungherese, o algoritmo ungherese, è un metodo di ottimizzazione combinatoria che risolve in tempo polinomiale il problema dell'assegnamento. Il metodo è stato sviluppato da Harold Kuhn nel 1955, anticipando i successivi metodi primali-duali, ed è chiamato "ungherese" in quanto basato su lavori di Dénes König e Jenő Egerváry. Nel 2006 fu scoperto un lavoro di Carl Jacobi, risalente al XIX secolo, che risolve il medesimo problema. La complessità dell'algoritmo era di $O(n^{4})$, ma si è dimostrato che modificando leggermente l'algoritmo si può arrivare ad ottenere una complessità computazionale pari a $O(n^{3})$.

Definizione del problema

Il problema dell'assegnamento richiede di associare coppie di elementi presi da due insiemi differenti. Tenendo conto che a ogni coppia è associato un costo, si vuole minimizzare il costo totale. Ad esempio: considerando un insieme di impiegati, un insieme di compiti da svolgere e il tempo che ciascun compito richiederebbe se svolto da uno specifico impiegato, si vuole associare ogni impiegato a un compito in modo da minimizzare il tempo totale richiesto.

Formalmente, data una matrice $n\times n$ di costi $C=(c_{ij})$, vogliamo trovare una permutazione $\phi$ di $\{1,\dots ,n\}$ che minimizzi $\sum _{i=1}^{n}c_{i\phi (i)}$.

Algoritmo

Il problema è codificato tramite un grafo bipartito, in cui i vertici sono gli elementi da associare e gli archi rappresentano le possibili scelte di coppie. A ogni arco è associato un costo. Formalmente, si considera il grafo $G=(U,V;E)$ dove U e V sono i due insiemi di elementi da associare ed E è l'insieme degli archi.

L'algoritmo inizia da una qualsiasi possibile soluzione, anche parziale, del problema e cerca di migliorarla verificando la presenza di elementi non assegnati.

A ogni iterazione, l'algoritmo tenta di trovare un percorso che aumenti il numero di elementi presenti nella soluzione. La prima iterazione inizia da un elemento di $u\in U$ non assegnato. Vi sono due possibilità:

1. vi è un arco che collega l'elemento u a un elemento $v\in V$ non facente parte della soluzione
2. vi sono solo archi che collegano l'elemento u ad elementi di V già assegnati

Nel primo caso, l'assegnamento tra u e v è aggiunto alla soluzione.

Interpretazione matriciale dell'algoritmo

Data una matrice quadrata di ordine $n$ rappresentante la matrice dei costi del problema di assegnamento, l'algoritmo si svolge come segue

1. Per ogni riga, individuare il minimo e sottrarlo a tutti gli elementi della riga;
2. Per ogni colonna, individuare il minimo e sottrarlo a tutti gli elementi della colonna;
3. Coprire con il minor numero di linee tutti gli zeri che si sono formati con le precedenti sottrazioni;
4. Se il numero minimo di linee necessarie è pari a $n$ è possibile determinare un assegnamento ottimo altrimenti procedere con lo step 5;
5. Individuare il minimo tra gli elementi non coperti da linee, sottrarlo agli elementi non coperti e sommarlo agli elementi che sono incrocio di due linee. Tornare allo step 3.

Per determinare il minor numero di linee necessarie per coprire tutti gli zeri formati (step 3) si può utilizzare il seguente algoritmo:

1. Determinare un assegnamento (anche incompleto, ovvero un assegnamento in cui può esistere qualche riga non assegnata a nessuna colonna);
2. Marcare le righe non assegnate;
3. Per ogni riga marcata non ancora esaminata, marcare le colonne che presentano uno zero su tale riga;
4. Per ogni colonna non marcata, marcare le righe che presentano un assegnamento su tali colonne;
5. Ripetere dallo step 3 fino ad esaurimento delle righe marcate non ancora visitate;
6. Il numero minimo di linee si ottiene selezionando le colonne marcate e le righe non marcate.

Esempio

Data la seguente matrice dei costi

$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}}$

I minimi di riga sono (dall'alto in basso): 9, 3, 13, 4, 10. Sottraendoli dalle rispettive righe si ottiene la seguente 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}}$

I minimi di colonna sono (da sinistra a destra): 0, 0, 0, 6, 0. Sottraendoli dalle rispettive colonne si ottiene:

$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}}$

Si determina un assegnamento (incompleto) scorrendo le righe e assegnandole alla prima colonna possibile. Ovvero si determina il seguente assegnamento (in grassetto gli elementi assegnati):

$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}}$

Si procede ora con la determinazione del numero minimo di linee per coprire gli elementi nulli della matrice. Viene marcata la riga 3 che non è assegnata. Tale riga presenta uno zero nella colonna 3 (che viene marcata). Tale colonna presenta un assegnamento alla riga 1 (che viene marcata). Viene esaminata ora la riga 1 (che è stata marcata nella precedente iterazione. Tale riga presenta uno zero nella colonna 3 che è già marcata. Non ci sono altre colonne marcate non esaminate e righe marcate non esaminate. Il numero minimo di linee è dato dalle colonne marcate (colonna 3) e righe non marcate (righe 2, 4, 5). Sono necessarie quindi $4<5=n$ linee. Non è possibile determinare un assegnamento completo e si procede con lo step 5.

Si determina il minimo tra gli elementi non coperti da linee, cioè il minimo della seguente matrice ottenuta eliminando gli elementi coperti da linee:

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

che è 9. Questo valore va sottratto agli elementi non coperti da linee e sommati agli elementi incrocio di due linee. Cioè si ottiene:

$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}}$

Si determina ora un assegnamento (eventualmente incompleto) scorrendo le righe ed assegnando la prima colonna possibile. Si ottiene

$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}}$

Tutte le righe sono assegnate, quindi nessuna riga è marcata. Le linee necessarie per coprire tutti gli elementi nulli è dato dalle colonne marcate (nessuna) e le righe non marcate (tutte) e sono $5=n$ è quindi possibile assegnare tutte le righe e l'assegnamento è dato da $A_{2}$.

Bibliografia

• (LA) Jacobi, C.G.J. e Borchardt, C.W., De investigando ordine systematis aequationum differentialium vulgarium cujuscunque, in Crelle's Journal, vol. 64, 1865, pp. 297-320. URL consultato il 19 novembre 2013.
• (DE) Dénes König, Theorie der endlichen und unendlichen graphen, Leipzig, Akademische Verlagsgesellschaft M.B.H., 1936.
• (HU) Egerváry, Jenő, Matrixok kombinatorius tulajdonságairól, in Matematikai és Fizikai Lapok, vol. 38, 1931, pp. 16-28.
  • tradotto in (EN) Kuhn, Harold W., On combinatorial properties of matrices, in Logistics Papers, vol. 11, n. 4, 1955, pp. 1-11.
• (EN) Kuhn, H.W., The Hungarian method for the assignment problem, in Naval Res. Log. Quart., vol. 2, 1955, pp. 83-97.
• (EN) Kuhn, H.W., Variants of the Hungarian method for the assignment problem, in Naval Res. Log. Quart., vol. 3, 1956, pp. 253-258.
• (EN) G.B. Dantzig, L.R. Ford e D.R. Fulkerson, A primal-dual algorithm for linear programs, in H.W Kuhn, AW. Tucker (a cura di), Linear inequalities and related systems, Princeton, Princeton University Press, 1956, pp. 171-181.
• (EN) H.W. Kuhn, On the origin of the Hungarian method for the assignment problem, in J.K. Lenstra, A.H.G. Rinnooy Kan, A. Schrijver (a cura di), History of Mathematical Programming, Amsterdam, North-Holland, 1991, pp. 77-81, ISBN 0-444-88818-7.
• (EN) Rainer Burkard, Mauro Dell'Amico e Silvano Martello, Linear sum assignment problem (PDF), in 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: from the origins of the Hungarian algorithm to satellite communication", Central European Journal of Operations Research 18, 47–58, 2010