Che cos'è un algoritmo greedy

Un algoritmo greedy è un algoritmo che genera una soluzione a un problema di ottimizzazione selezionando la “migliore” scelta disponibile da un insieme di opzioni decisionali in ogni fase.

Un algoritmo greedy molto noto è l'algoritmo del vicino più prossimo per risolvere i problemi di pianificazione dei tour: Si costruiscono i tour partendo dal deposito e visitando in ogni fase la località/cliente più vicina che non è ancora stata visitata e la cui aggiunta al tour è consentita. Se non è possibile aggiungere altre località, si torna al deposito, si completa il tour corrente e si inizia un nuovo tour. L'algoritmo termina quando tutte le località/clienti sono state aggiunte ai tour.

Sfortunatamente, gli algoritmi greedy di solito danno risultati molto scarsi, perché alla fine sono disponibili solo opzioni decisionali molto sfavorevoli. Un'eccezione è rappresentata dalla determinazione di un albero minimo di spanning in un grafo. In questo caso speciale, l'algoritmo greedy (il cosiddetto “algoritmo di Kruskal”) trova effettivamente una soluzione ottimale garantita.

Was ist ein Greedy-Algorithmus - gts systems
Consenso per i cookie con "Real Cookie Banner"