Algoritmo greedy: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
correzione di "non so" in "non si" |
cosa c'entra il tempo polinomiale con la soluzione ottimale? |
||
| (6 versioni intermedie di 4 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]]
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 60:
Una ''funzione peso'' ''w'' : ''E'' → '''R'''<sup>+</sup> per un matroide ''M''=(''E'', ''I'') assegna un peso strettamente positivo a ciascun elemento di ''E''. Estendendo la funzione ai sottoinsiemi di ''E'' attraverso la somma; ''w''(''A'') è la somma dei ''w''(''x'') sugli ''x'' in ''A''. Un matroide con una funzione peso associata è detto un matroide pesato.
Come semplice esempio, diciamo di voler trovare la [[massima foresta di copertura]] di un [[grafo]]. Ovvero, dato un grafo e un peso per ogni arco, trovare una foresta contenente ogni vertice e che massimizzi il peso totale degli archi nell'albero. Questo problema si presenta in alcune applicazioni di clustering. Se guardiamo alla definizione del matroide foresta sopra, vediamo che la massima foresta di copertura è semplicemente il sottoinsieme indipendente con peso totale massimo — tale da ricoprire il grafo, poiché in caso contrario potremmo aggiungere archi senza creare cicli. Ma come lo troviamo?
Un insieme indipendente di massimo peso totale è chiamato insieme ''ottimale''. Gli insiemi ottimali sono sempre basi, perché se può essere aggiunto un arco, dovrebbe essere fatto; ciò aumenta solo il peso totale. Si può dimostrare che esiste un banale algoritmo greedy per calcolare un insieme ottimale di una matroide pesata. Procede come segue:
Riga 83:
* [[Greedoide]]
[[Categoria:Algoritmi di ottimizzazione|Greedy]]▼
[[Categoria:Teoria delle matroidi]]▼
== Altri progetti ==
{{interprogetto|preposizione=sull'}}
== Collegamenti esterni ==
* {{Collegamenti esterni}}
{{Portale|matematica}}
▲[[Categoria:Algoritmi di ottimizzazione|Greedy]]
▲[[Categoria:Teoria delle matroidi]]
| |||