Dynamic Programming

Programación Dinámica
Análisis y Diseño de Algoritmos

Programación Dinámica
Introducción
Elementos de la programación dinámica
Principio de optimalidad de Bellman
Definición recursiva de lasolución óptima
Cálculo de la solución óptima

Ejemplos
Multiplicación encadenada de matrices
Subsecuencia de mayor longitud (LCS)
Selección de actividades con pesos
Problema de la mochilaCaminos mínimos: Algoritmos de Floyd y Bellman-Ford
BellmanDistancia de edición

Aplicaciones

1

Programación Dinámica
Esta técnica se aplica sobre problemas que presentan
las siguientescaracterísticas:
Subproblemas optimales: La solución óptima a un
optimales:
problema puede ser definida en función de soluciones
óptimas a subproblemas de tamaño menor.
Solapamiento entre subproblemas:Al plantear la
subproblemas:
solución recursiva del problema, un mismo problema
se resuelve más de una vez.

2

Programación Dinámica
Enfoque ascendente (bottom-up):
(bottomPrimero secalculan las soluciones óptimas para
problemas de tamaño pequeño.
Luego, utilizando dichas soluciones, encuentra
soluciones a problemas de mayor tamaño.
Clave: Memorización
Almacenar las soluciones delos subproblemas en
alguna estructura de datos para reutilizarlas
posteriormente. De esa forma, se consigue un
algoritmo más eficiente que la fuerza bruta, que
resuelve el mismo subproblema una yotra vez.
3

Programación Dinámica
Memorización
Para evitar calcular lo mismo varias veces:
Cuando se calcula una solución, ésta se almacena.
Antes de realizar una llamada recursiva para unsubproblema Q, se comprueba si la solución ha sido
obtenida previamente:
Si no ha sido obtenida, se hace la llamada recursiva
y, antes de devolver la solución, ésta se almacena.
Si ya ha sidopreviamente calculada, se recupera la
solución directamente (no hace falta calcularla).
Usualmente, se utiliza una matriz que se rellena
conforme las soluciones a los subproblemas son
4
calculados...