Algoritmo greedy: differenze tra le versioni

Versione delle 15:29, 5 giu 2013

Versione attuale delle 11:21, 16 set 2025

(34 versioni intermedie di 24 utenti non mostrate)

Riga 1:

Un '''algoritmo greedy''' (dall'inglese ''greedy'', avido) è un [[paradigma algoritmico]] che costruisce una soluzione passo dopo passo, effettuando ad ogni iterazione la scelta localmente ottimale, con l'obiettivo di trovare un ottimo globale<ref>{{cita libro|cognome=Cormen|nome=Thomas H.|cognome2=Leiserson|nome2=Charles E.|cognome3=Rivest|nome3=Ronald L.|cognome4=Stein|nome4=Clifford|titolo=Introduction to Algorithms|edizione=4|editore=MIT Press|anno=2022|isbn=978-0-262-04630-5|p=414-442}}</ref>. Questi algoritmi non sempre garantiscono la soluzione ottimale, ma sono spesso efficienti e forniscono buone approssimazioni per problemi di [[ottimizzazione (matematica)|ottimizzazione]] complessi<ref>{{cita libro|cognome=Kleinberg|nome=Jon|cognome2=Tardos|nome2=Éva|titolo=Algorithm Design|editore=Pearson|anno=2013|isbn=978-0321295354|p=115-171}}</ref>.

Un '''algoritmo greedy''' è un [[algoritmo]] che cerca di ottenere una soluzione ottima da un punto di vista globale attraverso la scelta della soluzione più ''golosa'' (aggressiva o avida, a seconda della traduzione preferita del termine ''greedy'' dall'inglese) ad ogni passo locale. Questa tecnica consente, dove applicabile (infatti non sempre si arriva ad una soluzione ottima), di trovare soluzioni ottimali per determinati problemi in un tempo polinomiale (cfr. [[NP-Completo|Problemi NP-Completi]], cioè problemi di soluzione non deterministica polinomiale).

Il paradigma greedy è caratterizzato da due proprietà fondamentali: la '''proprietà di scelta greedy''' (esiste sempre una soluzione ottimale che include la scelta localmente ottimale) e la '''sottostruttura ottima''' (la soluzione ottimale contiene soluzioni ottime ai sottoproblemi)<ref>{{cita libro|cognome=Demetrescu|nome=Camil|cognome2=Finocchi|nome2=Irene|cognome3=Liotta|nome3=Giuseppe|titolo=Algoritmi e strutture dati|edizione=3|editore=McGraw-Hill|anno=2019|isbn=978-8838615818|p=167-189}}</ref>.

== Esempi esplicativi ==

Il problema "Dai il minor numero di monete di resto utilizzando monete da 100, 10, 1 eurocent" è un problema risolvibile tramite un algoritmo di tipo greedy: ad ogni passo viene controllato il resto ancora da dare e si aggiunge la moneta con valore maggiore possibile. Quindi per dare un resto di 112 eurocent la macchina farà cadere in sequenza una moneta da 100, poi 10, poi 1, e infine ancora 1 eurocent (per un totale di 4 monete).

== Descrizione del paradigma ==

Il problema comunemente detto [[Problema del commesso viaggiatore|"del Commesso Viaggiatore"]], cioè "dato un numero di consegne e di ritiri con un mezzo che ha una portata massima P, si organizzi il viaggio che consente di viaggiare il minor numero di km con il maggior carico possibile per ottenere il massimo guadagno", non è un problema risolvibile tramite un algoritmo di tipo greedy, ma solo tramite algoritmi per [[NP-Completo|problemi NP-Completi]].

Un algoritmo greedy effettua una sequenza di scelte, dove ogni scelta è localmente ottimale al momento in cui viene presa. L'algoritmo non riconsiderera mai le scelte precedenti, a differenza della [[programmazione dinamica]] che esplora tutte le possibili combinazioni di sottoproblemi<ref>{{cita libro|cognome=Sedgewick|nome=Robert|cognome2=Wayne|nome2=Kevin|titolo=Algorithms|edizione=4|editore=Addison-Wesley|anno=2011|isbn=978-0321573513|p=655-678}}</ref>.

Facciamo notare che il problema del primo esempio, che possiamo chiamare "Minor monete di resto", è risolvibile grazie ad un algoritmo greedy solo per quell'insieme di valori di monete: se infatti avessimo anche monete da 105 eurocent, l'algoritmo greedy darebbe un totale di 8 monete (una da 105 e 7 da 1), quando posso trovare una soluzione ottima con 4 monete (100+10+1+1).

La strategia greedy può essere schematizzata come segue:

== Definizione formale ==

# Ordinare gli elementi secondo un criterio di ottimalità locale

In [[combinatoria]] e in [[ottimizzazione]] per '''algoritmo greedy''' si intende un algoritmo che consente di individuare una base di una [[matroide]] finita procedendo in modo notevolmente semplice ed efficiente.

# Inizializzare una soluzione vuota

# Per ogni elemento, se è compatibile con le scelte precedenti, aggiungerlo alla soluzione

# Restituire la soluzione costruita

=== Confronto con altri paradigmi ===

Consideriamo l'insieme E e una famiglia F di sottoinsiemi di E (<math> F \subseteq 2^E</math>) che forma un [[ideale d'ordine]] rispetto alla relazione di inclusione:

