Nell'informatica ci sono alcuni problemi che sembrano prenderti per il culo e darti continuamente fastidio: il pozzo senza fondo da trattamento sanitario obbligatorio di una ricorrenza complessa, un algoritmo parallelo incasinato, qualunque cosa che sembra non quadrare, in genere. Il sale sulla ferita è che di solito il problema più grosso in questo tipo di enigmi è un cervello nuclearizzato dai ragionamenti, ed è uno di quei problemi difficile da risolvere. Quest'è, la risposta esiste, è davanti a te e ti restituirà una soluzione corretta in maniera semplice ed efficace—ma forse non la soluzione più corretta. Un altro algoritmo può fare meglio, e quell'algoritmo è un inferno.
Pubblicità
Per capirlo, e per capire perché tutto ciò è interessante nonché parecchio importante, dobbiamo prima capire uno dei problemi più fondamentali dell'informatica: il problema dello zaino. È abbastanza semplice da spiegare e ci sono buone probabilità che tu lo abbia già incontrato nella vita di tutti i giorni. Funziona così. Ti viene dato un contenitore (uno zaino, o qualunque altra cosa) e quel contenitore ha una certa capienza. L'obiettivo è di rimepire lo zaino con una serie di oggetti dal valore totale più alto possibile rimanendo comunque all'interno dei limiti di capienza dello zaino.Come puoi includere nello zaino gli oggetti di maggior valore senza che diventi troppo pesante? È abbastanza semplice risolvere un problema del genere, come quello sotto, semplicemente riflettendoci, ma il problema diventa sempre più difficile non appena vengono aggiunti più oggetti e la capacità del contenitore aumenta. A un certo punto diventa incredibilmente difficile, quasi impossibile. Il problema è definito NP-hard, ciò significa che non esiste un algoritmo capace di risolverlo in maniera corretta e veloce in ogni situazione possibile.
(Un problema "veloce" può essere completato, nei casi peggiori, in tempi polinomici, ciò significa che dato un numero n di input, non servirà più tempo di nk, dove k è una costante qualsiasi.)
Il problema dello zaino è di solito considerato come un problema di gestione risorse e questo è il perché lo vediamo applicato più o meno ovunque nel mondo. Come puoi spendere il tuo stipendio per ottenere il maggior valore (o utilità) dai tuoi guadagni? Qual è il numero minore di aeroplani che possono essere utilizzati per fornire il servizio in una serie di tratte? Quante persone dalle differenti abilità e corrispondenti salari possono essere assunte nel tuo dipartimento per fare il maggior lavoro al minor costo? Si tratta del tessuto fondamentale di qualunque entità organizzativa.
Gli algoritmi che utilizzi per risolvere questi problemi sono molto probabilmente scadenti—tirano a indovinare, vero? Tirare a indovinare è una tattica funzionante la maggior parte delle volte (perlomeno nascondono in maniera efficace i loro fallimenti), ma, in altri casi, c'è una legione di laureandi in informatica là fuori pronta a ottimizzare l'efficienza del tuo zaino.
È qui che ci becchiamo quelle prese per il culo algoritmiche di cui parlavo prima. Il problema dello zaino è semplice, volendo anche molto semplice se risolto sfruttando algoritmi conosciuti come greedy algorithms. "Il loro nome è piuttosto eloquente: fai ciò che sembra la scelta migliore in un dato momento, e ripetila fino a quando non smette di essere la scelta migliore o vieni obbligato a smettere," spiega Jeremy Kun, un laureando in matematica alla University of Illinois nel suo fantastico blog Math ∩ Programming.
Il "greed" degli algoritmi non è cosa buona, ma in genere funziona.
Funziona proprio così: scegli come se potessi scegliere una volta soltanto. Nel problema dello zaino illustrato sopra la nostra prima scelta potrebbe essere quella di prendere l'oggetto con il miglior ratio costo-per-peso. La nostra seconda scelta sarebbe il secondo oggetto migliore e così via fino a quando lo zaino non si è riempito completamente.
Una variazione di questo problema è il problema del resto in moneta, in cui dobbiamo ragigungere un determinato valore in centesimo usando diversi tipi di monete di vario tipo. L'obiettivo è quello di usare quanto meno monete possibile. Quindi, dato il sistema monetario americano, se devo arrivare a diciamo 90 centesimi, la prima scelta sarebbe la moneta di più alto valore più vicina ai 90 centesimi, quindi un pezzo da 50 centesimi. Dopodiché si procede così fino a quando non si è arrivati a 90 centesimi.
Direi che ce l'abbiamo fatta. Inoltre, sembra anche essere corretto. Le monete che ho scelto prima sono la scelta più ottimale: il minor numero di monete possibile per arrivare a 90 centesimi. In più abbiamo fatto in fretta, nel peggior dei casi si arriva al massimo a n operazioni, dove n è il valore da raggiungere utilizzando le monete (nel caso di 1 dollaro, n sarebbe uguale a 100 operazioni, per 100 monete da un centesimo)
Ma ecco il problema. Il greedy algorithm non fornisce una soluzione ottimale, non sempre perlomeno. Per il problema delle monete, fornisce solamente ciò che è chiamato un "sistema monete canonico," che nella maggior parte dei casi è limitato da un certo numero di tipi di monete, come nella realtà. Questa caratteristica non è presente ovunque, e dato un certo numero di tipi di monete (un numero molto grande e a noi sconosciuto) siamo di nuovo al punto di prima: con un problema NP-hard.
Fortunatamente non abbiamo sempre bisogno della soluzione più ottimale per il problema dello zaino o delle monete. In questo caso il greedy algorithm si comporta come un algoritmo di approssimazione, che è esattamente ciò che sembra: una soluzione abbastanza buona. E sai già quale sia questa soluzione, visto che arrivi a soluzioni abbastanza buone sempre, probabilmente grazie a un qualche tipo di informale logica greedy.
Il "greed" degli algoritmi non è cosa buona, ma in genere funziona.