Algoritmo greedy: differenze tra le versioni

Versione delle 16:48, 26 ago 2009

Versione delle 16:49, 26 ago 2009

Riga 2:

== Esempi esplicativi ==

Il problema "Dai il minor numero di monete di resto utilizzando monete da 100, 10, 12 eurocent" è un problema risolvibile tramite un algoritmo di tipo greedy: ad ogni passo viene controllato il resto ancora da dare e si aggiunge la moneta con valore maggiore possibile. Quindi per dare un resto di 112 eurocent la macchina farà cadere in sequenza una moneta da 100, poi 10, poi 2 eurocent (per un totale di 3 monete).

Il problema comunemente detto [[Problema del commesso viaggiatore|"del Commesso Viaggiatore"]], cioè "dato un numero di consegne e di ritiri con un mezzo che ha una portata massima P, si organizzi il viaggio che consente di viaggiare il minor numero di km con il maggior carico possibile per ottenere il massimo guadagno", non è un problema risolvibile tramite nessun algoritmo di tipo greedy, ma solo tramite algoritmi per [[NP-Completo|problemi NP-Completi]].