{| class="wikitable"

<math>A \in F \and B \subseteq A \to B \in F</math>

|-

! Paradigma !! Strategia !! Garanzia di ottimalità !! Complessità tipica

|-

| '''Greedy''' || Scelta localmente ottima || Solo per problemi specifici || O(n log n)

|-

| [[Programmazione dinamica]] || Esplorazione di tutti i sottoproblemi || Sì, se esiste sottostruttura ottima || O(n²) - O(n³)

|-

| [[Divide et impera]] || Suddivisione ricorsiva || Dipende dal problema || O(n log n)

|-

| [[Backtracking]] || Esplorazione con ritorno || Sì, ma può essere esponenziale || O(2ⁿ) - O(n!)

|}

== Proprietà fondamentali ==

La coppia E,F forma un sistema di indipendenza. Viene definita inoltre la funzione peso w.

=== Proprietà di scelta greedy ===

Dato un sistema di indipendenza E,F e una funzione peso w, si ricava un insieme M tale che w(M) sia il massimo.

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<ref>{{cita libro|cognome=Cormen|nome=Thomas H.|titolo=Introduction to Algorithms|anno=2022|p=418}}</ref>.

== Descrizione dell'algoritmo ==

'''Dimostrazione tipica (Exchange Argument):'''

Si consideri un [[matroide]] degli indipendenti ''M'' = (''E'',''I'').

# Supporre l'esistenza di una soluzione ottima I* che non contiene la scelta greedy

L'algoritmo si serve di un insieme variabile ''X'' che viene progressivamente ampliato fino a individuare una base.

# Costruire una nuova soluzione I' sostituendo un elemento di I* con la scelta greedy

# Dimostrare che |I'| ≤ |I*| e che I' è ammissibile

# Concludere che I' è ottima e contiene la scelta greedy

=== Sottostruttura ottima ===

* Inizialmente assegniamo l'insieme vuoto all'insieme variabile ''X''.

* Procediamo a considerare successivi elementi ''x'' in ''E'' non contenuti in ''X'';

** Se <math>X \cup \{x\}</math> è indipendente, allora trasformiamo il precedente ''X'' aggiungendogli x, cioè applichiamo l'istruzione <math>X := X \cup \{x\}</math>. In caso contrario il processo si conclude.

La '''sottostruttura ottima''' garantisce che, dopo aver effettuato la scelta greedy, il problema residuo mantiene la stessa struttura di ottimalità. Questo permette di applicare ricorsivamente la strategia greedy sui sottoproblemi rimanenti<ref>{{cita libro|cognome=Kleinberg|nome=Jon|titolo=Algorithm Design|anno=2013|p=118}}</ref>.

Il risultato è chiaramente un insieme indipendente. Esso inoltre è un insieme indipendente massimale, in quanto se B U {x} non è indipendente per qualche sottoinsieme B di ''X'', allora <math>X \cup \{x\}</math> non è indipendente (in caso contrario si andrebbe contro la proprietà di ereditarietà). Quindi se trascuriamo un elemento non avremo l'opportunità di utilizzarlo più tardi.

== Esempi classici ==

== Matroidi pesati e algoritmi greedy ==

=== Selezione di attività ===

Generalizziamo questo algoritmo per risolvere un problema più difficile.

