Algoritmo greedy: differenze tra le versioni

Versione delle 14:54, 12 mag 2024

Versione attuale delle 18:10, 13 dic 2024

(4 versioni intermedie di 3 utenti non mostrate)

Riga 1:

{{F|algoritmi|ottobre 2015}}

Un '''algoritmo ''greedy''''' o '''algoritmo goloso'''<ref>{{cita libro|citazione=È opportuno sottolineare che [[Algoritmo di Kruskal|quello di Kruskal]] è un algoritmo che appartiene alla famiglia degli algoritmi "golosi", in gergo ''greedy''.|url=https://www.google.it/books/edition/Programmare_in_C_Guida_al_linguaggio_att/BybdDwAAQBAJ?hl=it&gbpv=1&dq=algoritmi+golosi&pg=PA279&printsec=frontcover|isbn=9788835807896|cognome=Liverani|nome=Marco|titolo=Programmare in C. Guida al linguaggio attraverso esercizi svolti e commentati|editore=Società Editrice Esculapio|anno=2020|p=279}}</ref><ref>{{cita libro|cognome1=Berardi|nome1=Luigia|cognome2=Beutelspacher|nome2=Albrecht|titolo=Matematica discreta. Dai fondamenti alle applicazioni|editore=Franco Angeli|anno=2003|lingua=it|p=62|url=https://www.google.it/books/edition/Matematica_discreta_Dai_fondamenti_alle/JrFOKxhi1DQC?hl=it&gbpv=1&dq=algoritmo+goloso&pg=PA62&printsec=frontcover|isbn=9788846449207}}</ref><ref>{{cita libro|cognome=Cerasoli|nome=Mauro|titolo=Elementi di matematica discreta|editore=Zanichelli|anno=1988|lingua=it|p=244|url=https://www.google.it/books/edition/Elementi_di_matematica_discreta/N-3uAAAAMAAJ?hl=it&gbpv=1&bsq=algoritmo+goloso&dq=algoritmo+goloso&printsec=frontcover|isbn=9788808038586}}</ref> è un [[paradigma algoritmico]] in base al quale la ricerca di una soluzione ottimale avviene seguendo una strategia euristica di problem-solving in cui l'[[algoritmo]], a ogni passaggio, opta per la soluzione ottimale a livello locale (come definita in precedenza dal programmatore). Quando applicabili, questi algoritmi consentono di trovare soluzioni ottimali per determinati problemi in un [[tempo polinomiale]], mentre; in altrimolti casi, non si può garantire la convergenza verso un 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.

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 ==

Riga 83:

* [[Greedoide]]

[[Categoria:Algoritmi di ottimizzazione|Greedy]]

[[Categoria:Teoria delle matroidi]]

== Altri progetti ==

{{interprogetto|preposizione=sull'}}

Line 92 ⟶ 90:

{{Portale|matematica}}

[[Categoria:Algoritmi di ottimizzazione|Greedy]]

[[Categoria:Teoria delle matroidi]]