Programacion dinamica

Técnicas de diseño de algoritmos

Programación dinámica
Dra. Elisa Schaeffer
elisa.schaeffer@gmail.com

PISIS / FIME / UANL

Programaci´ n din´ mica– p. o a

Programación dinámica

o a En programaci´ n din´ mica, uno empieza a construir la solución desde las soluciones de los subproblemas más pequeños, guardando las soluciones en una forma sistemática para construir soluciones aproblemas mayores.
Típicamente las soluciones parciales están guardadas en un arreglo para evitar a tener que solucionar un subprobelma igual más tarde el la ejecución del algoritmo.

Programaci´ n din´ mica– p. o a

Problema de la mochila

El algoritmo pseudo-polinomial que vimos para el problema de la mochila es esencialmente un algoritmo de programación dinámica (PD). En general, lautilidad de PD está en problemas donde la solución del problema completo contiene las soluciones de los subproblemas — una situación que ocurre en algunos o problemas de optimizaci´ n.

Programaci´ n din´ mica– p. o a

Coeficientes binómicos

Si uno lo aplica de la manera dividir y conquistar, es necesario volver a calcular varias veces algunos coeficientes pequeños, llegando a la complejidadasintótica 2n n =Ω √ Ω k n Por guardar las

Sin embargo, por guardarlas, la complejidad de espacio crece.

soluciones parciales: O (nk).

Programaci´ n din´ mica– p. o a

Triángulo de Pascal

k n 0 1 2 3 4 5 6 7 8

0 1 1 1 1 1 1 1 1 1 1 1 2 3 4 5 6 7 8

2

3

4

5

6

7 8

1 3 6 10 15 21 28

1 4 1 10 5 1 20 15 6 1 35 35 21 7 1 56 70 56 28 8 1
Programaci´ n din´ mica– p. o aTriangulación

Dado: Un polígono convexo de n lados en formato de la
lista de los n + 1 puntos finales de sus lados en la dirección del reloj.

Pregunta: ¿Cuál división del polígono a triángulos
minimiza la suma de los largos de los lados de los triángulos?

Programaci´ n din´ mica– p. o a

Ejemplo con una solución factible

Programaci´ n din´ mica– p. o a

Observaciones

Elnúmero de los puntos es n + 1

Programaci´ n din´ mica– p. o a

Observaciones

El número de los puntos es n + 1 Cada uno de los n lados del polígono tiene n opciones de asignación a triángulos, incluyendo un tri´ ngulo a degenerado que consiste del lado sólo

Programaci´ n din´ mica– p. o a

Observaciones

El número de los puntos es n + 1 Cada uno de los n lados del polígono tiene nopciones de asignación a triángulos, incluyendo un tri´ ngulo a degenerado que consiste del lado sólo Uno de estos triángulos necesariamente pertenece a la triangulación óptima.

Programaci´ n din´ mica– p. o a

Observaciones

El número de los puntos es n + 1 Cada uno de los n lados del polígono tiene n opciones de asignación a triángulos, incluyendo un tri´ ngulo a degenerado que consistedel lado sólo Uno de estos triángulos necesariamente pertenece a la triangulación óptima. Lo que queda es triangular el área o las áreas que quedan afuera del triángulo elegida.

Programaci´ n din´ mica– p. o a

Las opciones

Programaci´ n din´ mica– p. o a

Método de solución

Examinar cada triangulación de cada lado, empezando del lado entre el primero y el segundo punto, y continuandorecursivamente para los otros lados del polígono. El “precio” de un triángulo degenerado es cero.

Programaci´ n din´ mica– p. 1 o a

Precio de triangulación

Suponemos que estamos triangulizando el polígono parcial definido por los puntos i − 1, i, . . . , j − 1, j. El precio de la triangulación óptima es Ti,j = 0, i=j m´ {Ti,k + Tk+1,j + w(i − 1, k, j)} , i = j ın

i≤k≤j−1

donde w(i− 1, k, j) es el costo del triángulo definido por los tres puntos i − 1, k y j.

Programaci´ n din´ mica– p. 1 o a

El algoritmo

Guardar en la tabla de los Ti,j cero ∀Ti,i , i = 1, . . . , n.

Programaci´ n din´ mica– p. 1 o a

El algoritmo

Guardar en la tabla de los Ti,j cero ∀Ti,i , i = 1, . . . , n. Completar la tabla diagonal por diagonal hasta llegar al elemento T1,n ....