4.1 Definizione di algoritmi greedy.
Algoritmi Greedy (Greedy Algorithms) — sono una classe di algoritmi che costruiscono la soluzione prendendo decisioni localmente ottimali ad ogni passaggio. Queste decisioni sono prese in base allo stato attuale e non vengono riviste in futuro.
Gli algoritmi greedy sono spesso utilizzati per risolvere problemi di ottimizzazione, dove l'obiettivo è massimizzare o minimizzare una certa quantità.
Principi fondamentali degli algoritmi greedy
- Scelta Greedy: Ad ogni passo l'algoritmo sceglie la migliore opzione locale, che secondo lui porterà alla soluzione ottimale globale.
- Struttura Ottimale: Il problema deve avere la proprietà che le soluzioni ottimali locali possono essere combinate per ottenere la soluzione ottimale globale.
- Monotonia: Dopo aver scelto un ulteriore passo ottimale locale, la soluzione non dovrebbe essere peggiorata dalle scelte successive.
Vantaggi e svantaggi degli algoritmi greedy
Vantaggi:
- Semplicità di implementazione: Gli algoritmi greedy sono spesso semplici da comprendere e implementare.
- Efficienza: Di solito funzionano più velocemente rispetto ad algoritmi più complessi, come la programmazione dinamica.
Svantaggi:
- Mancanza di ottimalità globale: Gli algoritmi greedy non sempre portano alla soluzione ottimale globale.
- Non tutte le richieste sono adatte: Solo certi problemi possono essere risolti con algoritmi greedy.
Esiste un'intera classe di problemi il cui miglior risultato è ottenuto con un algoritmo greedy. Ti sarà utile sapere di questi.
4.2 Problema del resto del denaro.
Problema:
Abbiamo monete di diverso taglio. Bisogna trovare il numero minimo di monete per ottenere una somma data.
Soluzione:
Si prende sempre la moneta con il taglio più grande che non superi la somma rimanente.
Complessità temporale: O(n), dove n è il numero di tipi di monete.
Esempio di codice in Python:
def min_coins(coins, amount):
coins.sort(reverse=True)
count = 0
for coin in coins:
while amount >= coin:
amount -= coin
count += 1
return count
4.3 Problema dello zaino
Problema:
Abbiamo oggetti con valore e peso noti. Vogliamo mettere nello zaino di dimensione fissa oggetti dal massimo valore possibile
In questa variante del problema gli oggetti possono essere divisi in parti. Ad esempio, vogliamo comprare diversi tipi di cereali e possiamo prenderne anche 1000 grammi o 512.
Soluzione:
Ordinamento degli oggetti in base al valore relativo (valore/peso) e scelta dei valori relativi più alti fino a riempire lo zaino.
Complessità temporale: O(n log n), dove n è il numero di oggetti.
Esempio di codice in Python:
class Item:
def __init__(self, value, weight):
self.value = value
self.weight = weight
self.ratio = value / weight
def fractional_knapsack(items, capacity):
items.sort(key=lambda x: x.ratio, reverse=True)
total_value = 0.0
for item in items:
if capacity >= item.weight:
total_value += item.value
capacity -= item.weight
else:
total_value += item.ratio * capacity
break
return total_value
4.4 Problema della copertura con segmenti
Problema:
Ci sono segmenti su una linea retta, dati dai loro estremi (x1, x2), e un segmento bersaglio. Bisogna trovare il minimo numero di segmenti che coprono tutti i punti del segmento bersaglio.
Soluzione:
Ordinamento dei segmenti per l'estremo destro e scelta del segmento più piccolo che copra il punto attuale.
Complessità temporale: O(n log n), dove n è il numero di segmenti.
Esempio di codice in Python:
def min_segments(segments):
segments.sort(key=lambda x: x[1])
count = 0
end = -float('inf')
for seg in segments:
if seg[0] > end:
end = seg[1]
count += 1
return count
GO TO FULL VERSION