Algoritmo greedy
paradigma algoritmico / Da Wikipedia, l'enciclopedia encyclopedia
Caro Wikiwand AI, Facciamo breve rispondendo semplicemente a queste domande chiave:
Puoi elencare i principali fatti e statistiche su Algoritmo greedy?
Riassumi questo articolo per un bambino di 10 anni
Un algoritmo greedy è 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, mentre in altri casi non si può garantire la convergenza 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ò, 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 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.