Algoritmo greedy: differenze tra le versioni

Versione delle 16:01, 2 dic 2021

Versione delle 23:24, 8 gen 2022

Riga 8:

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).

Un altro esempio noto e ampiamente conosciuto è l'algoritmo di ''selezione delle attività'', il cui pseudocodice è presentato dal Cormen<ref>{{Cita libro|nome=Thomas H.|cognome=Cormen|nome2=Charles E.|cognome2=Leiserson|nome3=Ronald L.|cognome3=Rivest|titolo=Introduction to Algorithms|url=https://mitpress.mit.edu/books/introduction-algorithms-fourth-edition|accesso=2022-01-08|edizione=4|data=2022-03-22|editore=MIT Press|lingua=en|ISBN=978-0-262-04630-5}}</ref>.

<math>RECURSIVE-ACTIVITY-SELECTOR(s,f,k)

</math>

<math>m = k + 1</math>

<math>while \ m \leq n \ and \ s[m] \ \leq k </math>

<math>m = m + 1</math>

<math>if \ m \leq n</math>

<math>return \ a_m \bigcup RECURSIVE-ACTIVITY-SELECTOR(s,f,m,n)</math>

<math>else \ return \ 0</math>

Tale algoritmo seleziona le attività che sono compatibili da un punto di vista temporale, evitando che si sovrappongano. Piuttosto che selezionare tutte le attività, seleziona il maggior numero di attività tali che non siano sovrapponibili l'una con l'altra, quindi con inizio/fine distinti le une dalle altre. Un altro esempio noto di algoritmo greedy è la [[codifica di Huffman]], normalmente utilizzato nella compressione dei file e che utilizza il medesimo principio, quindi l'ottimizzazione dei dati presenti selezionando le frequenze in maniera ottimale alla posizione e numero dei singoli caratteri.

== Definizione formale ==