Algoritmo greedy

Definizione di algoritmo greedy

Gli algoritmi greedy sono una metodologia di progettazione algoritmica che, per risolvere un problema di ottimizzazione, ad ogni passo fa la scelta che sembra localmente ottima in quel determinato momento, con la speranza che questa conduca a una soluzione globalmente ottima.

DP vs Greedy

A differenza della programmazione dinamica (DP), che valuta e memorizza le soluzioni di tutti i sotto-problemi per costruire una soluzione ottimale complessiva, un algoritmo greedy si concentra solo sulla scelta più vantaggiosa nell’istante attuale.

Questa strategia di “scelta localmente ottima” non garantisce sempre la soluzione globale ottima per tutti i problemi. Tuttavia, per alcuni problemi, l’approccio greedy è sorprendentemente efficace e porta a risultati ottimali con notevole efficienza. In altri contesti, anche quando non produce la soluzione globalmente ottimale, può comunque servire come un’euristica efficace per problemi computazionalmente complessi.

Quando gli Algoritmi Greedy Funzionano: Il Problema di Selezione Attività

Un classico esempio in cui un algoritmo greedy fornisce la soluzione ottima è il Problema di Selezione Attività (Activity Selection Problem).

Problema: Dato un insieme di attività, ognuna con un tempo di inizio e un tempo di fine, che devono utilizzare la stessa risorsa, si vuole trovare il più grande sottoinsieme di attività mutualmente compatibili (ovvero, che non si sovrappongono).

Approccio con Programmazione Dinamica: Un approccio con Programmazione Dinamica per questo problema definirebbe come il numero ottimo di attività incluse in un intervallo. La relazione ricorsiva (dove è una delle attività incluse nell’insieme) richiederebbe di considerare tutte le possibilità, portando a una complessità temporale di per riempire una matrice .

Approccio Greedy Ottimale: È possibile fare molto meglio con un algoritmo greedy. La strategia avida consiste nel seguire questi passi:

1. Ordinare le attività in base al loro tempo di fine crescente.
2. Selezionare la prima attività (quella che termina prima).
3. Successivamente, selezionare l’attività compatibile successiva che inizia dopo la fine dell’ultima attività selezionata.

Esempio Pratico: Consideriamo l’esempio fornito:

Attività (i)	Inizio	Fine
1	0	3
2	1	4
3	2	5
4	5	7
5	3	9
6	5	9
7	7	10

Le attività sono già ordinate per tempo di fine.

• Passo 1: Si seleziona l’attività 1 (). .
• Passo 2: Si cerca la prossima attività che inizia dopo la fine di (fine: 3). L’attività 4 () inizia a 5. .
• Passo 3: Si cerca la prossima attività che inizia dopo la fine di (fine: 7). L’attività 7 () inizia a 7. .

La soluzione ottenuta è . La correttezza di questo approccio è dimostrata da un teorema che afferma che l’attività con il tempo di fine minore appartiene sempre a un sottoinsieme massimale di attività mutualmente compatibili. La dimostrazione procede per assurdo, sostituendo l’attività con fine minore di un insieme massimale con quella scelta dall’algoritmo greedy e mostrando che le cardinalità e compatibilità vengono mantenute, implicando che sono lo stesso insieme.

La complessità di questo algoritmo è dopo l’ordinamento iniziale, che se fatto con MergeSort o QuickSort è .

Quando gli Algoritmi Greedy Falliscono: Il Problema dello Zaino

Non tutti i problemi di ottimizzazione possono essere risolti in modo ottimale con un approccio greedy. Un esempio emblematico è il Problema dello Zaino (Knapsack Problem).

Problema: Si ha uno zaino con una certa capacità massima e una serie di oggetti, ognuno con un volume e un valore . L’obiettivo è selezionare un sottoinsieme di oggetti da mettere nello zaino in modo da massimizzare il valore totale, senza superare la capacità.

Esempio Pratico: Zaino con capacità .

Oggetto (i)	Volume	Valore
1	2	10
2	3	5
3	5	15
4	7	7

Tentativo Greedy (Massimizzare il Valore):

