Il metodo avido è una delle strategie come Divide et impera utilizzate per risolvere i problemi. Questo metodo viene utilizzato per risolvere problemi di ottimizzazione. Un problema di ottimizzazione è un problema che richiede risultati massimi o minimi. Capiamolo attraverso alcuni termini.
Il metodo Greedy è l’approccio più semplice e diretto. Non è un algoritmo, ma è una tecnica. La funzione principale di questo approccio è che la decisione viene presa sulla base delle informazioni attualmente disponibili. Qualunque siano le informazioni attuali, la decisione viene presa senza preoccuparsi dell'effetto della decisione attuale in futuro.
lente Java dell'array
Questa tecnica viene fondamentalmente utilizzata per determinare la soluzione fattibile che può essere o meno ottimale. La soluzione ammissibile è un sottoinsieme che soddisfa i criteri indicati. La soluzione ottima è quella che è la soluzione migliore e più favorevole nel sottoinsieme. Nel caso fattibile, se più di una soluzione soddisfa i criteri indicati, tali soluzioni saranno considerate fattibili, mentre la soluzione ottimale è la migliore soluzione tra tutte le soluzioni.
Caratteristiche del metodo Greedy
Di seguito le caratteristiche di un metodo goloso:
- Per costruire la soluzione in modo ottimale, questo algoritmo crea due insiemi in cui un insieme contiene tutti gli elementi scelti e un altro insieme contiene gli elementi rifiutati.
- Un algoritmo Greedy fa buone scelte locali nella speranza che la soluzione sia fattibile o ottimale.
Componenti dell'algoritmo Greedy
I componenti che possono essere utilizzati nell’algoritmo greedy sono:
che dimensioni ha lo schermo del mio monitor?
Applicazioni dell'algoritmo Greedy
- Viene utilizzato per trovare il percorso più breve.
- Viene utilizzato per trovare l'albero di copertura minimo utilizzando l'algoritmo di Prim o l'algoritmo di Kruskal.
- Viene utilizzato in una sequenza di lavori con una scadenza.
- Questo algoritmo viene utilizzato anche per risolvere il problema dello zaino frazionario.
Pseudo codice dell'algoritmo Greedy
Algorithm Greedy (a, n) { Solution : = 0; for i = 0 to n do { x: = select(a); if feasible(solution, x) { Solution: = union(solution , x) } return solution; } } Quanto sopra è l'algoritmo goloso. Inizialmente, alla soluzione viene assegnato valore zero. Passiamo l'array e il numero di elementi nell'algoritmo greedy. All'interno del ciclo for selezioniamo uno per uno gli elementi e controlliamo se la soluzione è fattibile oppure no. Se la soluzione è fattibile, allora eseguiamo l'unione.
Capiamo attraverso un esempio.
Supponiamo che ci sia un problema 'P'. Voglio viaggiare da A a B come mostrato di seguito:
P: A → B
Il problema è che dobbiamo percorrere questo viaggio da A a B. Ci sono varie soluzioni per andare da A a B. Possiamo andare da A a B a piedi, in macchina, in bicicletta, in treno, in aereo , ecc. C'è un vincolo nel viaggio che dobbiamo percorrere questo viaggio entro 12 ore. Se vado in treno o in aereo, posso coprire questa distanza entro 12 ore. Esistono molte soluzioni a questo problema ma ci sono solo due soluzioni che soddisfano il vincolo.
Se diciamo che dobbiamo coprire il viaggio al costo minimo. Ciò significa che dobbiamo percorrere questa distanza il minimo possibile, quindi questo problema è noto come problema di minimizzazione. Finora abbiamo due soluzioni praticabili, ovvero una in treno e un’altra in aereo. Poiché viaggiare in treno comporterà un costo minimo, è una soluzione ottimale. Una soluzione ottimale è anche la soluzione fattibile, ma fornisce il miglior risultato in modo che quella soluzione sia la soluzione ottimale con il costo minimo. La soluzione ottimale sarebbe una sola.
Il problema che richiede un risultato minimo o massimo è noto come problema di ottimizzazione. Il metodo goloso è una delle strategie utilizzate per risolvere i problemi di ottimizzazione.
lista collegata
Svantaggi dell'utilizzo dell'algoritmo Greedy
L'algoritmo goloso prende decisioni basate sulle informazioni disponibili in ogni fase senza considerare il problema più ampio. Quindi, potrebbe esserci la possibilità che la soluzione avida non dia la soluzione migliore per ogni problema.
Segue la scelta dell'ottimo locale in ogni fase con l'intento di trovare l'ottimo globale. Capiamo attraverso un esempio.
semplice programma Python
Consideriamo il grafico riportato di seguito:
Dobbiamo viaggiare dalla fonte alla destinazione al costo minimo. Poiché abbiamo tre soluzioni ammissibili con percorsi di costo pari a 10, 20 e 5, 5 è il percorso di costo minimo, quindi è la soluzione ottimale. Questo è l'ottimo locale e in questo modo troviamo l'ottimo locale in ogni fase per calcolare la soluzione ottima globale.