Differenza tra metodo greedy e programmazione dinamica
Per risolvere i problemi di ottimizzazione in informatica vengono utilizzati due metodi principali, vale a dire l’approccio o metodo greedy e la programmazione dinamica. Le soluzioni prodotte dagli algoritmi greedy sono più efficaci delle soluzioni di programmazione dinamica. La differenza principale tra il metodo greedy e la programmazione dinamica è che il metodo greedy genera solo una sequenza decisionale. Al contrario, la programmazione dinamica può produrre molte sequenze decisionali.
Definizione di metodo Greedy
Un metodo Greedy è considerato l’approccio progettuale più diretto e può essere applicato a un ampio tipo di problemi. Di solito, questi tipi di problemi contengono “n” input da cui si ottiene un certo gruppo di un sottoinsieme che soddisfa alcune condizioni. Il sottoinsieme che soddisfa queste condizioni è chiamato soluzione fattibile . Si cerca la particolare soluzione ammissibile che possa aumentare o diminuire la funzione obiettivo data, questa soluzione è chiamata come soluzione ottima . Una soluzione fattibile può essere facilmente determinata mentre una soluzione ottimale è difficile da trovare.
Il metodo goloso è utile per ideare un algoritmo che coinvolge alcune fasi con un’unica assunzione in ciascuna fase del suo funzionamento. Per ogni fase particolare, viene presa una decisione contro l’input in un ordine identificato da una procedura di selezione per la soluzione ottimale. L’input non è incluso nella soluzione parziale se l’aggiunta dell’ingresso successivo nella soluzione ottimale parzialmente costruita potrebbe portare al risultato non fattibile. Altrimenti, viene aggiunto.
La misura di ottimizzazione è il fondamento della procedura di selezione sotto forma di funzione obiettivo. Esistono diverse misure di ottimizzazione che producono soluzioni subottimali e questa tecnica è nota come paradigma del sottoinsieme.
Definizione di programmazione dinamica
La programmazione dinamica viene utilizzata per progettare gli algoritmi. È stato pensato principalmente per il problema che implica il risultato di una sequenza di decisioni. Quando è difficile ottenere una sequenza di decisioni graduali di un problema che portano alla sequenza decisionale ottimale, viene dedotta ogni possibile sequenza decisionale. Quindi tutta la sequenza decisionale può essere calcolata e viene selezionata la migliore. La programmazione dinamica è in grado di diminuire in modo significativo la quantità di enumerazione eludendo l’enumerazione relativa alle sequenze decisionali che non contengono risultati ottimali.
La programmazione dinamica segue il principio di ottimalità. Però, qual è il principio di ottimalità? Descrive che una sequenza ottimale di decisioni possiede una caratteristica che è indipendente dallo stato iniziale e dalla decisione e il resto delle decisioni dovrebbe costruire una sequenza di decisioni ottimale rispetto allo stato di esito della prima decisione.
La complessità degli algoritmi di programmazione dinamica è solitamente polinomiale. Un’altra proprietà cruciale di questo approccio è che le soluzioni ottimali dei sottoproblemi vengono memorizzate in precedenza per eliminare la richiesta di ricalcolo dei suoi valori.
Differenza tra metodo greedy e programmazione dinamica
- Il metodo Greedy produce una singola sequenza decisionale mentre nella programmazione dinamica possono essere prodotte molte sequenze decisionali.
- L’approccio di programmazione dinamico è più affidabile dell’approccio greedy.
- Il metodo greedy segue un approccio dall’alto verso il basso. Al contrario, la programmazione dinamica si basa su una strategia dal basso verso l’alto.
- L’algoritmo Greedy contiene un insieme univoco di un insieme fattibile di soluzioni in cui le scelte locali del sottoproblema portano alla soluzione ottimale. Al contrario, nella programmazione dinamica viene scelto un problema tra tutti i sottoproblemi secondari che è in grado di fornire una soluzione ottimale.
- La programmazione dinamica è meno efficiente e può essere inutilmente costosa dell’algoritmo greedy.
- Il metodo Greedy non ha la capacità di gestire i sottoproblemi sovrapposti mentre l’approccio di programmazione dinamica gestisce con successo i sottoproblemi sovrapposti.
- L’implementazione del metodo greedy è lo zaino frazionario, l’algoritmo del percorso più breve, eccetera. Al contrario, lo zaino 0/1 è uno degli esempi di programmazione dinamica.
Conclusioni
Possiamo concludere dicendo che sia il metodo greedy che la programmazione dinamica vengono utilizzati per trovare la soluzione ottimale al problema da un insieme di soluzioni fattibili. La principale differenza tra loro è che il metodo Greedy non riesamina mai le sue selezioni mentre la programmazione dinamica è inversa, il che assicura anche di fornire una soluzione ottimale al problema.
