9-Algoritmi Greedy e dinamici: Gli algoritmi avidi (greedy) prendono decisioni localmente ottimali in ogni passo per ottenere un risultato globalmente ottimale, mentre gli algoritmi dinamici suddividono un problema complesso in sottoproblemi più piccoli e memorizzano le soluzioni per evitarne il ricalcolo.
9.1-Algoritmi Greedy: Gli algoritmi avidi fanno scelte localmente ottimali in ogni passo nella speranza di raggiungere una soluzione globalmente ottimale. In altre parole, l'algoritmo prende la decisione che sembra essere la migliore in quel momento senza considerare possibili conseguenze future. Gli algoritmi avidi sono spesso utilizzati in problemi di ottimizzazione, come problemi di scheduling, algoritmi di percorso minimo e problemi di insiemi. Un esempio classico di algoritmo avido è l'algoritmo di Dijkstra per la ricerca dei percorsi minimi in un grafo pesato con pesi non negativi sugli archi.
Un esempio comune di un algoritmo greedy è l'algoritmo di Kruskal per la costruzione di un albero di copertura minimo in un grafo pesato. Questo algoritmo seleziona ripetutamente l'arco con il peso minimo che non forma cicli nell'albero di copertura parziale già costruito, fino a quando tutti i nodi non sono connessi in un unico albero di copertura minimo.
Ecco un esempio di implementazione di Kruskal in Python:
python
Copy code
class Grafo:
def __init__(self, vertici):
self.V = vertici
self.grafo = []
def aggiungi_arco(self, u, v, peso):
self.grafo.append([u, v, peso])
def trova_set(self, parent, i):
if parent[i] == i:
return i
return self.trova_set(parent, parent[i])
def unisci_set(self, parent, rank, x, y):
x_root = self.trova_set(parent, x)
y_root = self.trova_set(parent, y)
if rank[x_root] < rank[y_root]:
parent[x_root] = y_root
elif rank[x_root] > rank[y_root]:
parent[y_root] = x_root
else:
parent[y_root] = x_root
rank[x_root] += 1
def kruskal(self):
result = []
i = 0
e = 0
self.grafo = sorted(self.grafo, key=lambda item: item[2])
parent = []
rank = []
for node in range(self.V):
parent.append(node)
rank.append(0)
while e < self.V - 1:
u, v, peso = self.grafo[i]
i += 1
x = self.trova_set(parent, u)
y = self.trova_set(parent, v)
if x != y:
e += 1
result.append([u, v, peso])
self.unisci_set(parent, rank, x, y)
print("Archi dell'albero di copertura minimo:")
for u, v, peso in result:
print(f"{u} - {v}: {peso}")
# Esempio di utilizzo:
g = Grafo(4)
g.aggiungi_arco(0, 1, 10)
g.aggiungi_arco(0, 2, 6)
g.aggiungi_arco(0, 3, 5)
g.aggiungi_arco(1, 3, 15)
g.aggiungi_arco(2, 3, 4)
g.kruskal()
In questo esempio, si crea un grafo con archi e pesi associati ad essi. L'algoritmo di Kruskal seleziona gli archi in ordine crescente di peso e li aggiunge all'albero di copertura minimo, assicurandosi di non formare cicli. Alla fine, l'algoritmo restituirà gli archi dell'albero di copertura minimo.
9.2-Algoritmi Dinamici: Gli algoritmi dinamici, al contrario, risolvono problemi suddividendoli in sottoproblemi più piccoli e memorizzando le soluzioni per evitarne il ricalcolo. Questa tecnica è basata sul principio di "programmazione dinamica", che risolve i sottoproblemi una sola volta e memorizza i loro risultati per utilizzarli successivamente se necessario. Gli algoritmi dinamici sono spesso applicati a problemi di ottimizzazione in cui è necessario esplorare tutte le possibili soluzioni. Un esempio comune è l'algoritmo di ricerca della più lunga sottosequenza comune (LCS) utilizzato nella teoria dei linguaggi di programmazione, bioinformatica, ecc.
Un classico esempio di algoritmo dinamico è l'algoritmo di ricerca della più lunga sottosequenza comune (LCS) tra due sequenze. La più lunga sottosequenza comune è la lunghezza massima di una sottosequenza che è comune a entrambe le sequenze di input. Questo problema è risolvibile in modo efficiente utilizzando la programmazione dinamica.
Ecco un esempio di implementazione in Python dell'algoritmo per calcolare la lunghezza della più lunga sottosequenza comune tra due stringhe:
python
Copy code
def longest_common_subsequence(str1, str2):
m = len(str1)
n = len(str2)
# Creazione della matrice per memorizzare le lunghezze delle sottosequenze
lcs_matrix = [[0] * (n + 1) for _ in range(m + 1)]
# Riempimento della matrice utilizzando la programmazione dinamica
for i in range(1, m + 1):
for j in range(1, n + 1):
if str1[i - 1] == str2[j - 1]:
lcs_matrix[i][j] = lcs_matrix[i - 1][j - 1] + 1
else:
lcs_matrix[i][j] = max(lcs_matrix[i - 1][j], lcs_matrix[i][j - 1])
return lcs_matrix[m][n] # Lunghezza della più lunga sottosequenza comune
# Esempio di utilizzo:
stringa1 = "AGGTAB"
stringa2 = "GXTXAYB"
lunghezza_LCS = longest_common_subsequence(stringa1, stringa2)
print(f"Lunghezza della più lunga sottosequenza comune: {lunghezza_LCS}")
In questo esempio, la funzione longest_common_subsequence prende in input due stringhe str1 e str2. Utilizza la programmazione dinamica per riempire una matrice lcs_matrix che memorizza le lunghezze delle sottosequenze comuni tra le due stringhe. Alla fine, restituisce la lunghezza massima della sottosequenza comune tra le due stringhe.
L'algoritmo sfrutta la tabulazione delle soluzioni ai sottoproblemi più piccoli per costruire la soluzione ottimale del problema principale. La complessità temporale di questo algoritmo è
O(m×n), dove m e n sono le lunghezze delle due stringhe di input.
La principale differenza tra questi due tipi di algoritmi sta nella strategia di risoluzione dei problemi e nell'approccio all'ottimizzazione. Mentre gli algoritmi avidi tendono a fare scelte locali ottimali senza considerare il contesto complessivo del problema, gli algoritmi dinamici suddividono il problema in sottoproblemi più piccoli e combinano le soluzioni parziali per ottenere la soluzione ottimale complessiva, spesso utilizzando la memorizzazione dei risultati intermedi.
La scelta tra l'uso di un algoritmo avido o di un algoritmo dinamico dipende dalla natura del problema e dalla struttura dei dati coinvolti. In alcuni casi, gli algoritmi avidi possono fornire una soluzione ottimale, mentre in altri casi, gli algoritmi dinamici possono essere più appropriati e garantire una soluzione ottimale attraverso la memorizzazione delle sottosoluzioni.
Nessun commento:
Posta un commento