Dominando Algoritmos: Programación Dinámica, Grafos y Backtracking en Python
Enviado por Chuletator online y clasificado en Informática y Telecomunicaciones
Escrito el en 
español con un tamaño de 13,14 KB
Algoritmos Fundamentales en Programación: Implementaciones y Conceptos
Programación Dinámica: Optimización de Problemas Complejos
La programación dinámica es una técnica poderosa para resolver problemas complejos dividiéndolos en subproblemas más pequeños y superpuestos, almacenando los resultados de estos subproblemas para evitar recálculos. A continuación, se presentan implementaciones de algoritmos clásicos que utilizan este paradigma.
Implementación de la Secuencia de Fibonacci
La secuencia de Fibonacci es un ejemplo clásico para ilustrar la programación dinámica, tanto con memoización (recursiva con caché) como con un enfoque iterativo.
Fibonacci con Memoización (Recursivo)
def fibonacci(n: int) -> int:
"""
Calcula el n-ésimo número de Fibonacci utilizando memoización.
"""
def _fibonacci_cache(n: int, cache: dict) -> int:
if n == 0:
return 0
elif n == 1:
return 1
elif n in cache:
return cache[n]
else:
resultado = _fibonacci_cache(n - 1, cache) + _fibonacci_cache(n - 2, cache)
cache[n] = resultado
return resultado
cache = {}
return _fibonacci_cache(n, cache)
Fibonacci con Programación Dinámica (Iterativo)
def fibonacci_dinamico(n: int) -> int:
"""
Calcula el n-ésimo número de Fibonacci utilizando programación dinámica iterativa.
"""
if n < 0:
raise ValueError("El número debe ser no negativo.")
if n == 0:
return 0
if n == 1:
return 1
cache = [0, 1]
for i in range(2, n + 1):
cache.append(cache[i - 1] + cache[i - 2])
return cache[n]
Cálculo del Coeficiente Binomial (Programación Dinámica)
El coeficiente binomial C(n, k) se puede calcular eficientemente utilizando una tabla de programación dinámica, basándose en la identidad de Pascal C(n, k) = C(n-1, k-1) + C(n-1, k).
def binomial_dinamico(n: int, k: int) -> int:
"""
Calcula el coeficiente binomial C(n, k) utilizando programación dinámica.
"""
if k < 0 or k > n:
return 0 # O manejar como error, dependiendo del contexto
def _matriz_binomial(n: int, k: int) -> list[list[int]]:
# Inicializa la matriz con ceros
matriz = [[0 for _ in range(k + 1)] for _ in range(n + 1)]
# Rellena la matriz usando la identidad de Pascal
for i in range(n + 1):
for j in range(min(i, k) + 1):
if j == 0 or i == j:
matriz[i][j] = 1
else:
matriz[i][j] = matriz[i - 1][j - 1] + matriz[i - 1][j]
return matriz
return _matriz_binomial(n, k)[n][k]
Problema de la Mochila (Programación Dinámica)
El problema de la mochila busca maximizar el valor total de los objetos que se pueden llevar en una mochila con una capacidad limitada. La siguiente implementación muestra una parte del enfoque de programación dinámica para resolverlo.
# Definición de objetos (ejemplo)
objetos_ejemplo = [{'nombre': 'Tablet', 'valor': 100, 'volumen': 1},
{'nombre': 'Laptop', 'valor': 300, 'volumen': 3},
{'nombre': 'Auriculares', 'valor': 50, 'volumen': 0.5}]
# Capacidades disponibles (ejemplo)
capacidades_ejemplo = [0.0, 0.5, 1.0, 1.5, 2.0, 2.5, 3.0, 3.5, 4.0]
# La matriz 'matriz' debe ser inicializada previamente,
# por ejemplo, con ceros o valores base para el problema de la mochila.
# matriz[i][j] representaría el valor máximo para los primeros 'i' objetos
# con una capacidad 'j'.
# Ejemplo de inicialización (simplificado para el fragmento):
# matriz = [[0 for _ in range(len(capacidades_ejemplo))] for _ in range(len(objetos_ejemplo) + 1)]
n = len(objetos_ejemplo)
# Este fragmento asume que 'matriz' y 'capacidades' están definidas y que 'objetos' es 'objetos_ejemplo'
# y que 'capacidades' es 'capacidades_ejemplo'.
# El bucle principal para la programación dinámica del problema de la mochila:
# for i in range(1, n + 1):
# for j in range(1, len(capacidades_ejemplo)):
# objeto_actual = objetos_ejemplo[i-1]
# capacidad_actual = capacidades_ejemplo[j]
#
# if objeto_actual['volumen'] <= capacidad_actual:
# # Encuentra la columna correspondiente a la capacidad restante
# anterior_capacidad_necesaria = capacidad_actual - objeto_actual['volumen']
# col = 0
# while col < len(capacidades_ejemplo) and capacidades_ejemplo[col] < anterior_capacidad_necesaria:
# col += 1
# # Asegurarse de no exceder los límites del índice
# if col >= len(capacidades_ejemplo):
# col = len(capacidades_ejemplo) - 1
#
# valor_con_objeto = objeto_actual['valor'] + matriz[i-1][col]
# matriz[i][j] = max(valor_con_objeto, matriz[i-1][j])
# else:
# matriz[i][j] = matriz[i-1][j]
#
# Nota: El fragmento original es incompleto y asume la existencia de 'matriz'.
# Se ha comentado para evitar errores de sintaxis/ejecución en un contexto aislado.
# El código original proporcionado es:
# objetos = [{'nombre': 'Tablet’, 'valor': 100, 'volumen': 1},../
# capacidades = [0.0, 0.5, 1.0, 1.5, 2.0, 2.5, 3.0, 3.5, 4.0]
# n = len(objetos)
# for i in range(1, n + 1):
# for j in range(1, len(capacidades)):
# if objetos[i-1]['volumen'] <= capacidades[j]:
# anterior = capacidades[j] - objetos[i-1]['volumen']
# col = 0
# while capacidades[col] < anterior:
# col += 1
# nuevo = objetos[i-1]['valor'] + matriz[i-1][col]
# matriz[i][j] = max(nuevo, matriz[i-1][j])
# else:
# matriz[i][j] = matriz[i-1][j]
Nota: El fragmento de código original para el problema de la mochila con programación dinámica estaba incompleto y asumía la existencia de variables como matriz y una definición más extensa de objetos. Se ha añadido un contexto y comentarios para clarificar su propósito.
Algoritmos de Grafos: Explorando Conexiones
Los algoritmos de grafos son fundamentales para resolver problemas de conectividad, rutas y redes. El algoritmo de Floyd-Warshall es un ejemplo clave para encontrar los caminos más cortos entre todos los pares de nodos.
Algoritmo de Floyd-Warshall para Caminos Más Cortos
El algoritmo de Floyd-Warshall calcula las distancias más cortas entre todos los pares de vértices en un grafo ponderado, que puede contener pesos de arista negativos, pero no ciclos negativos.
def floyd_warshall(grafo: dict) -> tuple[list[list[float]], list[list[str]]]:
"""
Implementa el algoritmo de Floyd-Warshall para encontrar los caminos más cortos
entre todos los pares de nodos en un grafo.
Args:
grafo: Un diccionario que representa el grafo de adyacencia.
Ej: {'A': {'B': 1, 'C': 4}, 'B': {'C': 2}, 'C': {}}
Returns:
Una tupla que contiene:
- Una matriz de distancias (float('inf') si no hay camino).
- Una matriz de caminos (el nodo predecesor en el camino más corto).
"""
nodos = {}
pos = 0
for v in grafo:
nodos[v] = pos
pos += 1
num_nodos = len(nodos)
distancias = [[float('inf')] * num_nodos for _ in range(num_nodos)]
caminos = [[None] * num_nodos for _ in range(num_nodos)]
# Inicialización de distancias y caminos
for origen_node in grafo:
i = nodos[origen_node]
distancias[i][i] = 0
caminos[i][i] = origen_node
for destino_node, peso in grafo[origen_node].items():
j = nodos[destino_node]
distancias[i][j] = peso
caminos[i][j] = origen_node
# Triple bucle principal de Floyd-Warshall
for k in range(num_nodos): # Nodo intermedio
for i in range(num_nodos): # Nodo de origen
for j in range(num_nodos): # Nodo de destino
if distancias[i][k] + distancias[k][j] < distancias[i][j]:
distancias[i][j] = distancias[i][k] + distancias[k][j]
caminos[i][j] = caminos[k][j]
return distancias, caminos
# Ejemplo de uso (no parte del código original, solo para contexto)
# grafo_ejemplo = {
# 'A': {'B': 1, 'C': 4},
# 'B': {'C': 2, 'D': 5},
# 'C': {'D': 1},
# 'D': {}
# }
# dist, path = floyd_warshall(grafo_ejemplo)
# print("Distancias:", dist)
# print("Caminos:", path)
Grafos Implícitos y la Técnica de Backtracking
Un grafo implícito es aquel para el que se dispone de una descripción de sus nodos y aristas de forma que se pueden construir partes relevantes del grafo a medida que progresa el recorrido. El ahorro de tiempo es considerable si el recorrido tiene éxito antes de haber construido todo el grafo. Asimismo, el ahorro de memoria es significativo si podemos descartar los nodos que ya han sido examinados. Para ello, se utiliza frecuentemente la técnica de Backtracking o recursividad intensiva.
En su forma básica, el método de Backtracking se asemeja a un recorrido en profundidad dentro de un árbol cuya existencia solo es implícita, y que denominaremos árbol de expansión. Este esquema se corresponde con las siguientes ideas clave:
- Al llegar a un nodo (al entrar en una llamada recursiva), se tiene una solución parcial formada por k – 1 etapas.
- Se generan todas las decisiones posibles a partir de la solución parcial actual.
- Para cada una de esas decisiones, se incorpora a la solución parcial (por lo que ahora tendrá k etapas) y se comprueba si se ha conseguido una solución total.
Resolución del Problema de la Mochila con Backtracking
El problema de la mochila también puede abordarse mediante backtracking, explorando todas las combinaciones posibles de objetos y podando las ramas que exceden la capacidad o no conducen a una solución óptima.
from typing import List, Dict, Union
# Definición de tipo para un objeto de la mochila
# Se usa Dict[str, Union[str, float]] para ser más preciso con los tipos
# o se podría definir una TypedDict si se usa Python 3.8+
# class ObjetoMochila(TypedDict):
# nombre: str
# valor: float
# volumen: float
def _objeto(nombre: str, valor: float, volumen: float) -> Dict[str, Union[str, float]]:
"""
Crea un diccionario que representa un objeto con nombre, valor y volumen.
"""
return {'nombre': nombre, 'valor': valor, 'volumen': volumen}
def sumar(mochila: List[Dict[str, Union[str, float]]], campo: str) -> float:
"""
Suma los valores de un campo específico (valor o volumen) de los objetos en la mochila.
"""
assert campo == 'valor' or campo == 'volumen', 'PRE: El campo debe ser "valor" o "volumen".'
suma = 0.0
for objeto in mochila:
suma += float(objeto[campo]) # Asegurarse de que la suma sea float
return suma
def mochila_backtracking(
objetos: List[Dict[str, Union[str, float]]],
capacidad: float,
solucion: List[Dict[str, Union[str, float]]],
candidatos: List[Dict[str, Union[str, float]]] = None,
nivel: int = 0
) -> None:
"""
Resuelve el problema de la mochila utilizando la técnica de backtracking.
Args:
objetos: Lista de todos los objetos disponibles.
capacidad: Capacidad máxima de la mochila.
solucion: Lista que contendrá la mejor combinación de objetos encontrada.
candidatos: Lista de objetos actualmente seleccionados en la solución parcial.
nivel: Nivel de recursión actual.
"""
if candidatos is None:
candidatos = []
# Si la solución actual es mejor que la mejor encontrada hasta ahora, actualiza
if sumar(candidatos, 'valor') > sumar(solucion, 'valor'):
solucion.clear()
solucion.extend(candidatos)
# Generamos los nuevos hijos (objetos que se pueden añadir)
volumen_actual = sumar(candidatos, 'volumen')
hijos = []
# Para evitar duplicados y asegurar que los objetos se consideren en orden
# se puede pasar un índice de inicio o usar un conjunto de objetos ya considerados.
# Aquí, se asume que 'objetos' es la lista original y 'candidatos' son los ya elegidos.
# Para evitar re-evaluar objetos ya considerados en niveles anteriores,
# se podría pasar 'objetos[nivel:]' o un índice de inicio.
# El código original no maneja esto explícitamente, así que se mantiene la lógica original
# de verificar 'not objeto in candidatos', que es menos eficiente para listas grandes.
for objeto in objetos:
if volumen_actual + float(objeto['volumen']) <= capacidad and objeto not in candidatos:
hijos.append(objeto)
# Backtracking: explorar cada hijo
for hijo in hijos:
candidatos.append(hijo)
mochila_backtracking(objetos, capacidad, solucion, candidatos, nivel + 1)
candidatos.pop() # Deshacer la elección para explorar otras ramas