Programacion Dinamica

La programación dinámica.

Concepto

Frecuentemente para resolver un problema complejo se tiende a dividir este en subproblemas, más pequeños, resolver estos últimos (recurriendo posiblemente a nuevas subdivisiones) y combinar las soluciones obtenidas para calcular la solución del problema inicial. Puede ocurrir que la división natural del problema conduzca a un gran número de subejemplares idénticos. Si se resuelve cada uno de ellos sin tener en cuenta las posibles repeticiones, resulta un algoritmo ineficiente; en cambio si se resuelve cada ejemplar distinto una sola vez y se conserva el resultado, el algoritmo obtenido es mucho mejor.
Esta es la idea de la programación dinámica: no calcular dos veces lo mismo y utilizar normalmente una tabla de resultados que se va rellenando a medida que se resuelven los subejemplares.
La programación dinámica es un método ascendente. Se resuelven primero los subejemplares más pequeños y por tanto más simples. Combinando las soluciones se obtienen las soluciones de ejemplares sucesivamente más grandes hasta llegar al ejemplar original.

Ejemplo:

    Consideremos el cálculo de números combinatorios. El algoritmo sería:

    funcion C(n, k)

        si  k=0 o k=n entonces devolver 1

        si no devolver C(n-1, k-1) + C(n-1, k)

    Ocurre que muchos valores C(i, j), con i<n y j<k se calculan y recalculan varias veces.

Un fenómeno similar ocurre con el algoritmo de Fibonacci.

La programación dinámica se emplea a menudo para resolver problemas de optimización que satisfacen el principio de optimalidad: en una secuencia óptima de decisiones toda subsecuencia ha de ser también óptima.

Ejemplo: Si el camino más corto de Madrid a Barcelona pasa por Zaragoza, la parte del camino de Madrid a Zaragoza ha de ser necesariamente el camino mínimo entre estas dos ciudades.

Podemos aplicar esta técnica  en:

•     Camino mínimo en un grafo orientado
•     Arboles de búsqueda óptimos

·         La programación dinámica es un enfoque general para la solución de problemas en los que es necesario tomar decisiones en etapas sucesivas. Las decisiones tomadas en una etapa condicionan la evolución futura del sistema, afectando a las situaciones en las que el sistema se encontrará en el futuro (denominadas estados), y a las decisiones que se plantearán en el futuro.

·         Conviene resaltar que a diferencia de la programación lineal, el modelado de problemas de programación dinámica no sigue una forma estándar. Así, para cada problema será necesario especificar cada uno de los componentes que caracterizan un problema de programación dinámica.

·         El procedimiento general de resolución de estas situaciones se divide en el análisis recursivo de cada una de las etapas del problema, en orden inverso, es decir comenzando por la última y pasando en cada iteración a la etapa antecesora. El análisis de la primera etapa finaliza con la obtención del óptimo del problema.

 MODELOS DE PROGRAMACIÓN DINÁMICA

Existen tres modelos diferentes manejados por WINQSB.

* Problema de la diligencia (Stagecoach Problem)

* Problema de la mochila (Snapsack Problem)

* programación de producción e inventarios (Production and Inventory Scheduling)

Es una técnica que parte del principio de no calcular dos veces la misma información, por lo tanto se utilizan estructuras de almacenamiento como vectores, tablas, arreglos, archivos, con el fin de almacenarlos resultados parciales, que contribuyan a la solución final.

Este algoritmo evita calcular dos veces la misma información, manteniendo una tabla de resultados conocidos, la cual se va llenando a medida que seresuelven los subcasos. Es una técnica ascendente que normalmente, empieza por los subcasosmás pequeños y más sencillos.Combinando sus soluciones, obtenemoslas respuestas para los subcasos cada vez mayores, hasta que llegamosa la solucióndel caso original.

La programación dinámica se aplica no solo por razones de eficiencia, sino porque permite resolver de manera eficiente problemas que no se pueden resolver por otras metodologías.

El mayor número de aplicaciones se encuentra en problemas que requieren optimización, ya que se pueden hallar múltiples soluciones y así evaluarlas para hallar la óptima.