1. Si ordina per valore decrescente: Oggetto 3 (15), Oggetto 1 (10), Oggetto 4 (7), Oggetto 2 (5).
2. Passo 1: Si prende l’Oggetto 3 (Volume: 5, Valore: 15). Capacità rimanente: 10. .
3. Passo 2: Si prende l’Oggetto 1 (Volume: 2, Valore: 10). Capacità rimanente: 8. .
4. Passo 3: Si prende l’Oggetto 4 (Volume: 7, Valore: 7). Capacità rimanente: 1. . Valore totale: . Volume occupato: . Questa soluzione non è ottima. La soluzione (valore , volume ) non è migliore. Ma la soluzione ha valore 32. La fonte indica come soluzione ottima S = {O2, O3, O4} con valore 27, ma questo sembra un errore nella trascrizione dell’esempio. Un esempio migliore potrebbe essere che vale con volume . La soluzione non è possibile. Se la capacità è 15, la combinazione dà con volume . Se aggiungiamo , valore , volume . Questa è la soluzione data. Ah, la fonte dice: “NO! S = {O2, O*, O+} ottiene lo stesso guadagno utilizzando tutto”, il che implica che è ma con volume 15. Dunque, l’algoritmo greedy scelto per valore non è ottimo perché non utilizza la capacità al massimo. Un’altra combinazione come è con volume , che supera la capacità. La soluzione ottimale per la capacità 15 in questo esempio è con valore 32 e volume 14. L’algoritmo greedy basato su valore trova questa soluzione. La fonte dice “NO!” per la soluzione che dà 32, e poi propone ” ottiene lo stesso guadagno utilizzando tutto”. Questo è logicamente incoerente dato che ha valore 5, ha valore 15, ha valore 7, per un totale di . Il riferimento sembra indicare che è nel testo pseudocodice. Cerchiamo di chiarire l’esempio e la sua conclusione: se ha valore 32 e volume 14, e la capacità è 15, questa è un’ottima soluzione. L’affermazione “NO! ottiene lo stesso guadagno utilizzando tutto” è problematica. Se si riferisse a un guadagno uguale o migliore a quello ottenuto, e dovesse utilizzare tutto lo spazio (il che non è richiesto per l’ottimalità, solo per i problemi di “bin packing”), sarebbe un altro tipo di problema. La frase implica che il guadagno di è 32, il che non è vero (). L’errore nel testo della fonte evidenzia la necessità di verificare sempre gli assunti. Il punto chiave è che, indipendentemente dalla soluzione precisa in questo esempio, l’algoritmo greedy non è garantito essere ottimale per il problema dello zaino.

Tentativo Greedy (Massimizzare il Rapporto Valore/Volume):

1. Si calcola il rapporto valore/volume: , , , .
2. Si ordina per rapporto decrescente: Oggetto 1 (5), Oggetto 3 (3), Oggetto 2 (1.67), Oggetto 4 (1).
3. Passo 1: Si prende l’Oggetto 1 (Volume: 2, Valore: 10). Capacità rimanente: 13.
4. Passo 2: Si prende l’Oggetto 3 (Volume: 5, Valore: 15). Capacità rimanente: 8.
5. Passo 3: Si prende l’Oggetto 2 (Volume: 3, Valore: 5). Capacità rimanente: 5.
6. Passo 4: Si tenta di prendere l’Oggetto 4 (Volume: 7), ma non c’è spazio sufficiente. Soluzione ottenuta: . Valore: . Volume occupato: . Anche in questo caso, la soluzione non è quella con valore 32 ottenuta prima. Questo dimostra che, per il problema dello zaino, le scelte localmente ottime non conducono necessariamente a una soluzione globalmente ottima.

Applicazioni Avanzate: Algoritmi per Minimum Spanning Tree (MST)

Nonostante i limiti per alcuni problemi, gli algoritmi greedy sono fondamentali per la risoluzione di altri problemi complessi, come il Problema dell’Albero di Connessione Minimo (Minimum Spanning Tree - MST).

Problema: Dato un grafo connesso, non orientato e pesato , si cerca un sottoinsieme aciclico di archi che connetta tutti i vertici con il peso totale minimo . Questo problema è utile, ad esempio, per collegare i PIN di un circuito elettrico minimizzando il consumo di filo.

Gli algoritmi di Kruskal e Prim risolvono il problema MST in modo efficiente utilizzando entrambi una metodologia avida.

Principio Generico dell’MST Greedy: Generic-MST

L’idea base è aggiungere iterativamente un “arco sicuro” all’insieme A (inizialmente vuoto) finché A non forma un MST. Un “arco sicuro” è un arco che, se aggiunto ad A, mantiene la proprietà che A è un sottoinsieme di qualche MST.

Per definire un arco sicuro, introduciamo il concetto di taglio e arco leggero:

• Un taglio di un grafo non orientato è una partizione dell’insieme dei vertici in due sottoinsiemi e .
• Un arco attraversa il taglio se un estremo è in e l’altro è in .
• Un taglio rispetta un insieme di archi se nessun arco in attraversa il taglio (cioè, tutti gli archi in hanno entrambi gli estremi nello stesso sottoinsieme o ).
• Un arco è leggero per un taglio se il suo peso è il minimo tra i pesi di tutti gli archi che attraversano quel taglio.

