UNIVERSIDAD POLITÉCNICA Y ARTÍSTICA DEL PARAGUAY
FACULTAD DE ARTE Y TECNOLOGÍA
PROYECTO FINAL II
Tema: Trabajo Practico
Alumna: Luana A. Robles Centurion
Carrera: Ingeniería Civil
Profesor: Augusto Rafael De Llamas
San Lorenzo
2024
Programación Dinámica
Tema I: Defino
Programación Dinámica
La programación dinámica es una técnica de optimización matemática y
computacional utilizada para resolver problemas complejos al dividirlos en
subproblemas más pequeños y manejables. Su principal característica es
almacenar soluciones parciales para evitar la repetición de cálculos, logrando así
mayor eficiencia.
Terminología
- Subestructura Óptima: Propiedad donde la solución óptima del problema
principal se construye combinando soluciones óptimas de sus subproblemas.
- Superposición de Subproblemas: Reutilización de los mismos subproblemas
múltiples veces.
- Tabla (Memorización): Estructura de datos para almacenar soluciones
intermedias, como arreglos o matrices.
Tema II: Respondo
¿Qué es Algoritmo de Solución?
Un algoritmo de solución en programación dinámica establece una secuencia de
pasos que permite resolver un problema combinando soluciones de
subproblemas de manera eficiente. Estos algoritmos permiten abordar
problemas como la ruta más corta, optimización de inventarios, o asignación de
recursos.
Función de Valor Óptimo
Es una función que calcula el valor máximo o mínimo posible en un problema de
optimización. Se expresa mediante relaciones recursivas que definen cómo
combinar soluciones de subproblemas para obtener el resultado óptimo global.
Función de Política Óptima
La política óptima determina las decisiones o acciones que deben tomarse en
cada etapa para alcanzar el valor óptimo. Es particularmente útil en problemas
como cadenas de suministro o estrategias de inversión.
Diferencia entre Retroceso y Avance
- Retroceso: El cálculo se realiza desde el final hacia el principio, evaluando la
mejor solución posible desde el resultado deseado.
- Avance: El cálculo se realiza desde el principio hacia el final, resolviendo
subproblemas más pequeños y acumulando resultados parciales para resolver
el problema completo.
Tema III: Cita
Procedimiento de la Programación Dinámica
1. Identificar y definir los subproblemas.
2. Establecer una relación recursiva entre los subproblemas.
3. Resolver los subproblemas desde los más pequeños hacia los más grandes.
4. Almacenar las soluciones intermedias en una tabla para evitar cálculos
redundantes.
5. Combinar las soluciones para encontrar la solución óptima del problema
completo.
Características de un Problema de Programación Dinámica
- Subestructura Óptima: La solución global depende de las soluciones óptimas
de los subproblemas.
- Superposición de Subproblemas: Los subproblemas se resuelven
repetidamente, lo que permite almacenar sus soluciones.
- Eficiencia Computacional: La programación dinámica reduce significativamente
el tiempo de cálculo comparado con enfoques ingenuos.
Resolución de un Problema de Programación Dinámica
Por ejemplo, el Problema de la Mochila: Se busca maximizar el valor de los
objetos que pueden colocarse en una mochila con capacidad limitada.
1. Definición del Estado: f[i][w]: Máximo valor usando los primeros i objetos con
capacidad w.
2. Relación de Recurrencia: f[i][w] = max(f[i-1][w], f[i-1][w-peso[i]] + valor[i]).
3. Implementación: Construir una tabla para almacenar las soluciones parciales
y evitar cálculos repetidos.
Tipos de Programación Dinámica
- Determinística: Todos los datos son fijos y predecibles.
- Estocástica: Incorpora incertidumbre y probabilidades en los datos.
- Con Memorización: Usa estructuras de datos para almacenar soluciones
calculadas previamente.
- Tabular: Construye una tabla de abajo hacia arriba para resolver el problema.
Conceptos Fundamentales de Programación Dinámica
Estrategia de Divide y Vencerás vs. Programación Dinámica
Divide y vencerás: Divide el problema en subproblemas independientes y los
resuelve por separado (por ejemplo, la búsqueda binaria).
Programación dinámica: Divide el problema en subproblemas interdependientes,
almacenando soluciones para evitar redundancias.
Formulación Matemática
Un problema de programación dinámica puede representarse mediante
ecuaciones recursivas:
𝑓(𝑛)=min/max(𝑔(𝑠𝑢𝑏𝑝𝑟𝑜𝑏𝑙𝑒𝑚𝑎𝑠))
f(n)=min/max(g(subproblemas))
Donde 𝑔
g es una función que combina las soluciones de los subproblemas.
Relaciones de Transición
Estas relaciones definen cómo avanzar en la resolución de subproblemas. Por
ejemplo, en el problema de Fibonacci:
𝑓(𝑛)=𝑓(𝑛−1)+𝑓(𝑛−2)
f(n)=f(n−1)+f(n−2)
Áreas de Aplicación
Optimización de Rutas
Problemas como encontrar la ruta más corta en un grafo (algoritmo de Floyd-
Warshall).
Secuencias
Problema de la Subsecuencia Común Más Larga (LCS): Determina la mayor
subsecuencia compartida entre dos cadenas.
Problema de alineación de secuencias en bioinformática (por ejemplo, comparar
ADN).
Problemas de Inventario
Gestión de inventarios bajo incertidumbre o con costos variables.
Juegos y Estrategias
Resolver juegos como ajedrez o damas mediante evaluaciones dinámicas de
posiciones.
Ventajas y Limitaciones
Ventajas
Ahorra tiempo y recursos mediante la memorización.
Resuelve problemas que serían intratables con métodos ingenuos.
Fácil de implementar en lenguajes de programación modernos.
Limitaciones
Alto consumo de memoria en problemas con muchos subproblemas.
La formulación de relaciones de recurrencia puede ser compleja.
No todos los problemas tienen subestructura óptima o superposición de
subproblemas.
Ejemplos Clásicos de Problemas de Programación Dinámica
Fibonacci: Resolver la serie de Fibonacci utilizando memorización o tabulación.
Mochila (Knapsack): Maximizar el valor de objetos seleccionados bajo
restricciones de peso.
Triángulo de Números: Encontrar la ruta de suma mínima desde la cima hasta la
base de un triángulo numérico.
Problema del Cambio de Moneda: Minimizar el número de monedas necesarias
para alcanzar una cantidad específica.
Programación Dinámica y Algoritmos Voraces
Comparar cuándo usar programación dinámica y cuándo usar algoritmos
voraces:
Programación Dinámica: Se utiliza cuando hay superposición de subproblemas
y subestructura óptima.
Algoritmos Voraces: Se utiliza cuando las decisiones locales garantizan un
resultado global óptimo.
