Basi della Programmazione Dinamica

5.1 Definizione di programmazione dinamica.

La programmazione dinamica (Dynamic Programming, DP) è un metodo di ottimizzazione utilizzato per risolvere problemi complessi dividendo un problema in sottoproblemi più semplici. La programmazione dinamica è efficace per problemi che possono essere divisi in sottoproblemi sovrapposti con una struttura ottimale.

Principi di funzionamento:

1. Sottostruttura ottimale:

Un problema ha una sottostruttura ottimale se la soluzione ottimale può essere costruita a partire dalle soluzioni ottimali dei suoi sottoproblemi. Questo significa che si può risolvere un grande problema risolvendo diversi sottoproblemi più piccoli.

2. Sottoproblemi sovrapposti:

Un problema ha sottoproblemi sovrapposti se i suoi sottoproblemi vengono ripetuti più volte nel processo di risoluzione del problema. La programmazione dinamica risolve efficacemente problemi con sottoproblemi sovrapposti memorizzando i risultati dei sottoproblemi già risolti (memoizzazione).

3. Memoizzazione e tabulazione:

Memoizzazione (top-down): un approccio ricorsivo in cui i risultati dei sottoproblemi sono salvati in memoria per evitare calcoli ripetuti.

Tabulazione (bottom-up): un approccio iterativo in cui i risultati dei sottoproblemi sono calcolati e salvati in una tabella (solitamente un array) e utilizzati per calcolare il risultato finale.

Esempi di problemi risolvibili con la programmazione dinamica:

5.2 Problema dello zaino.

Problema:

Si ha un insieme di oggetti, ognuno con un peso e un valore. Bisogna scegliere gli oggetti per uno zaino con capacità limitata al fine di massimizzare il valore totale.

Importante! A differenza di un problema simile che si risolveva bene con un algoritmo goloso, in questo problema gli oggetti non possono essere frazionati.

Soluzione:

Si crea una tabella in cui le righe corrispondono agli oggetti e le colonne alla possibile capacità dello zaino. Il valore nella cella rappresenta il valore massimo per un dato numero di oggetti e capacità.

Complessità temporale: O(n * W), dove n è il numero di oggetti, W è la capacità dello zaino.

Esempio di codice in Python:

def knapsack(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
            
    for i in range(1, n + 1):
        for w in range(W + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
            else:
                dp[i][w] = dp[i - 1][w]
            
    return dp[n][W]
        
        

5.3 Problema di trovare il percorso minimo

Problema:

Trovare i percorsi minimi tra tutte le coppie di vertici di un grafo pesato.

Soluzione:

Si usa una tabella in cui righe e colonne corrispondono ai vertici del grafo. Il valore nella cella rappresenta la distanza minima tra due vertici.

Complessità temporale: O(V^3), dove V è il numero di vertici

Esempio di codice in Python:

def floyd_warshall(graph):
    v = len(graph)
    dist = list(map(lambda i: list(map(lambda j: j, i)), graph))
            
    for k in range(v):
        for i in range(v):
            for j in range(v):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
            
    return dist
        
        

5.4 Confronto tra programmazione dinamica e altri metodi.

Confronto con il metodo forza bruta (brute force):

Complessità temporale:

• Forza bruta: spesso ha una complessità temporale esponenziale (ad esempio, O(2^n) per il problema di Fibonacci).
• Programmazione dinamica: riduce la complessità temporale a polinomiale (ad esempio, O(n) per il problema di Fibonacci).

Complessità spaziale:

• Forza bruta: può usare meno memoria, ma i tempi di esecuzione sono elevati.
• Programmazione dinamica: può utilizzare più memoria per memorizzare i risultati intermedi (ad esempio, O(n) per il problema di Fibonacci con memoizzazione), ma è più veloce.

Confronto con il metodo degli algoritmi golosi (greedy algorithms):

Ottimalità:

• Algoritmi golosi: non sempre trovano la soluzione ottimale globale, ma sono più veloci e semplici da implementare.
• Programmazione dinamica: trova la soluzione ottimale globale, ma richiede più risorse computazionali.

Esempi di problemi:

• Algoritmi golosi: problema dello zaino frazionario (fractional knapsack), albero di copertura minimo (MST).
• Programmazione dinamica: problema dello zaino (intero), sottosequenza comune massima (LCS).