algoritmo greedy

Un algoritmo greedy è un , 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).