Programación Dinámica

Ángel M. Carreras Jusino

MATH 6350

Profesor Balbino García Bernal

UNIVERSIDAD INTERAMERICANA DE PUERTO RICO

RECINTO DE SAN GERMÁN

Departamento de Matemáticas y Ciencias Aplicadas

Contenido

¿Qué es programación dinámica?

Comparación entre recursión y

programación dinámica

Historia

Ejemplos de aplicaciones

◦ Knapsack Problem

◦ Needleman–Wunsch algorithm

Algebraic Dynamic Programming

¿Qué es la Programación

Dinámica? Es una técnica algorítmica la cual está basada

usualmente en una fórmula recurrente y un (o varios) estado(s) inicial(es). Una sub-solución del problema es construida de las halladas previamente.

Es un método para resolver eficientemente una amplia gama de problemas de búsqueda y optimización que exhiben las características de sub-problemas superpuestos y subestructura óptima.◦ Se dice que un problema tiene sub-problemas

superpuestos si este puede ser descompuesto en sub-problemas que son reutilizados varias veces.

◦ Se dice que un problema tiene subestructura óptima si la solución óptima global puede ser construida a partir de soluciones óptimas de sub-problemas.

Comparación entre Recursión y

Programación Dinámica La diferencia esencial entre Recursión y

Programación dinámica es que la última

guarda los resultados intermedios

mientras la primera no lo hace. Esto

hace una gran diferencia al rendimiento

cuando una función recursiva es llamada

en repetidas ocasiones con los mismos

argumentos.

De hecho la Programación Dinámica no

es más que recursión con estrategia de

“caching”.

Historia

El término Programación Dinámica fue utilizado originalmente en los 1940’s por Richard Bellmanpara describir el proceso de resolver problemas donde se necesita encontrar las mejores decisiones una tras otra.

Para 1953, el refinó esto a su significado moderno, el cual se refiere específicamente a anidar pequeños problemas de decisión dentro de grandes decisiones, luego de esto el campo fue reconocido por la lEEE como un tópico de análisis de sistemas e ingeniería.

La contribución de Bellman es recordada en el nombre de la ecuación de Bellman, un resultado central de programación dinámica que replantea un problema de optimización en forma recursiva.

Historia

Originalmente la palabra “programación” en “programación dinámica” no tenía conexión con la programación de computadoras y en cambio venía del término “programación matemática”.

Sin embargo, actualmente muchos problemas de optimización son mejor resueltos escribiendo programas de computadoras que implementa un algoritmo de programación dinámica, lo cual resulta mejor que llevar a cabo cientos de cálculos a mano.

Ejemplos de Aplicaciones

Knapsack Problem

Needleman–Wunsch Algorithm

Knapsack Problem

Knapsack Problem

El problema de la mochila (knapsack problem) consiste encontrar un subconjunto de productos que echar en una mochila de modo de maximizar el beneficio y no sobrepasar la capacidad de la mochila.

Se puede resumir el problema de la siguiente forma:

Donde l es la cantidad de objetos disponibles, bi es el beneficio que ofrece el objeto i, pi es el peso del objeto i, xi nos indica si colocamos o no el objeto i dentro de la mochila y P es el peso máximo que soporta la mochila.

maximizar bi x ii k

l

sujeto a pi xii k

l

P

con xi { 0 , 1} , k i l

Knapsack Problem

Digamos que tenemos l objetos con pesos p1, …,pl y beneficios b1, …,bl.

Definimos A(i, j) como el valor máximo que puede ser obtenido con los primeros i objetos pesando a lo más j.

Note que:

◦ A(0, j) = 0 y A(i, 0) = 0 para cualquier i ≤ l y j ≤ P.

◦ Si pi > j entonces A(i, j) = A(i – 1, j).

◦ Si pi ≤ j entonces A(i, j) tiene dos opciones incluir o no incluir el objeto i. Si no lo incluimos entonces tendrá un valor de A(i – 1, j).

Si lo incluimos entonces tendrá un valor de A(i – 1, j – pi) + bi.

Knapsack Problem

Expresado formalmente tenemos la

siguiente definición recursiva.

1

0 si 0 o 0

, 1, si

max 1, , , si

i

i i

i j

A i j A i j p j

A i j A i j j p b p j

Knapsack Problem

Ejemplo:

◦ Tenemos una caja que soporta 15 libras

en la cual vamos a colocar objetos para

vender. Hay disponibles tres objetos:

Objeto #1 pesa 9 libras y se vende a $38

Objeto #2 pesa 6 libras y se vende a $40

Objeto #3 pesa 5 libras y se vende a $24