{{Vedi anche|Problema di selezione delle 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.

Una ''funzione peso'' ''w'' : ''E'' → '''R'''⁺ per un matroide ''M''=(''E'', ''I'') assegna un peso strettamente positivo a ciascun elemento di ''E''. Estendiamo la funzione ai sottoinsiemi di ''E'' attraverso la somma; ''w''(''A'') è la somma dei ''w''(''x'') sugli ''x'' in ''A''. Un matroide con una funzione peso associata è detto un matroide pesato.

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

Come semplice esempio, diciamo di voler trovare la [[massima foresta di copertura]] di un grafo. Ovvero, dato un grafo e un peso per ogni arco, trovare una foresta contenente ogni vertice e che massimizzi il peso totale degli archi nell'albero. Questo problema si presenta in alcune applicazioni di clustering. Se guardiamo alla definizione del matroide foresta sopra, vediamo che la massima foresta di copertura è semplicemente il sottoinsieme indipendente con peso totale massimo — tale da ricoprire il grafo, poiché in caso contrario potremmo aggiungere archi senza creare cicli. Ma come lo troviamo?

<syntaxhighlight lang="text">

Un insieme indipendente di massimo peso totale è chiamato insieme ''ottimale''. Gli insiemi ottimali sono sempre basi, perché se può essere aggiunto un arco, dovrebbe essere fatto; ciò aumenta solo il peso totale. Si può dimostrare che esiste un banale algoritmo greedy per calcolare un insieme ottimale di una matroide pesata. Procede come segue:

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

</syntaxhighlight>

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

* Sia A l'insieme vuoto.

* Per ogni ''x'' in ''E'', preso in ordine (monotonicamente) decrescente di peso

** se A U {x} è indipendente, allora A diventi A U {x}.

=== Algoritmo di Kruskal ===

Tale algoritmo trova una base, poiché si tratta di un caso speciale del precedente algoritmo. Sceglie sempre l'elemento di massimo peso possibile preservando l'indipendenza (da cui il termine "greedy"). Ciò produce sempre un insieme ottimale: supponiamo che produca <math>A=\{e_1,e_2,\ldots,e_r\}</math> e che <math>B=\{f_1,f_2,\ldots,f_r\}</math>. Ora per ogni <math>k</math> con <math>1\le k\le r</math>, consideriamo gli insiemi aperti <math>O_1=\{e_1,\ldots,e_{k-1}\}</math> e <math>O_2=\{f_1,\ldots,f_k\}</math>. Visto che <math>O_1</math> è più piccolo di <math>O_2</math>, c'è qualche elemento di <math>O_2</math> che può essere messo in <math>O_1</math> mantenendo il risultato indipendente. Tuttavia <math>e_k</math> è un elemento di peso massimale che può essere aggiunto a <math>O_1</math> per mantenere l'indipendenza. Per cui <math>e_k</math> è di peso non inferiore di qualche elemento di <math>O_2</math>, e quindi <math>e_k</math> è of almeno di peso pari a <math>f_k</math>. Poiché questo vale per ogni <math>k</math>, <math>A</math> è più pesante di <math>B</math>.

{{Vedi anche|Algoritmo di Kruskal}}

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

Il modo più facile per traversare i membri di ''E'' nell'ordine desiderato è di ordinarli. Ciò richiede tempo O(|E|log|E|) utilizzando un [[algoritmo di ordinamento]]. Abbiamo anche bisogno di test per ogni ''x'' per determinare se A U {x} è indipendente; assumendo che il test di indipendenza richieda tempo O(f(|E|)) time, il tempo complessivo per l'algoritmo è O(|E|log|E| + |E|f(|E|)).

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

Se vogliamo trovare un albero di copertura minimo invece, semplicemente "invertiamo" la funzione peso sottraendola da una grande costante. Più precisamente, sia ''w''_min(''x'') = ''W'' - ''w''(''x''), dove ''W'' superi il peso totale attraverso tutti gli archi del grafo. Molti altri problemi di ottimizzazione su vari tipi di matroidi e funzioni peso possono essere risolti in questo modo banale, sebbene in molti casi possono essere trovati algoritmi più efficienti che sfruttano proprietà più specifiche.

<syntaxhighlight lang="text">

Notare anche che se prendiamo un insieme <math>I</math> di insiemi "indipendenti" che è un down-set ma non una matroide, allora l'algoritmo greedy non funzionerà sempre. Poiché in tal caso ci sono insiemi indipendenti <math>I_1</math> e <math>I_2</math> con <math>|I_1|<|I_2|</math>, ma tali che per nessun <math>e\in I_2\setminus I_1</math> è <math>I_1\cup e</math> indipendente.

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

</syntaxhighlight>

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

Prendiamo un <math>\varepsilon>0</math> e <math>\tau>0</math> tali che <math>(1+2\varepsilon)|I_1|+\tau|E|<|I_2|</math>. Pesiamo gli elementi di <math>I_1\cup I_2</math> nell'intervallo da <math>2</math> a <math>2+2\varepsilon</math>, gli elementi di <math>I_1\setminus I_2</math> nell'intervallo da <math>1+\varepsilon</math> a <math>1+2\varepsilon</math>, gli elementi di <math>I_2\setminus I_1</math> nell'intervallo da <math>1</math> a <math>1+\varepsilon</math>, e il resto nell'intervallo da <math>0</math> a <math>\tau</math>. L'algoritmo greedy sceglierà gli elementi di <math>I_1</math>, e in seguito non potrà scegliere nessun elemento di <math>I_2\setminus I_1</math>. Di conseguenza l'insieme indipendente che costruisce sarà di peso non superiore a <math>(1+2\varepsilon)|I_1|+\tau|E|+|I_1\cup I_2|</math>, che è più piccolo del peso di <math>I_2</math>.

=== Codifica di Huffman ===

{{Vedi anche|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.

<syntaxhighlight lang="text">

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)

</syntaxhighlight>

'''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''':

# Assumere l'esistenza di una soluzione ottima che differisce dalla scelta greedy

# Mostrare che è possibile "scambiare" elementi per ottenere una soluzione altrettanto buona che include la scelta greedy

# Concludere che esiste sempre una soluzione ottima con la scelta greedy

=== Dimostrazione della sottostruttura ottima ===

# Mostrare che dopo la scelta greedy, il problema residuo ha la stessa struttura

# 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 [[algoritmo di approssimazione|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 ==

{{Vedi anche|Matroide}}

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

# ∅ ∈ I (insieme vuoto è indipendente)

# Se A ∈ I e B ⊆ A, allora B ∈ I (proprietà ereditaria)

# 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<ref>{{cita news|cognome=Edmonds|nome=Jack|titolo=Matroids and the greedy algorithm|rivista=Mathematical Programming|volume=1|numero=1|anno=1971|pp=127-136|doi=10.1007/BF01584082}}</ref>.

=== Algoritmo greedy per matroidi pesati ===

<syntaxhighlight lang="text">

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

</syntaxhighlight>

== Esempi di implementazione ==

=== Problema del resto (cambio di monete) ===

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

<syntaxhighlight lang="text">

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

</syntaxhighlight>

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

=== Scheduling con deadline ===

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

<syntaxhighlight lang="text">

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

</syntaxhighlight>

== Voci correlate ==

* [[Programmazione dinamica]]

*[[Greedoide]]

* [[Algoritmo di approssimazione]]

* [[Teoria della complessità computazionale]]

* [[Matroide]]

* [[Algoritmo di Kruskal]]

* [[Algoritmo di Prim]]

* [[Codifica di Huffman]]

* [[Problema di selezione delle attività]]

== Note ==

<references/>

== Bibliografia ==

* {{cita libro|cognome=Cormen|nome=Thomas H.|cognome2=Leiserson|nome2=Charles E.|cognome3=Rivest|nome3=Ronald L.|cognome4=Stein|nome4=Clifford|titolo=Introduction to Algorithms|edizione=4|editore=MIT Press|anno=2022|isbn=978-0-262-04630-5}}

* {{cita libro|cognome=Kleinberg|nome=Jon|cognome2=Tardos|nome2=Éva|titolo=Algorithm Design|editore=Pearson|anno=2013|isbn=978-0321295354}}

* {{cita libro|cognome=Edmonds|nome=Jack|titolo=Paths, trees, and flowers|rivista=Canadian Journal of Mathematics|volume=17|anno=1965|pp=449-467}}

* {{cita libro|cognome=Demetrescu|nome=Camil|cognome2=Finocchi|nome2=Irene|cognome3=Liotta|nome3=Giuseppe|titolo=Algoritmi e strutture dati|edizione=3|editore=McGraw-Hill|anno=2019|isbn=978-8838615818}}

* {{cita libro|cognome=Sedgewick|nome=Robert|cognome2=Wayne|nome2=Kevin|titolo=Algorithms|edizione=4|editore=Addison-Wesley|anno=2011|isbn=978-0321573513}}

== Altri progetti ==

{{interprogetto|preposizione=sugli}}

== Collegamenti esterni ==

* {{en}} [https://web.stanford.edu/class/cs161/schedule.html Stanford CS161: Greedy Algorithms]

* {{en}} [https://www.algorithm-archive.org/contents/greedy_algorithms/greedy_algorithms.html Algorithm Archive: Greedy Algorithms]

* {{Collegamenti esterni}}

{{Portale|matematica|informatica}}

[[Categoria:Algoritmi di ottimizzazione]]

[[Categoria:Teoria delle matroidi]]

<!--[[Categoria:Ottimizzazione combinatoria]]-->

{{Portale|matematica}}