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à.
