Un ufficio ha cinque tecnici e cinque interventi da fare oggi. Non tutti i tecnici sanno fare tutto: chi ha la certificazione per gli impianti elettrici, chi conosce un certo software, chi può guidare il furgone. Quanti interventi si possono coprire, al massimo, assegnando a ciascun tecnico un solo intervento? E se ogni coppia tecnico-intervento avesse un costo, per esempio il tempo di trasferimento, quale assegnazione minimizzerebbe il totale?
Sono due problemi classici: il matching massimo in un grafo bipartito e il problema dell'assegnamento.
Il modello
Si costruisce un grafo bipartito: da un lato i tecnici, dall'altro gli interventi, con un arco tra tecnico e intervento quando l'abbinamento è possibile. Un matching (o abbinamento) è un insieme di archi senza estremi in comune: ogni tecnico e ogni intervento compare al massimo una volta. Un matching è:
- massimale se non si può aggiungere nessun arco;
- massimo se ha il numero più alto possibile di archi;
- perfetto se copre tutti i vertici.
Attenzione alla differenza tra massimale e massimo. Un approccio avido, che abbina ogni tecnico al primo intervento libero, produce un matching massimale, che però può essere molto più piccolo del massimo. Se Anna prende l'unico intervento che sapeva fare anche Bruno, e Bruno non sa fare altro, la scelta avida lascia Bruno senza lavoro anche se esisteva una soluzione migliore.
Cammini aumentanti
Dato un matching, un cammino alternante usa alternativamente archi fuori e dentro il matching. Se un cammino alternante parte e finisce in vertici liberi, si chiama cammino aumentante: scambiando gli archi lungo il cammino (quelli fuori entrano, quelli dentro escono) il matching cresce di uno.
Il teorema di Berge dice che un matching è massimo se e solo se non ammette cammini aumentanti. L'algoritmo base è quindi: finché trovi un cammino aumentante, usalo.
def matching_massimo(adj, n_sinistra, n_destra):
abbinato_a = [-1] * n_destra
def prova(u, visti):
for v in adj[u]:
if v in visti:
continue
visti.add(v)
if abbinato_a[v] == -1 or prova(abbinato_a[v], visti):
abbinato_a[v] = u
return True
return False
return sum(prova(u, set()) for u in range(n_sinistra))
La funzione prova cerca di sistemare il tecnico u: se l'intervento v è libero lo prende; se è occupato, chiede ricorsivamente al suo attuale tecnico di spostarsi su un altro intervento. Il costo è proporzionale a n · m. L'algoritmo di Hopcroft-Karp, che cerca molti cammini aumentanti disgiunti contemporaneamente, scende a circa m · √n.
Lo stesso risultato si ottiene con il flusso massimo: si collega una sorgente a tutti i tecnici e tutti gli interventi a un pozzo, con capacità 1 ovunque. Il flusso massimo intero corrisponde al matching massimo.
Il teorema di König
Nei grafi bipartiti vale un'uguaglianza utile: la dimensione del matching massimo è uguale alla dimensione della copertura minima dei vertici, cioè il più piccolo insieme di vertici che tocca tutti gli archi. In termini pratici: se il matching massimo è 4, esiste un gruppo di 4 persone o compiti che «spiega» perché non si può fare di meglio. Questo insieme si ricava dall'ultimo tentativo fallito di trovare cammini aumentanti, ed è un ottimo strumento per mostrare a chi pianifica dove sta il vincolo.
L'assegnamento pesato
Se ogni coppia tecnico-intervento ha un costo e si vuole un matching perfetto di costo totale minimo, si ha il problema dell'assegnamento. Provare tutte le combinazioni è impossibile già per dimensioni modeste: con 10 tecnici le assegnazioni possibili sono 10!, cioè 3.628.800, e con 20 sono oltre due miliardi di miliardi.
Il metodo ungherese, presentato da Harold Kuhn nel 1955, risolve il problema in tempo polinomiale, nella versione efficiente proporzionale a n³. Lavora sulla matrice dei costi con un'idea semplice: sottrarre una costante da una riga o da una colonna non cambia quale assegnazione sia ottima, perché ogni assegnazione usa esattamente un elemento per riga e per colonna.
I passi essenziali, nella versione a matrice:
- sottrai a ogni riga il suo minimo;
- sottrai a ogni colonna il suo minimo;
- cerca un'assegnazione che usi solo celle a costo zero;
- se non esiste, copri tutti gli zeri con il minimo numero di righe e colonne, sottrai il minimo valore scoperto dalle celle non coperte, aggiungilo alle celle coperte due volte e torna al passo 3.
| Intervento 1 | Intervento 2 | Intervento 3 | |
|---|---|---|---|
| Anna | 4 | 2 | 8 |
| Bruno | 4 | 3 | 7 |
| Carla | 3 | 1 | 6 |
Dopo la riduzione per righe e colonne si trova, per esempio, Anna → 2, Bruno → 3, Carla → 1, con costo 2 + 7 + 3 = 12. In questo caso esistono altre assegnazioni con lo stesso costo minimo, come Anna → 1, Bruno → 3, Carla → 2: il metodo ne restituisce una.
Casi pratici
- Turni e personale: chi copre quale turno, rispettando competenze e preferenze espresse come costi.
- Logistica: quale veicolo va a quale cliente per minimizzare i chilometri a vuoto.
- Tracciamento: nei sistemi di visione, abbinare gli oggetti rilevati in un fotogramma a quelli del fotogramma precedente minimizzando gli spostamenti.
- Revisione di documenti: assegnare revisori a pratiche evitando conflitti di interesse, che si modellano semplicemente togliendo gli archi vietati.
In sintesi
- Un matching abbina elementi di due gruppi senza usare due volte lo stesso elemento.
- Le scelte avide danno matching massimali ma non sempre massimi.
- I cammini aumentanti, o una riduzione a flusso massimo, trovano il matching massimo.
- Il teorema di König collega il matching massimo alla copertura minima dei vertici.
- Il metodo ungherese risolve l'assegnamento a costo minimo in tempo n³.
