Algoritmo greedy: differenze tra le versioni

Versione delle 23:31, 8 gen 2022

Versione delle 13:42, 10 gen 2022

Riga 1:

{{F|algoritmi|ottobre 2015}}

Un '''algoritmo greedy''' è un [[paradigma algoritmico]], dove l'[[algoritmo]] cerca una soluzione ammissibile da un punto di vista globale attraverso la scelta della soluzione più appetibile (definita in precedenza dal programmatore) per quel determinato programma a ogni passo locale. Quando applicabili, questi algoritmi consentono di trovare soluzioni ottimali per determinati problemi in un tempo polinomiale, mentre negli altri non è garantita la convergenza all'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ò, solitamente, viene applicata una tecnica ''cut and paste'' (quindi scelgo l'input migliore per poter risolvere il sottoproblema).

== Esempi esplicativi ==