Algoritmo greedyUn 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[1]. Questi algoritmi non sempre garantiscono la soluzione ottimale, ma sono spesso efficienti e forniscono buone approssimazioni per problemi di ottimizzazione complessi[2]. 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)[3]. Descrizione del paradigmaUn 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[4]. La strategia greedy può essere schematizzata come segue:
Confronto con altri paradigmi
Proprietà fondamentaliProprietà di scelta greedyLa 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[5]. Dimostrazione tipica (Exchange Argument):
Sottostruttura ottimaLa 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[6]. Esempi classiciSelezione 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 KruskalL'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 HuffmanLa 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 correttezzaPer dimostrare la correttezza di un algoritmo greedy sono necessari due passi: Dimostrazione della proprietà greedyUtilizzando l'exchange argument:
Dimostrazione della sottostruttura ottima
LimitazioniGli algoritmi greedy non sempre producono soluzioni ottime. Un esempio classico è il problema dello zaino frazionario vs problema dello zaino 0-1:
Esempio di fallimento: Capacità zaino: 10, Oggetti: (peso=6, valore=30), (peso=5, valore=20), (peso=4, valore=15)
Problemi di approssimazioneQuando gli algoritmi greedy non garantiscono l'ottimo, spesso forniscono buone approssimazioni:
Teoria dei matroidiUn matroide M = (E, I) è una struttura matematica dove E è un insieme finito e I è una famiglia di sottoinsiemi "indipendenti" di E che soddisfa:
Teorema fondamentale: Un algoritmo greedy trova sempre una soluzione ottima per problemi di ottimizzazione su matroidi pesati[7]. Algoritmo greedy per matroidi pesatiGREEDY_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 implementazioneProblema 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 deadlineDato 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
Voci correlate
Note
Bibliografia
Altri progetti
Collegamenti esterni
|