◦ ¿Cuál es la ganancia máxima que

podemos obtener?

Mathematica

Knapsack Problem

Continuación ejemplo:

◦ La información recopilada del algoritmo

se puede resumir en la siguiente tabla:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

p1 9 0 0 0 0 0 0 0 0 0 38 38 38 38 38 38 38

p2 6 0 0 0 0 0 0 40 40 40 40 40 40 40 40 40 78

p3 5 0 0 0 0 0 24 40 40 40 40 40 64 64 64 64 78

Needleman–Wunsch

Algorithm

Needleman–Wunsch

Algorithm Uno de los problemas de todos los días en

Bioinformática es la comparación o alineamiento de secuencias. Necesitamos saber que tan similares son dos secuencias, permitiendo que haya pequeñas diferencias ya sea de reemplazo o de borrado entre una y otra.

El algoritmo de Needleman-Wunsch sirve para realizar alineamientos globales de dos secuencias.

Fue propuesto por primera vez en 1970, por Saul Needleman y Christian Wunsch.

El algoritmo calcula puntajes de similitud global entre dos secuencias.

Needleman–Wunsch

Algorithm Ejemplo

◦ Consideremos el conjunto {A, G, C, T} sobre el cual definimos dos cadenas s1 = GAATTCAGTTA y s2 = GGATCGA.

◦ El objetivo del algoritmo es alinearlas de tal forma que puedan identificarse huecos, inserciones o cambios en los caracteres de las secuencias.

◦ Para el ejemplo un alineamiento es el siguiente:

s

Needleman–Wunsch

Algorithm El algoritmo de Needleman-Wunsch

busca generar el alineamiento para lo

cual coloca todas las posibles

combinaciones de las dos secuencias s1

y s2 más una fila y columna de ceros

para la generación de la recursividad,

en una matriz M.

Definiendo a n = |s1| y a m = |s2| entonces

la matriz M será de tamaño (m +1) (n +

1).

Needleman–Wunsch

Algorithm Luego procedemos a rellenar la matriz

M para lo cual primero definimos una

matriz S de semejanza de caracteres.

Needleman–Wunsch

Algorithm Si definimos Si;j como una función tal que devuelve la

similitud de los caracteres de la posición i de s1 y j de s2y a W como la penalización por hueco que en este caso es simplemente 0, tendremos listo las funciones necesarias para llenar la matriz M.

Para proceder a rellenar M tendrán la siguiente ley de formación:

Donde:◦ Indica la coincidencia o no coincidencia

de los caracteres de las secuencias.

◦ Indica la suma en horizontal más la penalización por hueco.

◦ Indica la suma en vertical más la penalización por hueco.

, 1, 1 , , 1 1,max , ,

i j i j i j i j i jM M S M W M W

1, 1 ,i j i jM S

, 1i jM W

1,i jM W

Needleman–Wunsch

Algorithm

Needleman–Wunsch

Algorithm

Needleman–Wunsch

Algorithm

Needleman–Wunsch

Algorithm

Needleman–Wunsch

Algorithm

Needleman–Wunsch

Algorithm

Needleman–Wunsch

Algorithm El procedimiento siguiente es describir

el patrón que se dibuja desde el

extremo inferior derecho de la matriz

M y se avanza a la izquierda o a la

izquierda y arriba tomando siempre el

valor que le precedió al construir M.

Needleman–Wunsch

Algorithm

Needleman–Wunsch

Algorithm

Needleman–Wunsch

Algorithm

Needleman–Wunsch

Algorithm

Needleman–Wunsch

Algorithm

G A A T T C A G T T A

| | | | | |

G G A ― T C ― G ― ― A

Dando el alineamiento:

Algebraic Dynamic

Programming Algebraic Dynamic Programming

(ADP) es un nuevo método para

diseñar e implementar, afinar, probar y

enseñar algoritmos de Programación

Dinámica.

Comparado con el modelo

tradicional, el ADP provee un nivel

mucho mayor de

abstracción, ayudando a resolver

problemas mas sofisticados con

mejores oportunidades de éxito.

Referencias

Algebraic Dynamic Programinghttp://bibiserv.techfak.uni-bielefeld.de/adp/

Dynamic Programming Tutorial for DNA sequence alignment http://www.avatar.se/molbioinfo2001/dynprog/dynamic.html

Introduction to Dynamic Programminghttp://20bits.com/articles/introduction-to-dynamic-programming/

Operations Research Models & Methods http://www.me.utexas.edu/~jensen/ORMM/methods/unit/dynamic/index.html

Wikipedia http://en.wikipedia.org/wiki/Dynamic_programming