Zastosowanie DP w rzeczywistych zadaniach

7.1 Optymalizacja dynamicznych algorytmów.

Optymalizacja dynamicznych algorytmów koncentruje się na poprawie ich efektywności czasowej i pamięciowej. Istnieje kilka podejść do optymalizacji, w tym użycie memoizacji, redukcja używanej pamięci i optymalizacja rekursji.

1. Memoizacja:

Memoizacja to technika, w której wyniki obliczeń są przechowywane, aby uniknąć wielokrotnych obliczeń tej samej podzadania.

Przykład:

W problemie wymiany monet, jeśli używamy podejścia rekursywnego, możemy przechowywać wyniki dla już obliczonych sum, aby uniknąć powtórnych obliczeń.

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. Rozwiązanie tablicowe (Bottom-Up):

Rozwiązanie tablicowe (bottom-up) buduje tabelę rozwiązań dla wszystkich możliwych podzadań od podstawowego przypadku do zadania docelowego. Pozwala to uniknąć nakładów związanych z rekursywnymi wywołaniami.

Przykład:

W problemie plecaka budowanie tabeli minimalnych ilości monet dla każdej sumy od 0 do 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. Redukcja używanej pamięci:

W niektórych zadaniach można zoptymalizować użycie pamięci, zmniejszając rozmiar tabeli lub tablicy używanej do przechowywania wyników pośrednich.

Przykład:

W problemie plecaka można użyć jednowymiarowej tablicy zamiast dwuwymiarowej tabeli, jeśli przechowujemy tylko bieżący i poprzedni wiersz.

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. Rekursja ogonowa:

Rekursja ogonowa to rekursywne wywołanie, które jest wykonywane na końcu funkcji. Pozwala to kompilatorowi lub interpreterowi optymalizować stos wywołań.

Przykład:

W zadaniu obliczania liczb Fibonacciego można użyć rekursji ogonowej z akumulatorem wyniku.

7.2 Zastosowanie dynamicznego programowania w rzeczywistych zadaniach.

Dynamiczne programowanie znajduje szerokie zastosowanie w różnych dziedzinach, w tym informatyce, ekonomii, bioinformatyce i badaniach operacyjnych. Oto kilka przykładów jego użycia w rzeczywistych zadaniach:

1. Optymalizacja tras i logistyka:

W zadaniach logistycznych i systemach transportowych dynamiczne programowanie jest używane do znajdowania optymalnych tras i minimalizacji kosztów.

Przykład:

Problem komiwojażera (Travelling Salesman Problem, TSP) — znalezienie najkrótszej trasy przechodzącej przez wszystkie miasta.

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. Wyrównanie sekwencji w bioinformatyce:

W bioinformatyce dynamiczne programowanie jest używane do wyrównywania sekwencji DNA, RNA i białek.

Przykład:

Algorytm Needleman-Wunsch do globalnego wyrównania sekwencji i algorytm Smith-Waterman do lokalnego wyrównania.

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. Obliczenia finansowe i planowanie ekonomiczne:

Dynamiczne programowanie jest stosowane do optymalizacji portfeli inwestycyjnych, zarządzania ryzykiem i planowania produkcji.

Przykład:

Problem wymiany monet i problem plecaka są używane do zarządzania aktywami i optymalnego rozdziału zasobów.

4. Zarządzanie zapasami i produkcją:

W produkcji i zarządzaniu zapasami dynamiczne programowanie pomaga optymalizować procesy i minimalizować koszty.

Przykład:

Model zarządzania zapasami (Inventory Management Model) do minimalizacji kosztów magazynowania i zamawiania produktów.

5. Uczenie maszynowe i sztuczna inteligencja:

W uczeniu maszynowym dynamiczne programowanie jest używane do optymalizacji algorytmów i znajdowania globalnych optimumów.

Przykład:

Algorytmy uczenia oparte na dynamicznym programowaniu, takie jak metoda wstecznej propagacji w sieciach neuronowych.