Algoritmo greedy: differenze tra le versioni

Versione delle 13:42, 10 gen 2022

Versione delle 11:43, 18 gen 2022

Riga 13:

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>GREEDY\text{greedy-ACTIVITYactivity-SELECTORselector}(s,f)</math>

</math>

<math>A = A_1</math>

Line 77 ⟶ 75:

Prendiamo un <math>\varepsilon>0</math> e <math>\tau>0</math> tali che <math>(1+2\varepsilon)|I_1|+\tau|E|<|I_2|</math>. Pesiamo gli elementi di <math>I_1\cup I_2</math> nell'intervallo da <math>2</math> a <math>2+2\varepsilon</math>, gli elementi di <math>I_1\setminus I_2</math> nell'intervallo da <math>1+\varepsilon</math> a <math>1+2\varepsilon</math>, gli elementi di <math>I_2\setminus I_1</math> nell'intervallo da <math>1</math> a <math>1+\varepsilon</math>, e il resto nell'intervallo da <math>0</math> a <math>\tau</math>. L'algoritmo greedy sceglierà gli elementi di <math>I_1</math>, e in seguito non potrà scegliere nessun elemento di <math>I_2\setminus I_1</math>. Di conseguenza l'insieme indipendente che costruisce sarà di peso non superiore a <math>(1+2\varepsilon)|I_1|+\tau|E|+|I_1\cup I_2|</math>, che è più piccolo del peso di <math>I_2</math>.

== Note ==

<references/>

== Voci correlate ==

* [[Colorazione golosa]]