Lemma dell’Arco Sicuro: Sia un grafo connesso non orientato e pesato. Sia un sottoinsieme di che è contenuto in qualche MST per . Sia un taglio di che rispetta . Sia un arco leggero che attraversa il taglio. Allora è un arco sicuro per .

• Dimostrazione (per “taglia e incolla”): Si assume un MST che contiene ma non (se lo contenesse, sarebbe già dimostrato). L’aggiunta di a crea un ciclo. Poiché attraversa il taglio , il ciclo deve contenere almeno un altro arco che attraversa lo stesso taglio. Rimuovendo dal ciclo, si ottiene un nuovo albero . Dato che è un arco leggero per il taglio, , quindi . Questo implica che è anch’esso un MST. Poiché è un sottoinsieme di , è un arco sicuro per .

Un Corollario importante derivante dal lemma dell’arco sicuro è che se è una componente connessa (un albero) nella foresta generata finora (dall’insieme ), e è un arco leggero che connette a un altro albero non in , allora è un arco sicuro per . Questo corollario è la base per gli algoritmi di Kruskal e Prim.

Algoritmo di Kruskal

L’algoritmo di Kruskal costruisce un MST aggiungendo iterativamente gli archi sicuri alla foresta di alberi di connessione, partendo da una situazione in cui ogni vertice è un albero separato senza archi.

Strategia Greedy di Kruskal:

1. Inizializzare un insieme A vuoto per contenere gli archi del MST.
2. Per ogni vertice , creare un insieme disgiunto contenente solo (MakeSet(v)).
3. Ordinare tutti gli archi del grafo in una lista in ordine non decrescente di peso.
4. Scorrere gli archi in (dal più leggero al più pesante):
   • Per ogni arco , se e appartengono a insiemi disgiunti diversi (FindSet(u) != FindSet(v)), significa che l’arco non forma un ciclo con gli archi già selezionati.
   • In tal caso, aggiungere ad A e unire gli insiemi contenenti e (Union(u,v)).

Implementazione delle Operazioni su Insiemi Disgiunti (DSU): Per gestire gli insiemi disgiunti, si utilizza una struttura dati DSU che supporta le operazioni MakeSet, FindSet e Union. Una implementazione efficiente si basa su liste concatenate modificate:

• Ogni lista ha puntatori alla testa (head) e alla coda (tail).
• Il rappresentante dell’insieme è l’elemento in testa alla lista.
• Ogni nodo ha un puntatore back che punta alla testa della sua lista, facilitando FindSet in .
• MakeSet(x): Crea una nuova lista con come unico elemento. Costo: .
• FindSet(x): Restituisce il rappresentante dell’insieme di (seguendo x.back). Costo: .
• Union(u,v): Concatena la lista di (o del suo rappresentante) alla coda della lista di (o del suo rappresentante). Tutti i nodi nella lista di devono aggiornare il loro puntatore back per puntare alla testa della lista di . Costo: nel caso peggiore (se la lista di è lunga ).

Analisi della Complessità di Kruskal:

1. Inizializzazione (MakeSet per ogni vertice): .
2. Ordinamento degli archi: (es. con MergeSort).
3. Ciclo principale (for e in L): Esegue iterazioni. Ogni iterazione include due FindSet ( ciascuno) e potenzialmente una Union ( nel caso peggiore con liste concatenate semplici). Utilizzando un’analisi ammortizzata più avanzata (non trattata in dettaglio nella fonte ma accennata), che sfrutta l’implementazione DSU con alberi e compressione dei percorsi, una sequenza di operazioni MakeSet, FindSet, Union su elementi impiega dove è la funzione inversa di Ackermann, estremamente lenta, rendendo il tempo quasi costante. In pratica, la complessità delle operazioni DSU è quasi . Pertanto, la complessità totale di Kruskal è dominata dall’ordinamento degli archi: . Poiché in un grafo connesso , , quindi può essere visto come .

Esempio Visivo (Kruskal): Immagina un grafo con 9 vertici e vari archi pesati. Kruskal selezionerà gli archi in ordine di peso:

1. Arco (d,e) peso 1. A = {(d,e)}. Union(d,e).
2. Arco (g,h) peso 2. A = {(d,e), (g,h)}. Union(g,h).
3. Arco (c,f) peso 2. A = {(d,e), (g,h), (c,f)}. Union(c,f). … e così via, unendo le componenti connesse con gli archi più leggeri che non formano cicli.

