Swappa : Uni / Glossario Programmazione dinamica e Greedy

Torna alla pagina di Algoritmi e strutture dati

---

 :: Glossario Programmazione dinamica e Greedy ::

Programmazione dinamica e greedy

Fasi per risolvere un problema

1. Classificazione del problema
2. Caratterizzazione della soluzione
3. Tecnica di progetto
4. Utilizzo di strutture dati

Classificazione del problema:

Problemi decisionali: Il dato di ingresso soddisfa una certa proprietà?
Esempio: Stabilire se un grafo è connesso
Problemi di ricerca: Spazio di ricerca (insieme di soluzioni possibili) e soluzione ammissibile (soluzione che rispetta certi vincoli).
Esempio: posizione di una sottostringa in una stringa.

Caratterizzazione della soluzione:

Definire la soluzione dal punto di vista matematico. Le caratteristiche formali della soluzione possono suggerire una possibile tecnica.

Tecnica di progetto:

1. Divide-et-impera: Un problema viene suddiviso in sotto-problemi indipendenti, che vengono risolti ricorsivamente (top-down).
2. Programmazione dinamica: La soluzione viene costruita (bottom-up) a partire da un insieme di sotto-problemi potenzialmente ripetuti. I sotto-problemi in cui esso si può scomporre non sono indipendenti.
3. Greedy: Ad ogni passo si sceglie la soluzione che è localmente ottima.

Divide-et-impera vs programmazione dinamica:

Divide-et-impera: E' una tecnica ricorsiva vantaggiosa quando i sottoproblemi sono indipendenti altrimenti, gli stessi sottoproblemi possono venire risolti più volte.
Programmazione dinamica: E' una tecnica iterativa vantaggiosa quando ci sono sottoproblemi in comune.

Quando applicare la programmazione dinamica?

Sottostruttura ottimale: E' possibile combinare le soluzioni dei sottoproblemi per trovare la soluzione di un problema più grande. Le decisioni prese per risolvere un problema rimangono valide quando esso diviene un sottoproblema di un problema più grande.
Sottoproblemi ripetuti: Un sottoproblema può occorrere più volte.
Spazio dei sottoproblemi: Deve essere polinomiale.

Fasi della programmazione dinamica:

1. Definire la struttura di una soluzione ottima. Mostrare che una soluzione ottima si ottiene da soluzioni ottime di sottoproblemi.
2. Definire ricorsivamente il valore di una soluzione ottima. La soluzione ottima ad un problema contiene le soluzioni ottime ai sottoproblemi.
3. Calcolare il valore di una soluzione ottima con strategia "bottom up" (cioè calcolando prima le soluzioni dei casi più semplici).
4. Costruzione della soluzione ottima a partire dalle informazioni calcolate.

Algoritmi greedy

Ogni volta si fa la scelta migliore localmente.

Elementi della strategia greedy:

Sottostruttura ottima: Ogni soluzione ottima non elementare si compone di soluzioni ottime di sottoproblemi.
Prorietà della scelta greedy: La scelta ottima localmente non pregiudica la possibilità di arrivare a una soluzione globalmente ottima.

---

Torna alla pagina di Algoritmi e strutture dati