Algoritmo greedy: differenze tra le versioni

Versione delle 14:55, 12 mag 2024

Versione delle 23:02, 8 giu 2024

Riga 4:

Per fare ciò, di solito, viene applicata una tecnica ''cut and paste'' (quindi scelgo l'input migliore per poter risolvere il sottoproblema).

Un tipo di strategia greedy può essere applicata al [[problema del commesso viaggiatore]] (che è un problema ad alta [[Teoria della complessità computazionale|complessità computazionale]]): essa può essere, ad esempio, quella che , a ogni passaggio, obbedisce alla seguente regola euristica: "A ogni passo del tragitto, vai alla più vicina tra le città non ancora visitate". L'adozione di questo semplice approccio [[Euristica|euristico]] non è in grado di garantire la soluzione ottima a questo problema complesso, ma ha il pregio che l'esecuzione termina dopo un ragionevole numero di passi; trovare una soluzione ottimale a un problema così complesso richiede, tipicamente, un numero altissimo di passaggi, circostanza che lo rende un problema praticamente non affrontabile.

== Esempi esplicativi ==

Riga 13:

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

Riga 52:

** Se <math>X \cup \{x\}</math> è indipendente, allora si trasforma il precedente ''X'' aggiungendogli x, cioè <math>X := X \cup \{x\}</math>. In caso contrario il processo si conclude.

Il risultato è un insieme indipendente. Inoltre esso è un [[insieme indipendente massimale]] in quanto se B U {x} non fosse indipendente per qualche sottoinsieme B di ''X'', allora <math>X \cup \{x\}</math> non sarebbe indipendente: in caso contrario si andrebbe contro la proprietà di ereditarietà. Quindi se si trascura un elemento non si avrà l'opportunità di utilizzarlo più tardi.

== Matroidi pesati e algoritmi greedy ==