TEMA 4: PROGRAMACIÓN DINÁMICA
1. Introducción a la Programación Dinámica
Definición Richard Bellman en los años 50, la programación dinámica es un
enfoque algorítmico utilizado para resolver problemas de decisión que pueden
descomponerse en subproblemas superpuestos.
Aplicación: Se emplea en problemas de optimización combinatoria, donde los
problemas pueden dividirse en subproblemas solapados.
Método: Utiliza tablas para almacenar resultados intermedios y construir
soluciones de manera eficiente.
Cálculo de Coeficientes Binomiales
El coeficiente binomial :
Complejidad
La complejidad del algoritmo para calcular los coeficientes binomiales es O(n×k), ya
que necesitamos rellenar una tabla de tamaño n×k y cada operación toma un tiempo
constante. La complejidad espacial también es O(n×k) ya que utilizamos una tabla de
esos mismos tamaños.
2. Subproblemas Repetidos
Cuando resolvemos un problema de programación dinámica, frecuentemente nos
encontramos calculando la solución de los mismos subproblemas múltiples veces. Esto
ocurre especialmente en problemas donde la solución puede descomponerse en
subproblemas que se solapan.
Ejemplo visual: En el cálculo de un coeficiente binomial C(n,k), podemos ver
cómo se calculan subproblemas similares (por ejemplo, C(4,2) C(3,1) varias
veces en una estructura recursiva. Sin optimización, este proceso repite cálculos
de manera innecesaria.
Solución: Para evitar
recalcular
subproblemas,
almacenamos los
resultados
intermedios en una
tabla. Esto nos
permite reutilizar los resultados ya calculados y evitar recomputar los mismos
subproblemas, logrando una solución más eficiente.
3. Almacenar Resultados Intermedios
Para evitar los cálculos repetidos, la programación dinámica utiliza una estructura de datos,
como una tabla bidimensional, para almacenar los resultados de subproblemas resueltos. Esta
tabla se suele rellenar de manera bottom-up (de abajo hacia arriba).
Estructura de la tabla: Para cada combinación de parámetros (como n y k en los
coeficientes
binomiales), se
guarda el resultado
del subproblema
correspondiente.
Luego, estos
valores
almacenados se
utilizan para
construir la
solución al
problema
4. Conceptos y Principios Básicos de Programación Dinámica
Subestructura Óptima: Una solución óptima al problema general contiene la solución
óptima de sus subproblemas. Esto se conoce como el Principio de Optimalidad de
Bellman.
Subproblemas Solapados: El problema se resuelve abordando cada subproblema una
sola vez, almacenando los resultados intermedios para reutilizarlos.
Principio de Optimalidad de Bellman: base fundamental para los problemas que
pueden resolverse mediante programación dinámica. Establece que:
Una solución óptima para un problema de varias etapas (un problema
compuesto por varios pasos o decisiones) incluye las soluciones óptimas de sus
subproblemas
Ejemplo: cambio de monedas
Descripción: Dado un conjunto ilimitado de monedas de diferentes denominaciones y
una cantidad M, se busca la forma de obtener M usando el número mínimo de monedas.
Función Objetivo: Minimizar el número de monedas empleadas.
Decisiones:
Usar o no una moneda de una determinada denominación.
Si se decide usarla, cuántas veces se debe usar o qué denominación elegir.
Ecuación de Bellman:
C(i,j) es el mínimo número de monedas necesarias para devolver j céntimos
usando solo monedas de tipo hasta i.
Se construye una tabla desde el valor 0 hasta M, y se rellena evaluando cada
posible denominación y cantidad de moneda.
Enunciado: Supongamos que tienes monedas de 1, 3 y 4 unidades, y deseas hacer un
cambio exacto para obtener una cantidad total de 6 unidades con el mínimo número de
monedas posible.
5. Enfoque Top-Down con Funciones de Memoria (Memoización)
Descripción: Utiliza una estrategia recursiva que sólo calcula los subproblemas
necesarios y guarda cada solución en una tabla para evitar recálculos futuros.
Memorización: Cada celda de la tabla de soluciones comienza vacía y se rellena
solo cuando se calcula el subproblema correspondiente, reutilizando luego el
valor almacenado.
6. Problema de la Mochila 0-1
Definición del Problema
Descripción: Dado un conjunto de objetos, cada uno con un peso y un valor, y
una capacidad máxima de peso WWW de la mochila, el objetivo es maximizar
el valor total de los objetos seleccionados sin exceder la capacidad.
Función Objetivo: Maximizar el valor de los objetos en la mochila:
donde vj es el valor de cada objeto en la
solución S.
Estructura y Subproblemas
Subproblema: Sea V(i,j) el mayor valor que se puede obtener usando los
primeros i objetos y con capacidad j en la mochila.
Ejemplo del Problema de la Mochila 0-1:
Enunciado
Imaginemos que tenemos una mochila con una capacidad de 5 unidades de peso
y queremos maximizar el valor de los objetos que llevamos en ella.
