Programación Dinámica
Martín Eduardo Chacón Orduño - 351840
3CC2
Carlos Esteban Barragán Bernal - 359299
Análisis de Algoritmos
Luz Mariam García Castillo - 348409
Norma Leticia Mendez Mariscal
Leonardo Franco Bulkley - 377288
01/10/2021
Concepto
Es un concepto desarrollado por
Richard Bellman, matemático y
economista.
La programación dinámica resuelve
problemas de optimización
dividiéndolos en subproblemas más
pequeños, resolviendo cada
subproblema una vez y almacenando
sus soluciones para poder
re-utilizarlas y combinarlas para
resolver el problemas más grande.
● Es utilizada en áreas en las que
tenemos problemas que
pueden dividirse en
¿En qué contexto subproblemas más pequeños y
sus soluciones se utilizan para
se utiliza? resolver problemas más
grandes.
Problemas que se pueden resolver
La PD nos permite resolver problemas que
cuenten con dos propiedades fundamentales:
● Subestructura óptima.
● Superposición de subproblemas.
● Optimización.
● Conteo.
● Decisión.
● Secuenciación.
¿En qué consiste?
● Definir los subproblemas.
● Resolver los subproblemas.
● Almacenar las soluciones.
● Construir la solución al problemas
original.
● Optimización.
Principios ● Mayor uso de memoria - Menor
costo de tiempo.
● Memorization.
Número de fibonacci
Memorization
EJEMPLO DETALLADO:
Secuencia común más larga o Longest Common Subsequence (LCS)
Cadena 1: "A", "B", "C", "AB", "AC",
"BD", "AB", "BA", "BDB",
Definición del problema: "ABCBDAB" "CAB", "BCAB", etc.
● Dados dos strings, encontrar la
longitud de la subsecuencia
común más larga (LCS).
● Una subsecuencia común es
aquella que aparece en ambos
strings en el mismo orden, pero Cadena 2: "B", "D", "C", "A", "BD",
no necesariamente de manera "BC", "BA", "CAB", "CBA",
consecutiva. "BDCAB" etc.
Problema tarea:
Problema de la Mochila (Knapsack Problem)
Llenar una mochila con objetos, cada uno con un peso y un valor, de tal forma que el valor total sea el
máximo posible, sin superar la capacidad (peso máximo) de la mochila.
Ejemplo
● Número de objetos n: 4
● Capacidad de la mochila W: 5
● Pesos de los objetos: w=[2,3,4,5]
● Valores de los objetos: v=[3,4,5,6]
Utilizaremos una tabla que guardará el valor máximo que se puede obtener para
cada capacidad de mochila y cada objeto.
Paso 1: Definición de la Ecuación de Recurrencia
La ecuación de recurrencia se define de la siguiente manera:
1. Si el peso del objeto i es mayor que la capacidad actual w, no podemos incluir este objeto. Así
que el valor máximo en este caso es el mismo que el valor máximo sin este objeto:
K[i][w]=K[i−1][w]K
2. Si el peso del objeto i es menor o igual que la capacidad actual w, tenemos dos opciones:
● No incluir el objeto iii: K[i][w]=K[i−1][w]K[i][w]
● Incluir el objeto iii: K[i][w]=v[i]+K[i−1][w−w[i]]
3. La ecuación completa es: K[i][w]=max(K[i−1][w],v[i]+K[i−1][w−w[i]])
Uso y ●
●
Como se usa
Áreas y aplicación
aplicaciones ● pros y contras
Objetivo de la programación dinámica
El objetivo general es descomponer
problemas que se puedan en partes más
pequeñas y evitar que se repitan dentro
del problema global. Resolviendo esos
subproblemas y reutilizar las soluciones
de los subproblemas cuando sea
necesario, en lugar de re-calcularlas cada
vez.
Objetivo de la programación dinámica
Para realizar el análisis de problemas que se pueden
resolver a través de la técnica de la programación
dinámica, existen varios algoritmos de solución.
Entre ellos se encuentran:
● El problema de la mochila
● Cálculo de los números de Fibonacci
● La subsecuencia común máxima
● El problema del camino de mínimo costo
● Multiplicación de una secuencia de matrices
Objetivo de la programación dinámica
Problema de la mochila (Knapsack Problem):
● Seleccionar objetos con un valor y peso dados para maximizar el valor total sin exceder la capacidad de la mochila, Se
utiliza programación dinámica en el caso 0-1, con una complejidad de O(n⋅W), donde n es el número de objetos y W
es la capacidad.
Subsecuencia común máxima (Longest Common Subsequence, LCS):
● Encontrar la subsecuencia más larga que aparece en dos secuencias en el mismo orden, pero no necesariamente
[Link] programación dinámica con una complejidad de O(m⋅n)), donde mmm y nnn son las longitudes de
las secuencias.
Camino de mínimo costo (Minimum Cost Path):
● Encontrar el camino con el costo más bajo desde un punto inicial a un destino en una matriz o [Link]ón
dinámica con complejidad O(m⋅n) para una matriz de tamaño m×n
Pros:
● Eficiencia en el tiempo de ejecución: Al almacenar
las soluciones de los subproblemas, evitando
recalcular resultados ya obtenidos, lo que puede
acelerar el tiempo de ejecución.
● Simplificación de problemas complejos: Esta
técnica permite abordar problemas difíciles
dividiéndolos en partes más simples, facilitando su
comprensión y solución.
● Garantía de soluciones óptimas: La programación
dinámica está diseñada para encontrar la solución
óptima de un problema, siempre que este pueda ser
dividido en sub problemas con soluciones óptimas
combinables
Contras:
● Elevado consumo de memoria: Almacenar las
soluciones de todos los subproblemas puede requerir
una cantidad considerable de memoria, especialmente
en problemas de gran tamaño
● Aplicabilidad limitada: No todos los problemas
pueden ser resueltos mediante programación
dinámica; es necesario que el problema tenga
subestructura óptima .
● Complejidad en la implementación: Aunque la idea
detrás de la programación dinámica es sencilla, su
implementación puede ser complicada.
CONCLUSIÓN
La programación dinámica nos ayuda en el diseño de algoritmos
eficientes para resolver problemas complejos que pueden
descomponerse en subproblemas más simples. Aprovechando los
principios de subestructura óptima y la memorización esta técnica
nos permite optimizar el tiempo de ejecución y reducir la
redundancia de los cálculos. Todo esto permite que la
programación dinámica sea una estrategia esencial para abordar
problemas complejos de manera eficiente y efectiva.
Bibliografía
● Kariuki, C. (2024, May 17). Programación dinámica: Qué es, cómo funciona y recursos de aprendizaje. Geekflare
Spain. [Link]
● 4.12. Programación dinámica — Solución de problemas con algoritmos y estructuras de datos. (n.d.).
[Link]
● Nicolas Gomez Cerinza. (2024). FAEDIS. [Link].
[Link]
VzdGlnYWNpb25fZGVfb3BlcmFjaW9uZXNfaWkvdW5pZGFkXzQv#slide_1
● LifeDer. (s.f.). Programación dinámica: Qué es, características y ejemplos. Recuperado el 30 de septiembre de 2024, de
[Link]
● GeeksforGeeks. (s.f.). Dynamic Programming. Recuperado el 30 de septiembre de 2024, de
[Link]
