Podstawy programowania dynamicznego

5.1 Definicja programowania dynamicznego.

Programowanie dynamiczne (Dynamic Programming, DP) — to metoda optymalizacji, która jest używana do rozwiązywania skomplikowanych problemów poprzez rozbijanie ich na prostsze podzadania. Programowanie dynamiczne jest efektywne dla zadań, które można podzielić na nakładające się podzadania z optymalną strukturą.

Zasady działania:

1. Optymalna podstruktura:

Zadanie posiada optymalną podstrukturę, jeśli jego optymalne rozwiązanie można zbudować z optymalnych rozwiązań jego podzadań. Oznacza to, że można rozwiązać duży problem, rozwiązując kilka mniejszych podzadań.

2. Nakładające się podzadania:

Zadanie ma nakładające się podzadania, jeśli jego podzadania powtarzają się kilka razy podczas rozwiązywania. Programowanie dynamiczne efektywnie rozwiązuje zadania z nakładającymi się podzadaniami poprzez zapamiętywanie wyników już rozwiązanych podzadań (memoizacja).

3. Memoizacja i tabulacja:

Memoizacja (top-down): Rekurencyjne podejście, w którym wyniki podzadań są przechowywane w pamięci, aby uniknąć ponownych obliczeń.

Tabulacja (bottom-up): Iteracyjne podejście, w którym wyniki podzadań są obliczane i przechowywane w tabeli (zwykle w tablicy) i używane do obliczenia ostatecznego wyniku.

Przykłady zadań rozwiązywanych metodą programowania dynamicznego

5.2 Problem plecakowy.

Zadanie:

Mamy zbiór przedmiotów, każdy z wagą i wartością. Trzeba wybrać przedmioty do plecaka o ograniczonej pojemności, aby zmaksymalizować całkowitą wartość.

Ważne! W odróżnieniu od podobnego zadania, które można dobrze rozwiązać algorytmem zachłannym, w tym zadaniu nie można dzielić przedmiotów.

Rozwiązanie:

Tworzymy tabelę, gdzie wiersze odpowiadają przedmiotom, a kolumny — możliwej pojemności plecaka. Wartość w komórce reprezentuje maksymalną wartość dla danej liczby przedmiotów i pojemności.

Złożoność czasowa: O(n * W), gdzie n — liczba przedmiotów, W — pojemność plecaka.

Przykład kodu w 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 Problem najkrótszej ścieżki

Zadanie:

Znajdź najkrótsze ścieżki między wszystkimi parami wierzchołków w ważonym grafie.

Rozwiązanie:

Używana jest tabela, gdzie wiersze i kolumny odpowiadają wierzchołkom grafu. Wartość w komórce reprezentuje najkrótszą odległość między dwoma wierzchołkami.

Złożoność czasowa: O(V^3), gdzie V — liczba wierzchołków

Przykład kodu w 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 Porównanie programowania dynamicznego z innymi metodami.

Porównanie z metodą brute force:

Złożoność czasowa:

• Brute force: często ma wykładniczą złożoność czasową (na przykład, O(2^n) dla problemu Fibonacciego).
• Programowanie dynamiczne: zmniejsza złożoność czasową do wielomianowej (na przykład, O(n) dla problemu Fibonacciego).

Złożoność przestrzenna:

• Brute force: może używać mniej pamięci, ale koszty czasowe są wysokie.
• Programowanie dynamiczne: może używać więcej pamięci do przechowywania wyników pośrednich (na przykład, O(n) dla problemu Fibonacciego z memoizacją), ale wygrywa na czasie.

Porównanie z algorytmami zachłannymi (greedy algorithms):

Optymalność:

• Algorytmy zachłanne: nie zawsze znajdują globalnie optymalne rozwiązanie, ale działają szybciej i są prostsze do wdrożenia.
• Programowanie dynamiczne: znajduje globalnie optymalne rozwiązanie, ale wymaga więcej zasobów obliczeniowych.

Przykłady zadań:

• Algorytmy zachłanne: problem plecakowy z ułamkami (fractional knapsack), minimalne drzewo rozpinające (MST).
• Programowanie dynamiczne: problem plecakowy (całkowitoliczbowy), najdłuższy wspólny podciąg (LCS).