PROGRAMACION
DINAMICA
GRUPO 4
¿QUE ES PROGRAMACION
DINAMICA?
Proporciona un procedimiento
sistemático para encontrar la
combinación de decisiones que
maximice la efectividad total, al
descomponer el problema en etapas, las
que pueden ser completadas por una o
más formas (estados), y enlazando cada
etapa a través de cálculos recursivos
Objetivo de la Programacion Dinámica
La programación dinámica es encontrar la
solución óptima a un problema de optimización,
minimizando o maximizando una función
objetivo, mediante la resolución eficiente de
subproblemas repetidos.
Proporciona un procedimiento sistemático para encontrar la
combinación de decisiones que maximice la efectividad total, al
descomponer el problema en etapas, las que pueden ser completadas por
una o más formas (estados), y enlazando cada etapa a través de cálculos
recursivos.
La decisión a adoptar en cada etapa debe tener en cuenta el estado
actual y los costes que se deriven en las sucesivas etapas.
Engloba problemas secuenciales en los que hay que adoptar decisiones
en etapas sucesivas con el fin de optimizar una función objetivo.
ESQUEMA DE UNA ETAPA
qi Variable de estado en la etapa i
Xij Uno de los valores que puede adoptar la variable de
decisión “Xi” en la etapa i
Xi * Decisión óptima de la etapa i
La programación dinámica se utiliza principalmente para
resolver problemas de optimización:
La búsqueda del camino más corto.
Asignación de recursos limitados.
La maximizando de ganancias.
PARA RESOLVER PROBLEMAS DE
PROGRAMACIÓN DINÁMICA SE
NECESITA:
Un grado de creatividad
Un buen conocimiento de la estructura general
de los problemas de programación dinámica
para reconocer cuando un problema se puede
resolver por medio de estos procedimientos y
como esto se puede llevar a cabo.
CARACTERÍSTICAS DE LOS
PROBLEMAS DE PROGRAMACIÓN
DINÁMICA
El problema se puede dividir en etapas que
requieren una política de decisión en cada una.
Cada etapa tiene cierto número de estados
asociados a ella.
El efecto de la política de decisión en cada
etapa es transformar el estado actual en un
estado asociado con la siguiente etapa.
El procedimiento de solución está diseñado
para encontrar una política óptima para el
problema completo.
Existen dos formas de plantear la fórmula de
recursividad en los problemas de programación
dinámica:
• Recursividad de Retroceso: el problema se
resuelva partiendo de la última etapa hacia la primera.
• Recursividad de Avance: el problema se resuelve
partiendo de la primera etapa hacia la última.
Mayor eficiencia en la Programacion Dinamica
La programación dinámica es más eficiente porque evita
recalcular soluciones para subproblemas que ya han sido
resueltos. Al almacenar y reutilizar estas soluciones, se reduce
significativamente la complejidad temporal del algoritmo.
¿Cómo funciona la programación dinámica?
Resolver un problema usando programación dinámica involucra los siguientes
pasos:
1. Definir los sub-problemas: Un gran problema se divide en pequeños sub-problemas.
2. Resuelva los sub-problemas: Se trata de resolver el sub-problema identificado, lo
que se puede hacer mediante recursividad o iteración.
3. Almacene las soluciones: Las soluciones a los sub-problemas se almacenan para
que puedan reutilizarse.
4. Construya la solución al problema original: La solución al problema grande se
construye a partir de los sub-problemas que ya han sido calculados
¡GRACIAS POR SU
ATENCIÓN!
