Algoritmo greedy: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m +wl |
cosa c'entra il tempo polinomiale con la soluzione ottimale? |
||
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).
| |||