Programación Dinámica.

Índice

1. Describir la Metodología de resolución de problemas “Programación Dinámicas”.

1.1 Aplicación y alcance.

1.2 Elementos característicos.

1.2 Esbozo del coste computacional.

2. Problema para realizar la resolución "más barata computacionalmente" y el cual se lleva a cabo mediante esta metodología. Aplicarla.

2.1 Identificación de los elementos característicos.

2.2 Demostración/Justificación de porque el problema es resoluble por esta vía.

2.3 Resumen del código y análisis del coste computacional.

3. Bibliografía.

______________________________________________________________

1. Describir la Metodología de resolución de problemas “Programación Dinámicas”.

El término “Programación Dinámica fue utilizado inicialmente en 1940, para resolver problemas de optimización matemática.

La programación dinámica es un método de optimización del cálculo de problemas y es utilizada en compiladores, consiste en solucionar cierto problema dividiéndolo en subproblemas más sencillos, calculando sus resultados y almacenándolos. Estos resultados posteriormente se

utilizan para la resolución del problema final.

Almacenar resultados de subproblemas es una gran ventaja en cálculos dónde se repiten las mismas operación múltiples veces, mediante el método de la programación dinámica estas operaciones sólo se realizan una vez y se guarda la solución.

Se dice de la programación dinámica que es un método para resolver problemas que exhiben propiedades de problemas sobrepuestos y estructura óptima.

1.1 Aplicación y alcance.

Dentro del contexto de la programación dinámica se usa el termino, "optimizar" que equivale a seleccionar (buscar) la "mejor" solución de entre muchas posibles alternativas. Este proceso de optimización puede ser visto como una secuencia de decisiones que nos proporcionan la solución correcta. Si, dada una subsecuencia de decisiones, siempre se conoce cuál es la decisión que debe tomarse a continuación para obtener la secuencia óptima, el problema es elemental y se resuelve trivialmente tomando una decisión detrás de otra, lo que se conoce como estrategia voraz.

A menudo, aunque no sea posible aplicar la estrategia voraz, se cumple el principio de optimalidad de Bellman : "dada una secuencia óptima de decisiones, toda subsecuencia de ella es, a su vez, óptima". En este caso sigue siendo posible el ir tomando decisiones elementales, en la confianza de que la combinación de ellas seguirá siendo óptima, pero será entonces necesario explorar muchas secuencias de decisiones para dar con la correcta, siendo aquí donde interviene la programación dinámica.

Contemplar un problema como una secuencia de decisiones equivale a dividirlo en subproblemas de talla inferior, en principio más fácilmente resolubles. Ello se enmarca en el método de Divide y Vencerás, técnica similar a la de Programación Dinámica.

Para diseñar un algoritmo de este tipo, se deben seguir los siguientes pasos:

- Se plantea la solución como una sucesión de soluciones. Se realiza una definición recursiva de la solución

- Se calcula el valor de la solución óptima de forma ascendente, mediante una tabla donde se almacenan las soluciones parciales, que posteriormente serán usadas en los cálculos restantes.

- Se construye la solución óptima utilizando la información de las tablas.

1.2 Elementos característicos.

* Ecuación recurrente: Va de las dificultades más pequeñas a las más complejas para calcular la solución.

* Determinación de los casos básicos: De los que partiremos para resolver el problema.

* Definición de las tablas: Usaremos estas para definir el algoritmo, y saber cómo se van rellenando las mismas.

* Estableceremos como se recompone la solución global a partir de los valores de las tablas.

1.3 Esbozo del coste computacional.

El coste computacional en este tipo de metodologías, depende de las características concretas del problema a resolver. De forma general dependerá del Tamaño de la tabla que utilicemos para su resolución por el tiempo que tardemos en rellenar cada elemento de esta.

Esta técnica se aplica sobre problemas que a simple vista necesitan un alto coste computacional (Posiblemente exponencial aproximadamente O(n2) ) donde la solución óptima a un problema puede ser definida en función de soluciones óptimas a subproblemas de tamaño menor, generalmente de forma recursiva y puede ocasionar el solapamiento entre subproblemas al plantear la solución recursiva, porque un mismo problema se resuelve más de una vez

Un aspecto importante a tener en cuenta sobre el coste, es que en los algoritmos de programación dinámica es que necesita una tabla para almacenar los resultados parciales, y esto puede ocupar mucha memoria.

2. Problema para realizar la resolución "más barata computacionalmente" y el cual se lleva a cabo mediante esta metodología. Aplicarla.

Un aficionado de la mecánica va a un taller. En el catálogo aparecen todas las configuraciones disponibles para montar su kart con el número de piezas que esto conlleva. El aficionado conoce el número mínimo de piezas que su kart necesita para la próxima carrera. Su objetivo es encontrar la puesta a punto (Conjunto de configuraciones) que cubra exactamente esa cantidad de piezas o las supere de forma mínima. Además, no quiere repetir configuraciones.

Diseña un algoritmo con programación dinámica que determine que configuraciones forman parte de la puesta a punto óptima y el número de piezas esta.

2.1 Identificación de los elementos característicos.

