Sommario:
Definizione - Cosa significa Greedy Algorithm?
Un algoritmo avido è una strategia algoritmica che rende la migliore scelta ottimale in ogni piccola fase con l'obiettivo di questo alla fine portare a una soluzione ottimale a livello globale. Ciò significa che l'algoritmo sceglie la migliore soluzione al momento senza tener conto delle conseguenze. Seleziona il miglior output immediato, ma non considera il quadro generale, quindi è considerato avido.
Techopedia spiega Greedy Algorithm
Un algoritmo avido funziona scegliendo la migliore risposta possibile in ogni passaggio e quindi passando al passaggio successivo fino a raggiungere la fine, senza considerare la soluzione complessiva. Spera solo che il percorso che intraprende sia quello ottimale a livello globale, ma come dimostrato più volte, questo metodo spesso non fornisce una soluzione ottimale a livello globale. In effetti, è del tutto possibile che le soluzioni più ottimali a breve termine portino al peggior risultato globale possibile.
Consideralo come prendere molte scorciatoie in un'azienda manifatturiera: a breve termine grandi quantità vengono risparmiate nei costi di produzione, ma questo alla fine porta a un calo poiché la qualità è compromessa, con conseguente ritorno dei prodotti e vendite basse man mano che i clienti conoscono il Prodotto "economico". Ma questo non è sempre il caso, ci sono molte applicazioni in cui l'algoritmo avido funziona meglio per trovare o approssimare la soluzione ottimale a livello globale come la costruzione di un albero di Huffman o di un albero di apprendimento delle decisioni.
Ad esempio: prendi il percorso con la somma più grande complessiva. Un algoritmo avido prenderebbe il percorso blu, a causa della miopia, piuttosto che il percorso arancione, che produce la somma più grande.
componenti:
- Un set di dati candidato che necessita di una soluzione
- Una funzione di selezione che sceglie il miglior collaboratore alla soluzione finale
- Una funzione di fattibilità che aiuta la funzione di selezione determinando se un candidato può contribuire alla soluzione
- Una funzione obiettiva che assegna un valore a una soluzione parziale
- Una funzione di soluzione che indica che è stata scoperta la soluzione ottimale
