In questo tutorial imparerai cos'è un algoritmo avido. Inoltre, troverai un esempio di approccio avido.
Un algoritmo avido è un approccio per risolvere un problema selezionando la migliore opzione disponibile al momento, senza preoccuparsi del risultato futuro che porterebbe. In altre parole, le scelte migliori a livello locale mirano a produrre i migliori risultati a livello globale.
Questo algoritmo potrebbe non essere l'opzione migliore per tutti i problemi. In alcuni casi può produrre risultati errati.
Questo algoritmo non torna mai indietro per invertire la decisione presa. Questo algoritmo funziona con un approccio dall'alto verso il basso.
Il vantaggio principale di questo algoritmo è:
- L'algoritmo è più facile da descrivere .
- Questo algoritmo può funzionare meglio di altri algoritmi (ma non in tutti i casi).
Soluzione fattibile
Una soluzione fattibile è quella che fornisce la soluzione ottimale al problema.
Algoritmo avido
- Per cominciare, il set di soluzioni (contenente le risposte) è vuoto.
- Ad ogni passaggio, un elemento viene aggiunto al set di soluzioni.
- Se la soluzione impostata è fattibile, l'elemento corrente viene mantenuto.
- Altrimenti, l'elemento viene rifiutato e non viene mai più preso in considerazione.
Esempio: approccio avido
Problema: devi modificare un importo utilizzando il minor numero possibile di monete. Importo: $ 28 Monete disponibili: $ 5 moneta $ 2 moneta $ 1 moneta
Soluzione:
- Crea un set di soluzioni vuoto = ().
- monete = (5, 2, 1)
- somma = 0
- Mentre somma ≠ 28, fai quanto segue.
- Seleziona una moneta C dalle monete tale che somma + C <28.
- Se C + sum> 28, non restituisce alcuna soluzione.
- Altrimenti, somma = somma + C.
- Aggiungi C al set di soluzioni.
Fino alle prime 5 iterazioni, il set di soluzioni contiene 5 monete da $ 5. Dopodiché, otteniamo 1 moneta da $ 2 e infine 1 moneta da $ 1.
Greedy Algorithm Applications
- Ordina selezione
- Problema dello zaino
- Spanning Tree minimo
- Problema del percorso più breve di origine singola
- Problema di pianificazione del lavoro
- Algoritmo Minimal Spanning Tree di Prim
- Algoritmo Minimal Spanning Tree di Kruskal
- Algoritmo Minimal Spanning Tree di Dijkstra
- Codifica Huffman
- Algoritmo Ford-Fulkerson
