Programación Dinámica

PROGRAMACIÓN DINÁMICA


Objetivos:
Conocer los conceptos básicos de esta técnica algorítmica.
Conocer el principio de optimalidad.
Mostrar algoritmos en los que se aplica la programación dinámica.


INTRODUCCIÓN

Una forma razonable y comúnmente empleada de resolver un problema es definir o caracterizar su solución en términos de las soluciones de subproblemas del mismo. Esta idea,cuando se emplea recursivamente, proporciona métodos eficientes de solución para problemas en los que los subproblemas son versiones más pequeñas del problema original.
Una técnica de diseño de algoritmos, que sigue esta idea, es la conocida como “Divide y Vencerás” la cual consiste en descomponer cada problema en subproblemas independientes, resolver cada uno de ellos (quizás empleando el mismométodo) y combinar estas soluciones parciales para obtener una solución global.
Desde el punto de vista de la complejidad de los algoritmos que se obtienen por este procedimiento, lo mejor es que todos los subproblemas tengan dimensión similar y que la suma de estas sea lo menor posible.
Posiblemente la manera más natural de resolver estos problemas es mediante un algoritmo recursivo. Sinembargo, el tiempo de ejecución de la solución recursiva, normalmente de orden exponencial y por tanto impracticable, puede mejorarse substancialmente mediante la Programación Dinámica.
El inconveniente se presenta cuando los subproblemas obtenidos no son independientes sino que existe solapamiento entre ellos; entonces es cuando una solución recursiva no resulta eficiente por la repetición decálculos que conlleva. En estos casos es cuando la Programación Dinámica nos puede ofrecer una solución aceptable. La eficiencia de esta técnica consiste en resolver los subproblemas una sola vez, guardando sus soluciones en una matriz para su futura utilización.
La Programación Dinámica no sólo tiene sentido aplicarla por razones de eficiencia, sino porque además presenta un método capaz de resolverproblemas cuya solución ha sido abordada por otras técnicas y ha fracasado.
Donde tiene mayor aplicación es en la resolución de problemas de optimización. En este tipo de problemas se pueden presentar distintas soluciones, cada una con un valor, y lo que se desea es encontrar la solución de valor óptimo (máximo o mínimo).

PRINCIPIO DE OPTIMALIDAD

La solución de problemas mediante estatécnica se basa en el llamado “principio de optimalidad” enunciado por Richard Bellman en 1957 y que dice:
“En una secuencia de decisiones óptima toda subsecuencia ha de ser también óptima”.
Lo que significa que es posible ir tomando decisiones elementales, en la confianza de que la combinación de ellas seguirá siendo óptima, aunque tal vez sea necesario explorar muchas secuencias de decisiones paradar con la correcta.
Hemos de observar que aunque este principio parece evidente no siempre es aplicable y por tanto es necesario verificar que se cumple para el problema en cuestión. Un ejemplo claro para el que no se verifica este principio aparece al tratar de encontrar el camino de coste máximo entre dos vértices de un grafo ponderado.
Richard Ernest Bellman (1920–1984) fue un matemáticoaplicado, cuya mayor contribución fue la metodología denominada programación dinámica.
Bellman estudió matemáticas en la Universidad de Brooklyn, donde obtuvo una diplomatura, y luego en la Universidad de Wisconsin, donde obtuvo su licenciatura. Posteriormente comenzó a trabajar en el Laboratorio Nacional Los Álamos en el campo de la física teórica. En 1946 obtuvo su doctorado en la Universidad dePrinceton. También ejerció la docencia en la universidad del sur de California (EE. UU.), fue socio de la Academia Americana de las Artes y las Ciencias (1975) y de la Academia Nacional Americana de Ingeniería (1977). En 1979 el IEEE le otorgó la medalla de honor por su contribución a la teoría de los sistemas de control y de los procesos de decisión, en especial por su contribución con la...