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

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

Programación Dinámica
Programación Dinámica

optimalidad de de Bellman
Bellman

Introducción
 Introducción
Elementos de la programación dinámica
 Elementos de la programación dinámica
 Principio de
Principio de optimalidad
Definición recursiva de la solución óptima
 Definición recursiva de la solución óptima
 Cálculo de la solución óptima
Cálculo de la solución óptima
Ejemplos
 Ejemplos
 Multiplicación encadenada de matrices
Multiplicación encadenada de matrices
Subsecuencia de mayor longitud (LCS)
 Subsecuencia
de mayor longitud (LCS)
Selección de actividades con pesos
 Selección de actividades con pesos
 Problema de la mochila
Problema de la mochila
Caminos mínimos: Algoritmos de Floyd y Bellman
 Caminos mínimos: Algoritmos de Floyd y
 Distancia de edición
Distancia de edición
 Aplicaciones
Aplicaciones

Bellman--FordFord

11

Programación Dinámica
Programación Dinámica

Esta técnica se aplica sobre problemas que presentan
Esta técnica se aplica sobre problemas que presentan
las siguientes características:
las siguientes características:

 Subproblemas

Subproblemas optimales
optimales: : La solución óptima a un
La solución óptima a un
problema puede ser definida en función de soluciones
problema puede ser definida en función de soluciones
problema puede ser definida en función de soluciones
problema puede ser definida en función de soluciones
óptimas a
óptimas a subproblemas

subproblemas de tamaño menor.
de tamaño menor.

 Solapamiento entre

subproblemas: : Al plantear la
Solapamiento entre subproblemas
Al plantear la
solución recursiva del problema, un mismo problema
solución recursiva del problema, un mismo problema
se resuelve más de una vez.
se resuelve más de una vez.

Programación Dinámica
Programación Dinámica

bottom--up):up):

