Algoritmo greedy: differenze tra le versioni

Versione delle 17:37, 10 mag 2021

Versione delle 16:01, 2 dic 2021

Riga 5:

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

Il problema comunemente dettocosiddetto [[Problemaproblema 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-Completocompleto|problemi NP-Completicompleti]].

Il primo esempio è risolvibile grazie ad un algoritmo greedy solo per opportuni insiemi di valori di monete: infatti se ci fossero ad esempio 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), mentre la soluzione ottima è quella con 4 monete (100+10+1+1).

Riga 12:

In [[combinatoria]] e in [[Ottimizzazione (matematica)|ottimizzazione]] per algoritmo greedy si intende un algoritmo che consente di individuare una base di una [[matroide]] finita procedendo in modo notevolmente semplice ed efficiente.

Si consideri l'insieme E e una famiglia F di sottoinsiemi di E (<math> F \subseteq 2^E</math>) che forma un [[Ideale (matematica)|ideale]] d'ordine]] rispetto alla relazione di inclusione:

<math>A \in F \land B \subseteq A \to B \in F</math>

Riga 60:

[[Categoria:Algoritmi di ottimizzazione|Greedy]]

[[Categoria:Teoria delle matroidi]]

<!--[[Categoria:Ottimizzazione combinatoria]]-->

== Altri progetti ==

{{interprogetto}}