Grundlagen der dynamischen Programmierung

5.1 Definition der dynamischen Programmierung.

Dynamische Programmierung (Dynamic Programming, DP) – ist eine Optimierungsmethode, die verwendet wird, um komplexe Probleme zu lösen, indem sie in einfachere Teilprobleme zerlegt werden. Dynamische Programmierung wird effektiv bei Problemen eingesetzt, die in überlappende Teilprobleme mit optimaler Teilstruktur zerlegt werden können.

Arbeitsprinzipien:

1. Optimale Teilstruktur:

Ein Problem hat eine optimale Teilstruktur, wenn die optimale Lösung aus den optimalen Lösungen seiner Teilprobleme aufgebaut werden kann. Das bedeutet, dass man ein großes Problem lösen kann, indem man mehrere kleinere Teilprobleme löst.

2. Überlappende Teilprobleme:

Ein Problem hat überlappende Teilprobleme, wenn seine Teilprobleme mehrmals während des Lösungsprozesses wiederkehren. Dynamische Programmierung löst solche Probleme effektiv durch das Speichern der Ergebnisse bereits gelöster Teilprobleme (Memoization).

3. Memoization und Tabellierung:

Memoization (top-down): Rekursiver Ansatz, bei dem die Ergebnisse der Teilprobleme gespeichert werden, um wiederholte Berechnungen zu vermeiden.

Tabellierung (bottom-up): Iterativer Ansatz, bei dem die Ergebnisse der Teilprobleme berechnet und in einer Tabelle (meistens Array) gespeichert werden und zur Berechnung des Endergebnisses verwendet werden.

Beispiele für Probleme, die mit der Methode der dynamischen Programmierung gelöst werden

5.2 Das Rucksackproblem.

Problem:

Es gibt eine Menge an Gegenständen, jeder mit Gewicht und Wert. Es müssen Gegenstände für einen Rucksack mit begrenzter Tragkraft ausgewählt werden, um den Gesamtwert zu maximieren.

Wichtig! Im Gegensatz zu einer ähnlichen Aufgabe, die gut mit einem Greedy-Algorithmus gelöst wurde, dürfen die Gegenstände bei diesem Problem nicht aufgeteilt werden.

Lösung:

Es wird eine Tabelle erstellt, bei der Zeilen den Gegenständen und Spalten den möglichen Kapazitäten des Rucksacks entsprechen. Der Wert in einer Zelle stellt den maximalen Wert für diese Anzahl von Gegenständen und Kapazität dar.

Zeitkomplexität: O(n * W), wobei n die Anzahl der Gegenstände und W die Kapazität des Rucksacks ist.

Beispielcode 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 Das Problem des kürzesten Weges

Problem:

Finde die kürzesten Wege zwischen allen Paaren von Knoten in einem gewichteten Graphen.

Lösung:

Es wird eine Tabelle verwendet, bei der Zeilen und Spalten den Knoten des Graphen entsprechen. Der Wert in einer Zelle stellt die kürzeste Entfernung zwischen zwei Knoten dar.

Zeitkomplexität: O(V^3), wobei V die Anzahl der Knoten ist

Beispielcode 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 Vergleich der dynamischen Programmierung mit anderen Methoden.

Vergleich mit der Methode der brutalen Gewalt (brute force):

Zeitkomplexität:

• Brute force: hat oft eine exponentielle Zeitkomplexität (z. B. O(2^n) für das Fibonacci-Problem).
• Dynamische Programmierung: reduziert die Zeitkomplexität auf polynomial (z. B. O(n) für das Fibonacci-Problem).

Speicherkomplexität:

• Brute force: kann weniger Speicher verwenden, aber die Zeitkosten sind hoch.
• Dynamische Programmierung: kann mehr Speicher für die Speicherung von Zwischenergebnissen verwenden (z. B. O(n) für das Fibonacci-Problem mit Memoization), hat aber einen Zeitvorteil.

Vergleich mit der Methode der Greedy-Algorithmen (greedy algorithms):

Optimalität:

• Greedy-Algorithmen: finden nicht immer die global optimale Lösung, aber arbeiten schneller und sind einfacher zu implementieren.
• Dynamische Programmierung: findet die global optimale Lösung, benötigt aber mehr Rechenressourcen.

Beispiele für Probleme:

• Greedy-Algorithmen: Das Rucksackproblem mit Brüchen (fractional knapsack), Minimaler spannbaum (MST).
• Dynamische Programmierung: Das Rucksackproblem (ganzzahlig), längste gemeinsame Teilsequenz (LCS).