Algoritmo greedy: differenze tra le versioni

Versione delle 23:24, 8 gen 2022

Versione delle 23:31, 8 gen 2022

Riga 1:

{{F|algoritmi|ottobre 2015}}

Un '''algoritmo greedy''' è un [[paradigma algoritmico]], dove l'[[algoritmo]] cerca una soluzione ammissibile da un punto di vista globale attraverso la scelta della soluzione più appetibile (definita in precedenza dal programmatore) per quel determinato programma a ogni passo locale. Quando applicabili, questi algoritmi consentono di trovare soluzioni ottimali per determinati problemi in un tempo polinomiale, mentre negli altri non è garantita la convergenza all'ottimo globale. In particolare questi algoritmi cercano di mantenere una proprietà di ''sottostruttura ottima'', quindi cercano di risolvere i sottoproblemi in maniera "avida" (da cui la traduzione letterale ''algoritmi avidi'' in italiano) considerando una parte definita migliore nell'input per risolvere tutti i problemi.

== Esempi esplicativi ==

Riga 11:

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>RECURSIVEGREEDY-ACTIVITY-SELECTOR(s,f,k)

</math>

<math>mA = k + 1A_1</math>

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

<math>mfor =\ m=2 \ to +\ 1n</math>

<math>if \ s[m] \leqgeq nf(k)</math>

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

<math>else \ return \ 0k=m</math>

<math>return \ A</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.