Cos'è un algoritmo greedy e in quali casi viene applicato?

L'algoritmo greedy è un approccio per risolvere problemi di ottimizzazione che, ad ogni passo, sceglie la migliore soluzione locale (l'opzione più vantaggiosa dal punto di vista del momento attuale) nella speranza che questa sequenza di soluzioni locali ottimali conduca a una soluzione globalmente ottimale. Non considera le possibili conseguenze della scelta attuale sui passi futuri.

Caratteristiche:

• Semplicità: Di solito più facile da implementare rispetto alla programmazione dinamica o ad altri metodi di ottimizzazione.
• Velocità: Spesso ha una complessità computazionale inferiore.
• Garanzia di ottimalità: Non garantisce sempre di trovare la soluzione globalmente ottimale. La garanzia vale solo per alcune classi di problemi.

Viene applicato in problemi dove è stato dimostrato che la scelta localmente ottimale ad ogni passo conduce a una soluzione globalmente ottimale. Esempi:

• Problema di selezione delle attività: Scegliere il massimo numero di attività non sovrapposte nel tempo.
• Problema dello zaino (con frazionamento degli oggetti): Quando gli oggetti possono essere divisi. Altrimenti, si tratta di un problema di programmazione dinamica.
• Algoritmo di Prim e Kruskal: Per trovare l'albero di copertura minimo in un grafo.
• Algoritmo di Dijkstra: Per trovare il percorso più breve in un grafo con pesi non negativi.
• Codifica di Huffman: Per costruire un codice prefisso ottimale.

Esempio di pseudocodice per l'algoritmo di selezione delle attività:

Funzione SelezionaAttività(attività):
  Ordina attività per tempo di fine
  attività_selezionate = lista vuota
  ultimo_tempo_fine = 0

  Per ogni attività in attività:
    Se attività.inizio >= ultimo_tempo_fine:
      Aggiungi attività a attività_selezionate
      ultimo_tempo_fine = attività.fine

  Ritorna attività_selezionate

È importante verificare se l'algoritmo greedy è applicabile a un problema specifico, poiché altrimenti potrebbe fornire una soluzione subottimale.