Applicazione di DP in problemi reali

7.1 Ottimizzazione degli algoritmi dinamici.

L'ottimizzazione degli algoritmi dinamici mira a migliorare la loro efficienza temporale e spaziale. Esistono diversi approcci per l'ottimizzazione, tra cui l'uso della memoizzazione, la riduzione della memoria utilizzata e l'ottimizzazione della ricorsione.

1. Memoizzazione:

La memoizzazione è una tecnica in cui i risultati dei calcoli vengono memorizzati per evitare calcoli ripetuti dello stesso sottoproblema.

Esempio:

Nel problema del cambio di monete, se si utilizza un approccio ricorsivo, è possibile memorizzare i risultati delle somme già calcolate per evitare calcoli ripetuti.

def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 2:
        return 1
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]
        
        

2. Soluzione tabellare (Bottom-Up):

La soluzione tabellare (bottom-up) costruisce una tabella di soluzioni per tutti i possibili sottoproblemi dal caso base al problema target. Questo permette di evitare l'overhead delle chiamate ricorsive.

Esempio:

Nel problema dello zaino, si costruisce la tabella delle quantità minime di monete per ogni somma da 0 a S.

def fibonacci(n):
    dp = [0] * (n + 1)
    dp[1] = dp[2] = 1
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]
        
        

3. Riduzione della memoria utilizzata:

In alcuni problemi è possibile ottimizzare l'uso della memoria riducendo la dimensione della tabella o dell'array utilizzato per memorizzare i risultati intermedi.

Esempio:

Nel problema dello zaino, è possibile utilizzare un array unidimensionale invece di una tabella bidimensionale, memorizzando solo la riga corrente e la precedente.

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

4. Ricorsione di coda:

La ricorsione di coda è una chiamata ricorsiva che viene eseguita alla fine della funzione. Questo permette al compilatore o all'interprete di ottimizzare lo stack di chiamate.

Esempio:

Nel calcolo dei numeri di Fibonacci, è possibile utilizzare la ricorsione di coda con un accumulatore di risultati.

7.2 Applicazione della programmazione dinamica in problemi reali.

La programmazione dinamica trova ampio utilizzo in vari campi, tra cui l'informatica, l'economia, la bioinformatica e la ricerca operativa. Ecco alcuni esempi del suo utilizzo in problemi reali:

1. Ottimizzazione dei percorsi e logistica:

Nei problemi di logistica e sistemi di trasporto, la programmazione dinamica viene utilizzata per trovare i percorsi ottimali e minimizzare i costi.

Esempio:

Il problema del commesso viaggiatore (Travelling Salesman Problem, TSP) consiste nel trovare il percorso più breve che attraversa tutte le città.

def tsp(graph, start):
    n = len(graph)
    dp = [[None] * (1 << n) for _ in range(n)]

    def visit(city, visited):
        if visited == (1 << n) - 1:
            return graph[city][start]
        if dp[city][visited] is not None:
            return dp[city][visited]
        result = float('inf')
        for next_city in range(n):
            if visited & (1 << next_city) == 0:
                result = min(result, graph[city][next_city] + visit(next_city, visited | (1 << next_city)))
        dp[city][visited] = result
        return result

    return visit(start, 1 << start)

2. Allineamento delle sequenze in bioinformatica:

In bioinformatica, la programmazione dinamica viene utilizzata per allineare le sequenze di DNA, RNA e proteine.

Esempio:

L'algoritmo di Needleman-Wunsch per l'allineamento globale delle sequenze e l'algoritmo di Smith-Waterman per l'allineamento locale.

def lcs(X, Y):
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]
        

3. Calcoli finanziari e pianificazione economica:

La programmazione dinamica viene applicata per ottimizzare i portafogli di investimento, gestire i rischi e pianificare la produzione.

Esempio:

Il problema del cambio di monete e il problema dello zaino vengono utilizzati per la gestione degli attivi e la distribuzione ottimale delle risorse.

4. Gestione delle scorte e produzione:

Nella produzione e nella gestione delle scorte, la programmazione dinamica aiuta a ottimizzare i processi e minimizzare i costi.

Esempio:

Il modello di gestione delle scorte (Inventory Management Model) per minimizzare i costi di stoccaggio e ordine dei prodotti.

5. Apprendimento automatico e intelligenza artificiale:

Nell'apprendimento automatico, la programmazione dinamica viene utilizzata per ottimizzare gli algoritmi e trovare gli ottimi globali.

Esempio:

Algoritmi di apprendimento basati sulla programmazione dinamica, come il metodo di backpropagation nelle reti neurali.