Cos'è un algoritmo goloso e come viene applicato…

L'algoritmo greedy è un approccio euristico che, ad ogni passo, prende la decisione localmente ottimale nella speranza che ciò porti a una soluzione globalmente ottimale.

Applicazioni:

Problema di selezione delle attività:

Problema: Scegliere il massimo numero di intervalli non sovrapposti in un insieme dato.
Soluzione greedy: Ordinare gli intervalli in base al tempo di fine crescente. Ad ogni passo, selezionare l'intervallo con il tempo di fine più piccolo che non si sovrappone a quelli già scelti.

# Esempio di selezione delle attività
# activities = [(start_time, end_time)]

activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
activities.sort(key=lambda x: x[1]) # Ordinare per tempo di fine

selected_activities = []
last_finish_time = -1

for activity in activities:
    if activity[0] >= last_finish_time:
        selected_activities.append(activity)
        last_finish_time = activity[1]

print(selected_activities) # [ (1, 4), (5, 7), (8, 11), (12, 16) ]

Problema di resto con le monete (Coin Change Problem) per set di monete canonici:
- Problema: Restituire una somma data con il numero minimo di monete.
- Soluzione greedy: Usare il più grande numero possibile di monete di denominazioni più grandi finché la somma non viene restituita. Funziona solo per alcuni set di monete (ad esempio, 1, 5, 10, 25).
```
# Esempio di resto con le monete (per monete canoniche)
coins = [25, 10, 5, 1]
amount = 67
result = {}

for coin in coins:
    while amount >= coin:
        result[coin] = result.get(coin, 0) + 1
        amount -= coin

print(result) # {25: 2, 10: 1, 5: 1, 1: 2}
```
Algoritmo di Kruskal per trovare l'albero di copertura minimo:
- Problema: Trovare un sottoinsieme di archi di un grafo non orientato pesato connesso che collega tutti i vertici con il peso totale minimo.
- Soluzione greedy: Ordinare tutti gli archi per peso in ordine crescente. Aggiungere gli archi in ordine, se non formano un ciclo con quelli già scelti, fino a quando non si avranno n-1 archi (dove n è il numero di vertici).

Gli algoritmi greedy sono facili da implementare, ma non sempre trovano la soluzione ottimale globale per problemi arbitrari. Per alcuni problemi (ad esempio, il resto con monete di set arbitrari, il problema dello zaino in generale), l'approccio greedy non è ottimale. Per garantire l'ottimalità o una migliore approssimazione, possono essere necessari metodi come la programmazione dinamica o altri. Prima di applicare un algoritmo greedy, è importante assicurarsi che sia adatto al problema specifico.

Cos'è un algoritmo goloso e come viene applicato nella risoluzione dei problemi?