A continuación se procede a identificar los elementos característicos. D (i,j) contiene el número de piezas de la configuración optima considerando las i primeras configuraciones del catálogo como aquél con el menor número de piezas ( mayor o igual a j). Con lo que el valor que buscamos será el correspondiente a D(n, Piezas).

Para calcular D(i,j), podemos diferenciar dos casos:

- Si no se elige la configuración i del catálogo, entonces la puesta a punto elegida para D(i,j) contendrá exclusivamente configuraciones de 1 a i-1: D(i-1,j).

- Si se elige la configuración i, entonces el número de piezas total de la puesta a punto D(i,j) es ci + D (i-1, j-ci ), siendo ci el número de piezas de la nueva configuración.

La estructura de datos intermedia será una matriz D(1..n, 0…Piezas] con una fila por cada

configuración de la puesta a punto (desde 1 hasta n), y el número total de piezas en las columnas.

La función mín permite elegir la puesta a punto con el menor número de piezas. Así mismo, los valores +∞ garantizan que no se va a elegir una puesta a punto que tenga menos piezas que el mínimo necesario.

Hay que tener en cuenta algunos casos especiales:

1. D (1, j) = + ∞, j > c1, porque no es posible conseguir una puesta a punto de más de c1 piezas utilizando exclusivamente la configuración 1 (no se puede repetir la misma).

2. D (1, j) = c1, si 0 < j ≤ c1.  D (i, j) = 0, si j ≤ 0, pues la puesta a punto óptima con al menos 0 (o menos) piezas 6 consiste en no elegir ninguna configuración.

2.2 Demostración/Justificación de porque el problema es resoluble por esta vía.

Se propone un problema de optimización para determinar la puesta a punto con el mínimo número de piezas por encima de una cantidad. Tanto la metodología voraz como la programación dinámica se usan para resolver problemas de optimización, ya que permiten resolver problemas mediante una secuencia de decisiones. Aunque en este caso si lo resolviéramos por voraz, deberíamos tomar siempre la configuración que tenga menor beneficio. Pero en determinadas situaciones no se calcula la solución óptima. Por ello usaremos programación dinámica, que a diferencia de los algoritmos voraces, realizan varias secuencias de decisiones y solamente se sabe cuál es la mejor de ellas al final. Este problema es muy parecido al problema de la “Mochila 0/1”, ya que las configuraciones deben ser completas o son desechadas, pero en este caso queremos obtener el mínimo número de piezas, en vez de el máximo, con lo que el cálculo de la optimalidad cambia. Además, también disponemos del número mínimo de piezas necesario como valor de referencia. Con lo expuesto hasta ahora y complementándolo con el apartado 2.1, queda demostrado que el problema es resoluble por esta vía.

2.3 Resumen del código y análisis del coste computacional.

funcion Puesta_a_punto ( ci[1..n], tPiezas, Pap[1..n] )
crear D[ 1..n, 0..tPiezas ]

desde confi = 1 hasta n hacer
D[confi,0] = 0
desde nPiezas = 1 hasta tPiezas hacer
si confi = 1 Y nPiezas > ci [1] entonces D[confi,nPiezas] = + ∞

si no si confi = 1 entonces D[confi,nPiezas] = ci [1];

si no
si nPiezas < ci [confi] entonces
D[confi,nPiezas] = Minimo(D[confi-1,nPiezas], ci [confi])

si no  D[confi,nPiezas] = Minimo(D[confi-1,nPiezas],ci[confi]+D[confi- 1,nPiezas-ci[confi]])

fin si

fin desde

fin desde

si D[n,tPiezas] < + ∞ entonces
obtener_configuracion(D,ci,pap)  devolver D[n,tPiezas]

fin función

proc obtener_configuracion (D[1..n,0..tPiezas], ci[1..n],pap[1..n])

configuracion = 1
i = n
j = tPiezas

mientras i > 0 Y j > 0 hacer

si D[i,j]=D[i-1,j] entonces
i = i-1
si no

fin si


pap[configuracion ] = i; configuracion = configuracion + 1; j = j-ci[i]
i = i-1

fin mientras

si i = 1 ∧  j > 0 entonces
pap[configuracion ] = 1 ;
configuracion = configuracion +1

desde i = configuracion hasta n hacer pap[i] = -1
fin proc

La complejidad de este algoritmo viene determinado de forma aproximada por un orden de complejidad igual a O (n • tPiezas), debido a los dos bucles desde anidados en la función Puesta_a_punto  ya que  las  demás  operaciones  de esta  función  tienen  coste  constante,  y la funcion obtener_configuracion tiene un coste de O (N) debido el bucle desde i = configuracion hasta n hacer m[i] = -1.

3. Bibliografía.

- http://es.wikipedia.org/wiki/Programación_dinámica.

- Libro: “Teoría de colas y Programación Dinámica” de Isabel Plaza Idalgo.

- Universidad Complutense de Madrid, Facultad de Informática,http://www.fdi.ucm.es

-Universidad de Cataluña, Departamento de Lenguajes y sistemas informáticos, http://www.lsi.upc.es.

- Libro: “Análisis y diseño de Algoritmos”, Universidad de Málaga.