Gli algoritmi greedy, o algoritmi golosi, rappresentano una categoria fondamentale di tecniche risolutive in informatica e matematica combinatoria. Questi algoritmi sono progettati per risolvere problemi di ottimizzazione, nei quali l'obiettivo è trovare la soluzione migliore secondo un certo criterio. A differenza di altri approcci, come la programmazione dinamica o la ricerca esaustiva, gli algoritmi greedy prendono decisioni locali ottimali in ogni fase del processo, sperando che queste decisioni conducano a una soluzione globale ottimale. L'idea alla base di questa metodologia è piuttosto semplice: si seleziona la scelta migliore possibile al momento, senza preoccuparsi delle conseguenze future.

La caratteristica distintiva degli algoritmi greedy è il loro approccio locale alla risoluzione dei problemi. Essi valutano le opzioni disponibili in un dato momento e scelgono quella che appare più vantaggiosa, senza considerare come questa scelta influirà sulle decisioni future. Questi algoritmi non garantiscono sempre una soluzione ottimale per tutti i problemi, ma sono spesso molto efficienti e semplici da implementare. La loro efficacia dipende fortemente dalla struttura del problema da risolvere. Alcuni problemi, detti greedy-choice property, possono essere risolti in modo ottimale attraverso questo approccio, mentre altri potrebbero portare a soluzioni subottimali.

Un esempio classico di utilizzo degli algoritmi greedy è il problema del cambiamento di monete. Supponiamo di avere un insieme di monete di diverse denominazioni, e vogliamo trovare il modo più efficiente per restituire un certo importo. L'algoritmo greedy in questo caso funziona selezionando la moneta di valore più alto disponibile, sottraendo il valore della moneta dall'importo totale, e ripetendo il processo fino a quando non si raggiunge l'importo desiderato. Ad esempio, se abbiamo monete da 1, 5, e 10 euro e dobbiamo restituire 28 euro, l'algoritmo selezionerà prima due monete da 10 euro, poi una da 5 euro, e infine tre da 1 euro, per un totale di sette monete. Questo approccio è semplice e veloce, ma funzioni correttamente solo se le denominazioni delle monete seguono una certa logica, come nel caso delle monete europee.

Un altro esempio noto è l'algoritmo di Kruskal, utilizzato per trovare l'albero di copertura minimo in un grafo non orientato e pesato. In questo caso, l'algoritmo costruisce l'albero di copertura selezionando gli archi con il peso più basso, evitando cicli, fino a quando non si è connessi tutti i vertici. Inizialmente, si ordinano gli archi in base al loro peso, e si aggiunge l'arco più leggero all'albero finché non è stato raggiunto il numero richiesto di vertici. Questo metodo è particolarmente efficiente, grazie alla sua complessità temporale di O(E log E), dove E è il numero di archi del grafo.

Un ulteriore esempio di algoritmo greedy è l'algoritmo di Prim, anch’esso utilizzato per trovare l'albero di copertura minimo. A differenza dell'algoritmo di Kruskal, che si concentra sugli archi, l'algoritmo di Prim inizia da un vertice e aggiunge iterativamente l'arco più leggero che collega l'albero corrente a un nuovo vertice. Questo processo continua fino a coprire tutti i vertici del grafo. Anche Prim ha una buona complessità temporale, che può essere ottimizzata a O(E + V log V) utilizzando strutture dati appropriate come le code di priorità.

Un altro problema che può essere affrontato con un approccio greedy è il problema della selezione di attività. Supponiamo di avere un insieme di attività, ognuna con un tempo di inizio e un tempo di fine, e vogliamo massimizzare il numero di attività che possiamo completare senza sovrapposizioni. L'algoritmo greedy per questo problema consiste nel selezionare sempre l'attività che termina per prima, permettendo così di massimizzare il tempo disponibile per le attività successive. Questo approccio è efficiente e porta sempre a una soluzione ottimale.

Le formule associate agli algoritmi greedy variano in base al problema specifico che si sta risolvendo. Ad esempio, nel caso del problema del cambiamento di monete, possiamo esprimere il costo totale delle monete utilizzate come una somma dei valori delle monete scelte. Se denotiamo per ogni moneta il suo valore \( v_i \) e il numero di monete scelte come \( n_i \), il costo totale \( C \) può essere formulato come:

\[
C = \sum_{i=1}^{k} n_i \cdot v_i
\]

dove \( k \) è il numero totale di differenti denominazioni di monete. Per l'algoritmo di Kruskal, il costo totale dell'albero di copertura minimo è dato dalla somma dei pesi degli archi selezionati, simile alla formula precedente.

Nel corso della storia, diversi matematici e informatici hanno contribuito allo sviluppo degli algoritmi greedy. Uno dei pionieri in questo campo è stato il matematico statunitense Claude Shannon, noto per i suoi lavori sulla teoria dell'informazione, i quali hanno influenzato anche l'ottimizzazione. Altri contributi significativi sono arrivati da Richard Karp e Charles Papadimitriou, che hanno esteso la comprensione degli algoritmi greedy in contesti più complessi e in relazione a problemi NP-completi. Inoltre, la ricerca continua nel campo dell'ottimizzazione ha portato a nuove tecniche e miglioramenti degli algoritmi esistenti, rendendo gli algoritmi greedy ancora più utili in applicazioni pratiche.

In sintesi, gli algoritmi greedy rappresentano una potente e versatile metodologia di risoluzione dei problemi che, sebbene non sempre garantiscano una soluzione ottimale, offrono un approccio semplice e spesso efficace per affrontare una vasta gamma di problemi di ottimizzazione. Con una comprensione approfondita delle loro caratteristiche e delle situazioni in cui sono applicabili, è possibile sfruttare al meglio queste tecniche per risolvere problemi complessi in modo efficiente e pratico.