Glossario · approach
Algoritmo Ungherese
Algoritmo combinatorio che risolve il problema di assegnazione (matrice di costo n×n, matching uno-a-uno di costo minimo) in tempo polinomiale O(n³); Kuhn (1955) e Munkres (1957).
Hungarian MethodHungarian AlgorithmAlgoritmo di Kuhn-Munkres
L'algoritmo ungherese (detto anche algoritmo di Kuhn-Munkres) è l'algoritmo di ottimizzazione combinatoria che risolve il problema di assegnazione — matching uno-a-uno di n lavoratori/risorse a n compiti con matrice di costo n×n, minimizzando il costo totale — in tempo polinomiale O(n³). Harold Kuhn presentò l'algoritmo nel suo articolo del 1955 sul *Naval Research Logistics Quarterly*; il nome è stato attribuito in onore dei teoremi di matching bipartito sviluppati ai primi del Novecento dai matematici ungheresi Dénes König e Jenő Egerváry. James Munkres trasformò l'algoritmo nel 1957 in una procedura polinomiale O(n³) pienamente formale, da cui la denominazione alternativa moderna di algoritmo di Kuhn-Munkres. Funzionamento: sottrai i minimi di riga/colonna (riduzione), trova un matching massimo sulle celle a costo zero col teorema di König-Egerváry, se non è perfetto applica una procedura sequenziale di copertura per aggiornare la matrice, ripeti fino al matching perfetto. Ottimo garantito, tempo polinomiale, combinatorio. Alternative moderne più veloci: LAP — shortest augmenting path (Jonker e Volgenant 1987, 5-20× più veloce in pratica); auction algorithm (Bertsekas 1988, parallelizzabile). Kuhn (1955), Munkres (1957).
Örnek
Data una matrice di costo 5×5 in cui ciascun tecnico ha tempi di viaggio diversi verso ciascun cliente, l'algoritmo ungherese trova in pochi secondi il matching uno-a-uno che minimizza il tempo totale; 15-30% migliore dell'assegnazione intuitiva.