Un algoritmo greedy (avido) costruisce la soluzione un pezzo alla volta e, a ogni passo, prende la scelta che sembra migliore in quel momento, senza mai tornare indietro. È l'approccio più naturale e spesso il più veloce. Il problema è che «sembra migliore adesso» non significa «porta all'ottimo alla fine». A volte funziona perfettamente, a volte sbaglia in modo clamoroso. Saper distinguere i due casi è una delle competenze più utili nella progettazione di algoritmi.
Un caso in cui funziona: la selezione di intervalli
Una sala riunioni riceve molte richieste di prenotazione, ciascuna con orario di inizio e di fine. Si vuole accettare il massimo numero di riunioni senza sovrapposizioni.
Tre strategie avide sembrano ragionevoli:
- scegliere prima la riunione che inizia per prima;
- scegliere prima la riunione più breve;
- scegliere prima la riunione che finisce per prima.
Solo la terza è sempre ottima. Le prime due falliscono con controesempi semplici: una riunione che inizia alle 8 e finisce alle 18 blocca la strategia 1; una riunione breve dalle 11:30 alle 12:30, posta a cavallo tra due riunioni 9–12 e 12–15, blocca la strategia 2, che accetta una sola riunione invece di due.
def seleziona(riunioni):
scelte, fine_ultima = [], float("-inf")
for inizio, fine in sorted(riunioni, key=lambda r: r[1]):
if inizio >= fine_ultima:
scelte.append((inizio, fine))
fine_ultima = fine
return scelte
Il costo è dominato dall'ordinamento: n log n.
Come si dimostra che una scelta avida è giusta
Il metodo più usato è l'argomento di scambio. Si prende una soluzione ottima qualsiasi e si mostra che la si può modificare, senza peggiorarla, fino a farla coincidere con quella avida.
Per gli intervalli: sia O una soluzione ottima e sia g la riunione che finisce per prima in assoluto. Se O non contiene g, si sostituisce la prima riunione di O con g. Poiché g finisce non dopo di essa, non crea sovrapposizioni con le altre riunioni di O, e il numero di riunioni resta lo stesso. Quindi esiste una soluzione ottima che contiene la scelta avida, e lo stesso ragionamento si ripete sul resto.
Due proprietà, insieme, garantiscono il successo:
- proprietà della scelta avida: esiste sempre una soluzione ottima che contiene la prima scelta avida;
- sottostruttura ottima: dopo quella scelta, ciò che resta è un problema dello stesso tipo, più piccolo.
Altri greedy corretti
- Alberi ricoprenti minimi: Kruskal e Prim sono greedy; la loro correttezza deriva dalla proprietà del taglio.
- Dijkstra: a ogni passo rende definitivo il vertice più vicino; è un greedy, e funziona solo con pesi non negativi.
- Codici di Huffman: per comprimere un testo si assegnano codici binari più corti ai simboli più frequenti. L'algoritmo fonde ripetutamente i due simboli (o gruppi) meno frequenti in un nuovo nodo. Il risultato è un codice prefisso di lunghezza media minima, usato ancora oggi all'interno di formati di compressione diffusi.
- Zaino frazionario: prendere gli oggetti in ordine di valore per unità di peso è ottimo, se si possono frazionare.
- Minimizzare il ritardo massimo: con lavori che hanno durata e scadenza, eseguirli in ordine di scadenza crescente minimizza il ritardo massimo. Anche qui la prova è un argomento di scambio: due lavori consecutivi in ordine sbagliato si possono invertire senza peggiorare.
Casi in cui fallisce
| Problema | Scelta avida | Perché fallisce |
|---|---|---|
| Zaino 0/1 | Valore per chilo più alto | Può lasciare capacità inutilizzata che un'altra combinazione sfrutterebbe |
| Resto con tagli arbitrari | Moneta più grande | Con tagli 1, 3, 4 e resto 6 dà 4 + 1 + 1 invece di 3 + 3 |
| Commesso viaggiatore | Città più vicina | Gli ultimi spostamenti possono essere lunghissimi |
| Cammini con pesi negativi | Vertice più vicino (Dijkstra) | Un arco negativo successivo cambia le distanze già fissate |
Interessante il caso delle monete: con i tagli dell'euro la strategia avida dà sempre il numero minimo di monete, perché il sistema è costruito apposta. Con tagli arbitrari no. La stessa regola, quindi, può essere ottima o sbagliata a seconda dei dati.
Greedy come euristica
Anche quando non è ottimo, un algoritmo avido è prezioso:
- fornisce in fretta una soluzione iniziale da migliorare con ricerca locale;
- dà un incumbent al branch and bound, aumentando la potatura;
- in alcuni problemi ha una garanzia di approssimazione: per la copertura di insiemi, la scelta ripetuta dell'insieme che copre più elementi nuovi produce una soluzione al massimo un fattore logaritmico peggiore dell'ottimo.
Nella pratica professionale il percorso tipico è proprio questo: prima un greedy semplice, per avere un risultato e capire il problema; poi la verifica se esiste un argomento di scambio; se non esiste, una tecnica più potente come la programmazione dinamica o una metaeuristica.
In sintesi
- Un greedy sceglie a ogni passo l'opzione migliore del momento e non torna mai indietro.
- Nella selezione di intervalli funziona solo il criterio «finisce per prima».
- L'argomento di scambio è il modo standard per dimostrare che una scelta avida è ottima.
- MST, Dijkstra, Huffman e zaino frazionario sono greedy corretti; zaino 0/1 e commesso viaggiatore no.
- Anche quando non è ottimo, un greedy fornisce soluzioni iniziali e talvolta garanzie di approssimazione.
