Algoritmo greedy: differenze tra le versioni

Versione delle 15:29, 5 giu 2013

Versione delle 17:36, 20 dic 2013

Riga 6:

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 un algoritmo di tipo greedy, ma solo tramite algoritmi per [[NP-Completo|problemi NP-Completi]].

Facciamo notare che il problema del primo esempio, che possiamo chiamare "Minor monete di resto", è risolvibile grazie ad un algoritmo greedy solo per quell'insieme di valori di monete: se infatti avessimo anche monete da 105 eurocent (valori monete: 105, 100, 10, 1), l'algoritmo greedy darebbe un totale di 8 monete (una da 105 e 7 da 1), quando posso trovare una soluzione ottima con 4 monete (100+10+1+1).

== Definizione formale ==