Algoritmo greedy: differenze tra le versioni

Versione delle 21:42, 21 apr 2023

Versione delle 16:27, 18 mag 2023

Riga 1:

{{F|algoritmi|ottobre 2015}}

Un '''algoritmo greedy''' è un [[paradigma algoritmico]], dovein l'[[algoritmo]]base cercaal quale la ricerca di una soluzione ammissibileottimale daavviene unseguendo puntouna strategia euristica di vistaproblem-sovling globalein attraversocui lal'[[algoritmo]], sceltaa dellaogni passaggio, opta per la soluzione piùottimale appetibilea livello locale (come 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 negliin altri casi non èso garantitapuò garantire la convergenza all'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ò, solitamentedi 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 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 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 ==