Algoritmo di Prim

A differenza di Kruskal, l’algoritmo di Prim costruisce l’MST a partire da un singolo vertice sorgente r e fa crescere un solo albero.

Strategia Greedy di Prim:

1. Inizializzare per ogni vertice : v.key = ∞ (costo per connettersi all’albero in crescita) e v.pi = NIL (predecessore nell’albero MST).
2. Impostare r.key = 0 per la radice scelta, in modo che sia il primo nodo estratto.
3. Creare una coda a min-priorità Q contenente tutti i vertici di .
4. Finche Q non è vuota:
   • Estrarre il vertice u con il key minimo da Q (Extract-Min(Q)). Questo u viene aggiunto all’MST.
   • Per ogni vertice v adiacente a u (for v in G.Adj[u]):
     • Se v è ancora in Q (non è ancora stato aggiunto all’MST) e il peso dell’arco è minore del v.key corrente:
       • Aggiornare v.pi = u (impostando u come predecessore di v nell’MST).
       • Aggiornare v.key = w(u,v) (nuovo costo minimo per connettere v all’MST) e aggiornare la priorità di v in Q (Decrease-Key(Q, v, w(u,v))).

Struttura Dati per Coda a Min-Priorità: L’efficienza di Prim dipende crucialmente dall’implementazione della coda a min-priorità. I min-Heap sono una scelta comune.

• Un min-heap è un array che rappresenta un albero binario quasi completo, dove ogni nodo genitore ha un valore minore o uguale a quello dei suoi figli.
• Operazioni chiave per min-heap: Insert, Minimum, Extract-Min, Decrease-Key.

Analisi della Complessità di Prim:

• Inizializzazione: per impostare key e pi.
• Popolamento della coda a priorità: Inserire elementi in un min-heap costa se fatto element by element, o se si costruisce l’heap direttamente.
• Ciclo while Q != ∅: Esegue volte Extract-Min (costo ciascuno). Totale .
• Ciclo for v in G.Adj[u]: Tutti gli archi vengono esaminati al più una volta, in totale volte. Ogni Decrease-Key costa . Totale .
• Complessità totale: (poiché in un grafo connesso ).

Esempio Visivo (Prim): Immagina un grafo con 9 vertici e vari archi pesati, partendo dal nodo ‘a’.

1. Inizializzazione: tutti i nodi hanno key = ∞, pi = NIL, tranne ‘a’ che ha key = 0.
2. Extract-Min estrae ‘a’.
3. Per i vicini di ‘a’ (b,h): b.key diventa 4 (da a), h.key diventa 8 (da a). Aggiornate le priorità in Q.
4. Extract-Min estrae ‘b’ (key 4).
5. Per i vicini di ‘b’ (a,c,h,i): c.key diventa 8 (da b), i.key diventa 7 (da b). h.key diventa 7 (da b) perché . … e così via, facendo crescere l’albero MST.

Relazione con Ricerca A* e Euristiche

Il concetto greedy emerge anche nel campo della ricerca informata, in particolare nella ricerca A* e nella ricerca Best-First Greedy.

• Una Ricerca Best-First Greedy utilizza una funzione di valutazione , dove è una funzione euristica che stima il costo per raggiungere l’obiettivo dal nodo . Fa una scelta localmente ottima basandosi solo sulla stima del costo rimanente, senza considerare il costo già sostenuto per raggiungere . Non è garantita la soluzione ottima.
• L’algoritmo A* è un’estensione più sofisticata, che utilizza una funzione di valutazione , dove è il costo effettivo dal nodo iniziale a , e è l’euristica. A* è ottimo se l’euristica è ammissibile (non sovrastima mai il costo reale per raggiungere l’obiettivo).

È possibile concettualizzare questi algoritmi come casi particolari di una Ricerca A Pesata (Weighted A*)*, dove la funzione di valutazione è con un peso sull’euristica.

• Ricerca Costo Uniforme (equivalente a Dijkstra): , quindi . Si basa solo sul costo accumulato.
• Ricerca A*: , quindi . Bilancia costo accumulato e stima rimanente.
• Ricerca Best-First Greedy: (o molto grande, enfatizzando solo ), quindi . Si basa solo sulla stima del costo rimanente.

Gli algoritmi greedy, pur non essendo una soluzione universale per l’ottimalità, rimangono strumenti computazionalmente efficienti e fondamentali nel panorama degli algoritmi, spesso utilizzati in combinazione con euristiche per problemi complessi dove una soluzione esaustiva sarebbe impraticabile.