La programació dinàmica és una tècnica de disseny d'algorismes que es basa en descompondre un problema complex en subproblemes més simples i resoldre'ls de manera òptima. Aquesta tècnica és especialment útil per a problemes d'optimització on les solucions es poden construir a partir de solucions òptimes de subproblemes més petits.
Conceptes Clau
-
Descomposició en Subproblemes:
- Dividir el problema original en subproblemes més petits i més manejables.
- Cada subproblema es resol una vegada i el resultat es guarda per evitar càlculs repetits.
-
Solapament de Subproblemes:
- Els subproblemes es solapen, és a dir, el mateix subproblema es resol múltiples vegades en un algorisme naïf.
- La programació dinàmica evita aquesta redundància emmagatzemant els resultats de subproblemes ja resolts.
-
Propietat de Subestructura Òptima:
- Una solució òptima del problema original es pot construir a partir de solucions òptimes dels seus subproblemes.
Estratègies de Programació Dinàmica
- Memòria (Top-Down)
En aquest enfocament, es comença resolent el problema original i es descompon en subproblemes més petits. Els resultats dels subproblemes es guarden en una estructura de dades (normalment una taula o diccionari) per evitar càlculs repetits.
Exemple: Fibonacci amb Memòria
def fibonacci_memo(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
return memo[n]
# Exemple d'ús
print(fibonacci_memo(10)) # Sortida: 55
- Taula (Bottom-Up)
En aquest enfocament, es resolen primer els subproblemes més petits i es construeixen solucions per a subproblemes més grans a partir d'aquestes solucions. Normalment, es fa ús d'una taula per guardar els resultats dels subproblemes.
Exemple: Fibonacci amb Taula
def fibonacci_table(n):
if n <= 1:
return n
fib = [0] * (n + 1)
fib[1] = 1
for i in range(2, n + 1):
fib[i] = fib[i-1] + fib[i-2]
return fib[n]
# Exemple d'ús
print(fibonacci_table(10)) # Sortida: 55Exemples Clàssics de Programació Dinàmica
- Problema de la Motxilla (Knapsack Problem)
Donat un conjunt d'objectes, cadascun amb un pes i un valor, determinar el nombre d'objectes que es poden incloure en una motxilla de capacitat màxima de pes per tal de maximitzar el valor total.
Implementació
def knapsack(weights, values, capacity):
n = len(values)
dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
for i in range(n + 1):
for w in range(capacity + 1):
if i == 0 or w == 0:
dp[i][w] = 0
elif weights[i-1] <= w:
dp[i][w] = max(values[i-1] + dp[i-1][w-weights[i-1]], dp[i-1][w])
else:
dp[i][w] = dp[i-1][w]
return dp[n][capacity]
# Exemple d'ús
weights = [1, 2, 3]
values = [10, 15, 40]
capacity = 5
print(knapsack(weights, values, capacity)) # Sortida: 55
- Problema del Camí Més Curt (Shortest Path Problem)
Donat un graf amb pesos no negatius, trobar el camí més curt des d'un node font a tots els altres nodes.
Implementació: Algorisme de Floyd-Warshall
def floyd_warshall(graph):
n = len(graph)
dist = [[float('inf')] * n for _ in range(n)]
for i in range(n):
for j in range(n):
if i == j:
dist[i][j] = 0
elif graph[i][j] != 0:
dist[i][j] = graph[i][j]
for k in range(n):
for i in range(n):
for j in range(n):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist
# Exemple d'ús
graph = [
[0, 3, float('inf'), 5],
[2, 0, float('inf'), 4],
[float('inf'), 1, 0, float('inf')],
[float('inf'), float('inf'), 2, 0]
]
print(floyd_warshall(graph))
# Sortida: [[0, 3, 7, 5], [2, 0, 6, 4], [3, 1, 0, 5], [5, 3, 2, 0]]Exercicis Pràctics
Exercici 1: Subseqüència Comuna Més Llarga (Longest Common Subsequence)
Donades dues cadenes, trobar la longitud de la subseqüència comuna més llarga.
Implementació
def lcs(X, Y):
m = len(X)
n = len(Y)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
for j in range(n + 1):
if i == 0 or j == 0:
dp[i][j] = 0
elif 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]
# Exemple d'ús
X = "AGGTAB"
Y = "GXTXAYB"
print(lcs(X, Y)) # Sortida: 4Exercici 2: Problema de la Cadena de Matrius (Matrix Chain Multiplication)
Donada una seqüència de matrius, determinar la manera més eficient de multiplicar-les.
Implementació
def matrix_chain_order(p):
n = len(p) - 1
dp = [[0] * n for _ in range(n)]
for l in range(2, n + 1):
for i in range(n - l + 1):
j = i + l - 1
dp[i][j] = float('inf')
for k in range(i, j):
q = dp[i][k] + dp[k+1][j] + p[i]*p[k+1]*p[j+1]
if q < dp[i][j]:
dp[i][j] = q
return dp[0][n-1]
# Exemple d'ús
p = [1, 2, 3, 4]
print(matrix_chain_order(p)) # Sortida: 18Resum
La programació dinàmica és una tècnica poderosa per resoldre problemes d'optimització que es poden descompondre en subproblemes més petits. Utilitzant estratègies com la memòria (top-down) i la taula (bottom-up), podem evitar càlculs repetits i millorar l'eficiència dels nostres algorismes. Els exemples clàssics com el problema de la motxilla i el problema del camí més curt il·lustren la utilitat d'aquesta tècnica en una àmplia varietat de problemes.
Curs d'Anàlisi i Disseny d'Algorismes
Mòdul 1: Introducció als Algorismes
Mòdul 2: Anàlisi d'Algorismes
- Anàlisi de Complexitat Temporal
- Anàlisi de Complexitat Espacial
- Cases de Complexitat: Millor, Pitjor i Promig
Mòdul 3: Estratègies de Disseny d'Algorismes
Mòdul 4: Algorismes Clàssics
- Cerca Binària
- Ordenació per Inserció
- Ordenació per Mescla (Merge Sort)
- Ordenació Ràpida (Quick Sort)
- Algorisme de Dijkstra
- Algorisme de Floyd-Warshall