Algoritmi golosi

Hieronymus Bosch, Sette peccati capitali, Gola

Nel sesto canto dell'Inferno, Dante incontra i golosi, flagellati da una piova etterna, maladetta, fredda e greve. 
La pioggia cade incessante, con intensità sempre uguale, mista a neve e grandine, e il fango che si forma al suolo è maleodorante.

Forse anche un ipotetico inferno degli informatici avrebbe un girone dei golosi: ma in questo caso a essere puniti non sarebbero gli ingordi di cibi e bevande, ma i progettisti di algoritmi che non si sono saputi trattenere dall'utilizzo di metodologie "golose", o "greedy".

Un algoritmo goloso è un metodo per risolvere un problema attraverso una serie di passi, ciascuno dei quali mira a espandere la soluzione parziale fino a quel momento costruita, con lo scopo di arrivare infine a una soluzione completa: a ogni passo, l'algoritmo goloso compie la propria scelta in modo "ingordo", perseguendo cioè il massimo guadagno possibile, senza ovviamente violare le regole del problema.

Vediamo un esempio. Supponiamo di avere una macchina distributrice di bevande in grado di dare il resto. Ogni volta che la macchinetta deve dare il resto, deve prendere decisioni inerenti a quali monete utilizzare per arrivare alla somma da restituire. L'obiettivo è quello di utilizzare ogni volta il numero più basso possibile di monete. Immaginiamo, per semplicità, che la macchina disponga sempre di quantità infinite di monete da 1 euro, 10 cent e 1 cent.
Un algoritmo goloso, in questo caso, potrebbe funzionare a ogni passo come segue:
1. calcola quanto manca al raggiungimento della somma da restituire;
2. seleziona, tra le monete con valore minore della somma che manca, quella con valore più alto;
3. emetti una moneta del tipo selezionato.
Se, per esempio, deve essere erogato un resto di 1,12 euro, la macchina sceglierà, al primo passo, di consegnare una moneta da 1 euro. Al secondo passo, dato che mancano 12 cent, la macchina selezionerà una moneta da 10 cent. Gli ultimi due passi comporteranno entrambi l'emissione di una moneta da 1 cent.
Tutto bene, direte voi. Anche noi, dovendo pagare 1,12 euro e disponendo di questi tagli, avremmo scelto questa combinazione. Sì, però abbiamo visto un caso fortunato, in cui l'algoritmo goloso perviene a una soluzione completa soddisfacente.
Cosa accadrebbe se invece di monete da 1 euro, 10 cent e 1 cent, la macchina disponesse di monete da 1 cent, 15 cent e 25 cent, e dovesse consegnare un resto di 30 cent? Per colpa del suo modo di pensare ingordo, sceglierebbe di erogare dapprima una moneta da 25 euro, e poi sarebbe costretta a snocciolare una dopo l'altra cinque monete da 1 cent. Si tratta della soluzione migliore? No, perché fa uso di ben sei monete, quando due monete da 15 cent avrebbero risolto il problema molto più brillantemente.
E non ditemi che le monete da 15 e da 25 cent non esistono: non è questo il punto.
Gli algoritmi golosi, in generale, non garantiscono il successo nel trovare la soluzione ottima di un problema. Anzi, possiamo dire che il  più delle volte falliscono miseramente.

Un altro esempio? Immaginate che quattro uomini, Aldo, Bernardo, Carlo e Damiano, equipaggiati con una torcia, debbano attraversare di notte un ponte pericolante. Non più di due persone alla volta possono passare sul ponte, e ogni uomo o coppia che si avventura deve avere con sè la torcia. La torcia, inoltre, deve essere portata avanti e indietro, e non può essere lanciata da un capo all'altro del ponte. Aldo impiega 1 minuto ad attraversare il ponte, Bernardo ci mette 2 minuti, Carlo 5 minuti, e Damiano 10 minuti. Una coppia impiegherà il tempo imposto dall'attraversatore più lento.
Qual è, per i quattro uomini, il modo più veloce di attraversare il ponte?

Se gli uomini decidono di risolvere il problema adottando un approccio greedy, saranno inviate al di là del ponte le due persone più veloci, cioè Aldo e Bernardo, che impiegheranno 2 minuti. Il più veloce dei due, cioè Aldo, tornerà con la torcia in un minuto. Di nuovo partiranno i due uomini più veloci disponibili, cioè Aldo e Carlo, che arriveranno al di là del ponte in 5 minuti. Tornerà di nuovo Aldo con la torcia, impiegando 1 minuto. Infine sarà la volta di Aldo e Damiano, che giungeranno a destinazione in 10 minuti. Il tempo complessivo sarà quindi di 19 minuti.
Secondo voi è il modo più veloce di attraversare il ponte, cioè è la soluzione ottimale del problema? Provate a investigare: scoprirete che non lo è: esiste una soluzione migliore, e quindi la "golosità algoritmica" ha messo a grave rischio i quattro uomini (ricordate che il ponte era pericolante, e ogni minuto risparmiato era prezioso).

Non si devono confondere gli algoritmi greedy con gli algoritmi di discesa: è vero che anche in questo secondo caso si tratta di procedure che, a ogni passo, scelgono la via che appare più conveniente, senza guardare alla globalità del problema, ma i due scenari sono molto diversi.
Il "passo" di un algoritmo greedy serve a espandere la soluzione fino a quel momento costruita: aggiunge, per così dire, un mattone al muro in costruzione, ma il muro completo, che può essere definito una soluzione, sarà pronto soltanto alla fine dell'algoritmo.
Nel problema del resto, ogni passo corrisponde a una delle monete erogate. Nel problema del ponte, ogni passo è un attraversamento.
Gli algoritmi di discesa, invece, costruiscono a ogni passo una soluzione completa, e cercano di migliorarla costruendone un'altra che differisce dalla precedente per qualche particolare. In questa transizione effettuano una scelta che, in un certo senso, è miope, cioè cerca di massimizzare un qualche "profitto". Anche in questo tipo di metodologia la scarsa lungimiranza può portare su strade poco promettenti, è vero: ma in generale si tratta di un approccio molto importante nella risoluzione dei problemi di ottimizzazione, che con alcune correzioni e accorgimenti particolari può condurre a risultati interessanti. Nel vecchio post Mosse tabu avevo accennato a una di queste importanti correzioni.