Enfoque ascendente (
Enfoque ascendente (bottom
Primero se calculan las soluciones óptimas para
 Primero se calculan las soluciones óptimas para
problemas de tamaño pequeño.
problemas de tamaño pequeño.
Luego, utilizando dichas soluciones, encuentra
 Luego, utilizando dichas soluciones, encuentra
soluciones a problemas de mayor tamaño.
soluciones a problemas de mayor tamaño.
soluciones a problemas de mayor tamaño.
soluciones a problemas de mayor tamaño.

Clave: Memorización
Clave: Memorización

subproblemas en en

Almacenar las soluciones de los
Almacenar las soluciones de los subproblemas
alguna estructura de datos para reutilizarlas
alguna estructura de datos para reutilizarlas
posteriormente. De esa forma, se consigue un
posteriormente. De esa forma, se consigue un
algoritmo más eficiente que la fuerza bruta, que
algoritmo más eficiente que la fuerza bruta, que
resuelve el mismo
resuelve el mismo subproblema

subproblema una y otra vez.
una y otra vez.

22

33

Programación Dinámica
Programación Dinámica

Memorización
Memorización
Para evitar calcular lo mismo varias veces:
Para evitar calcular lo mismo varias veces:
 Cuando se calcula una solución, ésta se almacena.
Cuando se calcula una solución, ésta se almacena.
Antes de realizar una llamada recursiva para un
 Antes de realizar una llamada recursiva para un
subproblema
subproblema Q, se comprueba si la solución ha sido
subproblema
subproblema Q, se comprueba si la solución ha sido
Q, se comprueba si la solución ha sido
Q, se comprueba si la solución ha sido
obtenida previamente:
obtenida previamente:
Si no ha sido obtenida, se hace la llamada recursiva
 Si no ha sido obtenida, se hace la llamada recursiva
y, antes de devolver la solución, ésta se almacena.
y, antes de devolver la solución, ésta se almacena.
Si ya ha sido previamente calculada, se recupera la
 Si ya ha sido previamente calculada, se recupera la
solución directamente (no hace falta calcularla).
solución directamente (no hace falta calcularla).

 Usualmente, se utiliza una matriz que se rellena
Usualmente, se utiliza una matriz que se rellena
conforme las soluciones a los
subproblemas son
son
conforme las soluciones a los subproblemas
calculados (espacio vs. tiempo).
calculados (espacio vs. tiempo).

Programación Dinámica
Programación Dinámica

Uso de la programación dinámica:
Uso de la programación dinámica:

1.1. Caracterizar la estructura de una solución óptima.
Caracterizar la estructura de una solución óptima.

2.2. Definir de forma recursiva la solución óptima.
2.2. Definir de forma recursiva la solución óptima.
Definir de forma recursiva la solución óptima.
Definir de forma recursiva la solución óptima.

3.3. Calcular la solución óptima de forma ascendente.
Calcular la solución óptima de forma ascendente.

4.4. Construir la solución óptima a partir de los datos
Construir la solución óptima a partir de los datos
almacenados al obtener soluciones parciales.
almacenados al obtener soluciones parciales.

44

55

Estrategias de diseño
Estrategias de diseño

Algoritmos greedy:
Algoritmos
greedy:

Se Se construye
un un criterio

construye la la solución
criterio de de optimización

optimización local.
local.

solución incrementalmente

incrementalmente, , utilizando
utilizando

Programación dinámica
Programación
dinámica::

descompone el el problema

Se Se descompone
problema en en subproblemas
subproblemas
construyendo la la solución
solapados
solapados y se
soluciones
soluciones de de esosesos subproblemas
subproblemas..

y se vava construyendo

solución con

con laslas

Divide y vencerás
Divide y
vencerás::
Se Se descompone
independientes y se
independientes
esosesos subproblemas
subproblemas..

descompone el el problema

problema en en subproblemas
subproblemas

y se combinan

combinan laslas soluciones

soluciones dede

Principio de Optimalidad
Principio de
Optimalidad

Para poder emplear programación dinámica, una
Para poder emplear programación dinámica, una
secuencia óptima debe cumplir la condición de que
secuencia óptima debe cumplir la condición de que
cada una de sus
cada una de sus subsecuencias
subsecuencias también sea óptima:
también sea óptima:

Dado un problema P con n elementos,
Dado un problema P con n elementos,
Dado un problema P con n elementos,
Dado un problema P con n elementos,
si la secuencia óptima es e
si la secuencia óptima es e11ee22......eekk...e...enn entonces:
entonces:
 ee11ee22......eekk es solución al problema P considerando los
es solución al problema P considerando los

k primeros elementos.
k primeros elementos.

 eek+1k+1...e...enn es solución al problema P considerando los
es solución al problema P considerando los

elementos desde k+1 hasta n.
elementos desde k+1 hasta n.

66

77

Principio de Optimalidad
Principio de
Optimalidad

En otras palabras:
En otras palabras:

La solución óptima de cualquier instancia no trivial
La solución óptima de cualquier instancia no trivial
de un problema es una combinación de las soluciones
de un problema es una combinación de las soluciones
óptimas de sus subproblemas
óptimas de sus
óptimas de sus
óptimas de sus subproblemas
subproblemas..
subproblemas..

 Se busca la solución óptima a un problema
Se busca la solución óptima a un problema
como un proceso de decisión “multietápico
como un proceso de decisión “

multietápico”.”.

 Se toma una decisión en cada paso, pero ésta
Se toma una decisión en cada paso, pero ésta
depende de las soluciones a los
depende de las soluciones a los subproblemas
subproblemas
que lo componen.
que lo componen.

88

Principio de Optimalidad
Principio de
Optimalidad

Un poco de historia:
Un poco de historia: Bellman

Bellman, años 50…
, años 50…

Enfoque está inspirado en la teoría de control:
Enfoque está inspirado en la teoría de control:
Se obtiene la política óptima para un problema de
Se obtiene la política óptima para un problema de
control con n etapas basándose en una política óptima
control con n etapas basándose en una política óptima
para un problema similar, pero de n--1 etapas.
para un problema similar, pero de n
para un problema similar, pero de n
para un problema similar, pero de n--1 etapas.
1 etapas.
1 etapas.

Etimología: Programación dinámica = Planificación temporal
Etimología: Programación dinámica = Planificación temporal

En una época “hostil” a la investigación matemática,
En una época “hostil” a la investigación matemática, Bellman
Bellman
buscó un nombre llamativo que evitase posibles confrontaciones:
buscó un nombre llamativo que evitase posibles confrontaciones:
 “it's impossible to use dynamic in a pejorative sense”
“it's impossible to use dynamic in a pejorative sense”
 “something not even a Congressman could object to”
“something not even a Congressman could object to”

Richard E. Bellman: “Eye of the Hurricane: An Autobiography”
Richard E. Bellman: “Eye of the Hurricane: An Autobiography”

99

Principio de Optimalidad
Principio de
Optimalidad

Principio de
Principio de Optimalidad
[[Bellman, R.E.: “Dynamic Programming”. Princeton University Press, 1957]
Bellman, R.E.: “Dynamic Programming”. Princeton University Press, 1957]

Optimalidad de de Bellman
Bellman

política óptima
cuales sea el
cuales sea el

óptima tiene
sea el estado
sea el estado

estado inicial
estado inicial

inicial y la
inicial y la

tiene la la propiedad

propiedad de de queque, ,

decisiones restantes

restantes deben
respecto al al estado

deben constituir
estado resultante

con respecto

y la decisión
y la decisión

decisión inicial
decisión inicial

inicial, ,
inicial, ,
constituir unauna solucíón
solucíón
de la primera
resultante de la
primera

““UnaUna política
seansean cuales
seansean cuales
laslas decisiones
óptima
óptima con
decisión
decisión”.”.

problema queque puede

puede descomponerse
descomponerse

En En Informática

, un problema

Informática, un
de de estaesta forma se dice
optimales (la base de los
optimales
programación
programación dinámica
dinámica).).

forma se di