Schreiben von dynamischen Algorithmen

6.1 Grundlegende Schritte bei der Entwicklung dynamischer Algorithmen.

Grundlegende Schritte bei der Entwicklung dynamischer Algorithmen

1. Bestimmung der Teilprobleme:

Teile das Problem in kleinere Teilprobleme auf, die unabhängig voneinander gelöst werden können. Diese Teilprobleme sollten sich überschneiden, damit man die Ergebnisse vorheriger Berechnungen nutzen kann.

2. Identifikation der Zustände:

Bestimme alle möglichen Zustände, die bei der Lösung des Problems auftreten können. Die Zustände sollten alle erforderlichen Informationen beschreiben, um von einem Schritt zum nächsten zu gelangen.

3. Formulierung einer Rekursionsgleichung:

Bestimme, wie die Lösung des Problems für den aktuellen Zustand von den Lösungen für vorherige Zustände abhängt. Diese Gleichung sollte ausdrücken, wie man die optimale Lösung unter Nutzung der Lösungen für die Teilprobleme erhält.

4. Bestimmung der Basisfälle:

Bestimme die Basisfälle, für die die Lösung des Problems direkt bekannt ist, ohne dass weitere Berechnungen erforderlich sind.

5. Ausfüllen der Tabelle:

Erstelle eine Tabelle (in der Regel ein Array oder eine Matrix), um die Lösungen aller Teilprobleme zu speichern. Verwende die Rekursionsgleichung und die Basisfälle, um die Tabelle von unten nach oben oder oben nach unten auszufüllen.

6. Optimierung (Memoisierung):

Falls ein rekursiver Ansatz verwendet wird, füge Memoisierung hinzu, um die Ergebnisse der Teilprobleme zu speichern und deren erneute Berechnung zu vermeiden.

Zeit- und Speicherkomplexität dynamischer Algorithmen

Zeitkomplexität:

• Die Zeitkomplexität dynamischer Algorithmen wird normalerweise durch die Anzahl der Teilprobleme und die Zeit, die für die Berechnung jedes Teilproblems erforderlich ist, ausgedrückt.
• In den meisten Fällen beträgt die Zeitkomplexität O(n) oder O(n^2), wobei n die Größe der Eingabedaten ist.

Speicherkomplexität:

• Die Speicherkomplexität hängt von der Anzahl der Zustände ab, die gespeichert werden müssen.
• In einigen Fällen ist es möglich, die Speicherkomplexität durch Optimierungen zu reduzieren, z.B. durch Verringerung des Speicherverbrauchs auf O(n) oder O(1).

6.2 Das Rucksackproblem.

Das Rucksackproblem ist ein klassisches Problem der kombinatorischen Optimierung, das in verschiedenen Bereichen auftritt, einschließlich Informatik, Wirtschaft und Logistikmanagement. Das Hauptziel des Problems besteht darin, die begrenzten Ressourcen möglichst effizient zu nutzen.

Beschreibung des Rucksackproblems

Es gibt einen Rucksack, der ein bestimmtes Gewicht W tragen kann. Außerdem gibt es n Gegenstände, von denen jeder ein bestimmtes Gewicht wt[i] und einen Wert val[i] hat. Man muss entscheiden, welche Gegenstände genommen werden sollen, um den Gesamtwert der Gegenstände im Rucksack zu maximieren, ohne dessen Gewichtskapazität zu überschreiten.

Arten des Rucksackproblems

1. 0/1-Rucksackproblem (0/1 Knapsack Problem):

Jeder Gegenstand kann entweder ganz genommen oder nicht genommen werden (nicht teilweise).

2. Fraktionales Rucksackproblem (Fractional Knapsack Problem):

Jeder Gegenstand kann geteilt werden, und es kann ein beliebiger Teil davon genommen werden.

3. Mehrfach-Rucksackproblem (Multiple Knapsack Problem):

Es gibt mehrere Rucksäcke mit unterschiedlichen Gewichtsbeschränkungen.

Formulierung des 0/1-Rucksackproblems in algorithmischen Begriffen:

Rekursionsgleichung:

Für jeden Gegenstand i und für jedes mögliche Gewicht w (von 0 bis W), kann die optimale Lösung wie folgt ausgedrückt werden:

