Algoritmi greedy
Gli algoritmi greedy costruiscono la soluzione in maniera incrementale, e ad ogni passo si seleziona la parte della soluzione che permette di avvicinarsi sempre di più all’obiettivo.
Questo tipo di algoritmi si applica a problemi in cui devono essere selezionati degli oggetti che verificano una certa proprietà in modo da ottimizzare il costo associato agli oggetti selezionati.
- ordinare gli oggetti in base alla possibilità che facciano parte della soluzione
- generare la soluzione in maniera incrementale, scegliendo iterativamente l’oggetto più appetibile tra quelli non ancora selezionati
title: Attenzione
Gli algoritmi greedy non sono sempre la soluzione ottimale.Il problema deve avere delle proprietà affinché si possa implementare la soluzione greedy.
- sottostruttura ottima. Una soluzione ottima contiene le soluzioni ottime dei sottoproblemi
- scelta greedy. La scelta greedy permette di scegliere un elemento della soluzione che fa parte della soluzione ottima.
Un algoritmo greedy costruisce una soluzione in maniera incrementale, effettuando una serie di scelte in cui, ad ogni passo, si va a prendere una parte di soluzione che permette di ottimizzare il costo della soluzione parziale costruita fino a quel momento.
Un esempio di algoritmo greedy è il minimum spanning tree. Un altro esempio di algoritmo greedy è il Codifica di Huffman.