Algoritmo greedy

Un algoritmo goloso[1][2][3][4] o greedy (dall'inglese, lett. "avido") è un tipo di algoritmo che costruisce una soluzione passo dopo passo, effettuando ad ogni iterazione la scelta localmente ottimale, con l'obiettivo di trovare (o approssimare) un ottimo globale[5]. Questa classe di algoritmi non sempre garantisce la soluzione ottimale, ma offre spesso il vantaggio dell'efficienza, con buone approssimazioni per problemi di ottimizzazione complessi[6].

Il paradigma goloso è caratterizzato da due proprietà fondamentali: la proprietà di scelta golosa (esiste sempre una soluzione ottimale che include la scelta localmente ottimale) e la sottostruttura ottima (la soluzione ottimale contiene soluzioni ottime ai sottoproblemi)[7]. Il rispetto di queste proprietà garantisce l'ottenimento dell'ottimo globale.

Descrizione del paradigma

Un algoritmo greedy effettua una sequenza di scelte, in cui ogni scelta è localmente ottimale al momento in cui viene presa. L'algoritmo non riconsidererà mai le scelte precedenti, a differenza della programmazione dinamica che esplora tutte le possibili combinazioni di sottoproblemi[8].

La strategia greedy può essere schematizzata come segue:

  1. Ordinare gli elementi secondo un criterio di ottimalità locale
  2. Inizializzare una soluzione vuota
  3. Per ogni elemento, se è compatibile con le scelte precedenti, aggiungerlo alla soluzione
  4. Restituire la soluzione costruita

Confronto con altri paradigmi

ParadigmaStrategiaGaranzia di ottimalità
GreedyScelta localmente ottimaSolo per problemi specifici
Programmazione dinamicaEsplorazione di tutti i sottoproblemiSì, se esiste sottostruttura ottima
Divide et imperaSuddivisione ricorsivaDipende dal problema
BacktrackingEsplorazione con ritornoSì, ma può essere esponenziale

Proprietà fondamentali

Proprietà di scelta greedy

La proprietà di scelta greedy stabilisce che una scelta localmente ottima porta sempre a una soluzione globalmente ottima. Formalmente, esiste sempre una soluzione ottima che contiene la scelta greedy effettuata al primo passo[9].

Dimostrazione tipica (Exchange Argument)
  1. Supporre l'esistenza di una soluzione ottima I* che non contiene la scelta greedy
  2. Costruire una nuova soluzione I' sostituendo un elemento di I* con la scelta greedy
  3. Dimostrare che |I'| ≤ |I*| e che I' è ammissibile
  4. Concludere che I' è ottima e contiene la scelta greedy

Sottostruttura ottima

La sottostruttura ottima garantisce che, dopo aver effettuato la scelta greedy, il problema residuo mantenga la stessa struttura ottima. Questo permette di applicare ricorsivamente la strategia greedy ai sottoproblemi rimanenti[10].

Esempi classici

Selezione di attività

Il problema di selezione delle attività consiste nel selezionare il massimo numero di attività mutuamente compatibili da un insieme di attività, ciascuna caratterizzata da un tempo di inizio e un tempo di fine.

Strategia greedy: Selezionare sempre l'attività che termina prima tra quelle non ancora considerate.

ACTIVITY_SELECTOR(s, f, n):
    A = {a₁}
    k = 1
    for m = 2 to n:
        if s[m] ≥ f[k]:
            A = A ∪ {aₘ}
            k = m
    return A

Complessità: O(n log n) per l'ordinamento iniziale, O(n) per la selezione.

Algoritmo di Kruskal

L'algoritmo di Kruskal trova l'albero di copertura minimo di un grafo pesato utilizzando una strategia greedy.

Strategia greedy: Selezionare sempre l'arco di peso minimo che non crea cicli.

KRUSKAL(G):
    A = ∅
    for each vertex v ∈ G.V:
        MAKE_SET(v)
    sort edges of G.E in nondecreasing order by weight
    for each edge (u,v) ∈ G.E:
        if FIND_SET(u) ≠ FIND_SET(v):
            A = A ∪ {(u,v)}
            UNION(u,v)
    return A

Complessità: O(E log E) dove E è il numero di archi.

Codifica di Huffman

La codifica di Huffman costruisce un codice a lunghezza variabile ottimale per la compressione di dati.

Strategia greedy: Unire sempre i due nodi con frequenza minima.

HUFFMAN(C):
    n = |C|
    Q = C
    for i = 1 to n-1:
        allocate new node z
        z.left = x = EXTRACT_MIN(Q)
        z.right = y = EXTRACT_MIN(Q)  
        z.freq = x.freq + y.freq
        INSERT(Q, z)
    return EXTRACT_MIN(Q)

Complessità: O(n log n) utilizzando una coda di priorità.

Analisi di correttezza

Per dimostrare la correttezza di un algoritmo greedy sono necessari due passi:

Dimostrazione della proprietà greedy

Utilizzando l'exchange argument:

  1. Assumere l'esistenza di una soluzione ottima che differisce dalla scelta greedy
  2. Mostrare che è possibile "scambiare" elementi per ottenere una soluzione altrettanto buona che include la scelta greedy
  3. Concludere che esiste sempre una soluzione ottima con la scelta greedy

Dimostrazione della sottostruttura ottima

  1. Mostrare che dopo la scelta greedy, il problema residuo ha la stessa struttura
  2. Dimostrare che una soluzione ottima del problema originale contiene soluzioni ottime dei sottoproblemi

Limitazioni

Gli algoritmi greedy non sempre producono soluzioni ottime. Un esempio classico è il problema dello zaino frazionario vs problema dello zaino 0-1:

  • Zaino frazionario: L'algoritmo greedy (ordinare per rapporto valore/peso) è ottimale
  • Zaino 0-1: L'algoritmo greedy può fallire e richiede programmazione dinamica
Esempio di fallimento

Capacità zaino: 10, Oggetti: (peso=6, valore=30), (peso=5, valore=20), (peso=4, valore=15)

  • Greedy: seleziona primo oggetto → valore totale = 30
  • Ottimo: seleziona secondo e terzo oggetto → valore totale = 35

Problemi di approssimazione

Quando gli algoritmi greedy non garantiscono l'ottimo, spesso forniscono buone approssimazioni:

  • Set Cover: Greedy garantisce approssimazione O(log n)
  • Vertex Cover: Greedy garantisce approssimazione 2-ottimale
  • TSP metrico: Algoritmi greedy garantiscono approssimazioni costanti

Teoria dei matroidi

Un matroide M = (E, I) è una struttura matematica dove E è un insieme finito e I è una famiglia di sottoinsiemi "indipendenti" di E che soddisfa:

  1. ∅ ∈ I (insieme vuoto è indipendente)
  2. Se A ∈ I e B ⊆ A, allora B ∈ I (proprietà ereditaria)
  3. Se A, B ∈ I e |A| < |B|, esiste x ∈ B\A tale che A ∪ {x} ∈ I (proprietà di scambio)

Teorema fondamentale: Un algoritmo greedy trova sempre una soluzione ottima per problemi di ottimizzazione su matroidi pesati[11].

Algoritmo greedy per matroidi pesati

GREEDY_MATROID(M, w):
    A = ∅
    sort elements of M.E in decreasing order by weight w
    for each x ∈ M.E:
        if A ∪ {x} ∈ M.I:
            A = A ∪ {x}
    return A

Esempi di implementazione

Problema del resto (cambio di monete)

Per sistemi monetari "canonici" (come Euro), l'algoritmo greedy è ottimale:

CHANGE_MAKING(amount, coins):
    result = []
    sort coins in decreasing order
    for each coin in coins:
        while amount ≥ coin:
            result.append(coin)
            amount -= coin
    return result

Attenzione: Per sistemi non canonici, l'algoritmo può fallire.

Scheduling con deadline

Dato un insieme di lavori con profitti e deadline, massimizzare il profitto:

JOB_SCHEDULING(jobs, n):
    sort jobs by profit in decreasing order
    result = []
    for i = 0 to n-1:
        for j = min(n, jobs[i].deadline)-1 down to 0:
            if result[j] is empty:
                result[j] = jobs[i]
                break
    return result

Note

  1. ↑ algoritmo goloso, su Nuovo De Mauro. URL consultato il 21 giugno 2026.
  2. ↑ Marco Liverani, Programmare in C. Guida al linguaggio attraverso esercizi svolti e commentati, Società Editrice Esculapio, 2020, p. 279, ISBN 9788835807896.
    «È opportuno sottolineare che quello di Kruskal è un algoritmo che appartiene alla famiglia degli algoritmi "golosi", in gergo greedy.»
  3. ↑ Luigia Berardi e Albrecht Beutelspacher, Matematica discreta. Dai fondamenti alle applicazioni, Franco Angeli, 2003, p. 62, ISBN 9788846449207.
  4. ↑ Mauro Cerasoli, Elementi di matematica discreta, Zanichelli, 1988, p. 244, ISBN 9788808038586.
  5. ↑ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein, Introduction to Algorithms, 4ª ed., MIT Press, 2022, p. 414-442, ISBN 978-0-262-04630-5.
  6. ↑ Jon Kleinberg e Éva Tardos, Algorithm Design, Pearson, 2013, p. 115-171, ISBN 978-0321295354.
  7. ↑ Camil Demetrescu, Irene Finocchi e Giuseppe Liotta, Algoritmi e strutture dati, 3ª ed., McGraw-Hill, 2019, p. 167-189, ISBN 978-8838615818.
  8. ↑ Robert Sedgewick e Kevin Wayne, Algorithms, 4ª ed., Addison-Wesley, 2011, p. 655-678, ISBN 978-0321573513.
  9. ↑ Thomas H. Cormen, Introduction to Algorithms, 2022, p. 418.
  10. ↑ Jon Kleinberg, Algorithm Design, 2013, p. 118.
  11. ↑ Jack Edmonds, Matroids and the greedy algorithm, in Mathematical Programming, vol. 1, n. 1, 1971, pp. 127-136, DOI:10.1007/BF01584082.

Bibliografia

  • (EN) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein, Introduction to Algorithms, 4ª ed., MIT Press, 2022, ISBN 978-0-262-04630-5.
  • (EN) Jon Kleinberg e Éva Tardos, Algorithm Design, Pearson, 2013, ISBN 978-0321295354.
  • (EN) Jack Edmonds, Paths, trees, and flowers, in Canadian Journal of Mathematics, vol. 17, 1965, pp. 449-467.
  • Camil Demetrescu, Irene Finocchi e Giuseppe Liotta, Algoritmi e strutture dati, 3ª ed., McGraw-Hill, 2019, ISBN 978-8838615818.
  • (EN) Robert Sedgewick e Kevin Wayne, Algorithms, 4ª ed., Addison-Wesley, 2011, ISBN 978-0321573513.

Voci correlate

Altri progetti

Collegamenti esterni

Questa voce è stata pubblicata da Wikipedia. Il testo è rilasciato in base alla licenza Creative Commons Attribution-Share Alike 4.0, salvo diversa indicazione. Potrebbero essere applicate clausole aggiuntive per i file multimediali.