• Wenn der Gegenstand i nicht in den Rucksack aufgenommen wird, dann ist der optimale Wert gleich dem optimalen Wert für i − 1 Gegenstände und Gewicht w.
• Wenn der Gegenstand i in den Rucksack aufgenommen wird, dann ist der optimale Wert gleich dem Wert dieses Gegenstands plus dem optimalen Wert für i − 1 Gegenstände und Gewicht w − wt[i].

Zeit- und Speicherkomplexität

Zeitkomplexität:

Die Zeitkomplexität dieses Algorithmus beträgt O(nW), wobei n die Anzahl der Gegenstände und W die Kapazität des Rucksacks ist. Dies liegt daran, dass eine Tabelle der Größe n × W gefüllt werden muss.

Speicherkomplexität:

Die Speicherkomplexität beträgt ebenfalls O(nW), weil eine Tabelle benötigt wird, um die Zwischenergebnisse zu speichern.

Beispiele für die Implementierung des 0/1-Rucksackproblems

def knapsack(W, wt, val, n):
    # Erstellen einer Tabelle zum Speichern der Zwischenergebnisse
    dp = [[0 for x in range(W + 1)] for x in range(n + 1)]
        
    # Die Tabelle dp von unten nach oben ausfüllen
    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                dp[i][w] = 0
            elif wt[i - 1] <= w:
                dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w])
            else:
                dp[i][w] = dp[i - 1][w]
        
    return dp[n][W]
        
# Anwendungsbeispiel
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print(f"Maximaler Wert des Rucksacks: {knapsack(W, wt, val, n)}")
        

6.3 Das Münzwechselproblem.

Das Münzwechselproblem ist ein klassisches Problem der dynamischen Programmierung, das darin besteht, die minimale Anzahl von Münzen oder die Anzahl der Möglichkeiten zu finden, um einen bestimmten Geldbetrag aus einem Satz von Münzen mit bestimmten Nennwerten zusammenzustellen. Dieses Problem hat zwei Hauptvarianten:

Minimale Anzahl von Münzen (Minimum Coin Change Problem):

Die minimale Anzahl von Münzen finden, die insgesamt eine gegebene Summe bilden.

Anzahl der Möglichkeiten (Number of Ways to Make Change):

Die Anzahl der verschiedenen Möglichkeiten finden, um eine gegebene Summe aus einem gegebenen Satz von Münzen zusammenzustellen.

Variante 1. Minimale Anzahl von Münzen

Problemstellung

Gegeben:

• Ein unbegrenzter Satz von Münzen mit bestimmten Nennwerten.
• Ein Zielbetrag S.

Gesucht:

• Die minimale Anzahl von Münzen finden, die den Betrag S ergeben.

Lösung mit dynamischer Programmierung

Rekursionsgleichung:

• Sei dp[i] die minimale Anzahl von Münzen, die erforderlich ist, um die Summe i zu bilden.
• Für jede Münze c aus dem Münzsatz, wenn i ≥ c, dann: dp[i] = min(dp[i], dp[i − c] + 1)

Basisfälle:

• dp[0] = 0 (für die Summe 0 werden 0 Münzen benötigt).

Zeit- und Speicherkomplexität:

• Zeitkomplexität: O(n ⋅ S), wobei n die Anzahl der Münznennwerte und S der Zielbetrag ist.
• Speicherkomplexität: O(S), da ein Array benötigt wird, um die minimale Anzahl von Münzen für jede Summe von 0 bis S zu speichern.

Beispielimplementierung in Python

def min_coins(coins, S):
    dp = [float('inf')] * (S + 1)
    dp[0] = 0
        
    for i in range(1, S + 1):
        for coin in coins:
            if i >= coin:
                dp[i] = min(dp[i], dp[i - coin] + 1)
        
    return dp[S] if dp[S] != float('inf') else -1
        
# Anwendungsbeispiel
coins = [1, 2, 5]
S = 11
print(f"Minimale Anzahl von Münzen für die Summe {S}: {min_coins(coins, S)}")
        
        

Das Münzwechselproblem zeigt die Flexibilität der dynamischen Programmierung. Es wird zum Lernen und Untersuchen algorithmischer Techniken verwendet, da es zeigt, wie rekursive Beziehungen und Basisfälle genutzt werden können, um Probleme effizient zu lösen.