Publicado el 16 de Abril del 2017
1.444 visualizaciones desde el 16 de Abril del 2017
726,1 KB
31 paginas
Creado hace 14a (08/01/2011)
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
Comentarios de: Análisis y Diseño de Algoritmos - Programación Dinámica (0)
No hay comentarios