Programacion dinamica
Enviado por dany_d_r • 2 de Junio de 2013 • 399 Palabras (2 Páginas) • 336 Visitas
Existe una serie de problemas cuyas soluciones pueden ser expresadas
recursivamente en términos matemáticos, y posiblemente la manera más natural de
resolverlos es mediante un algoritmo recursivo. Sin embargo, 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.
En el diseño Divide y Vencerás del capítulo 3 veíamos cómo para resolver un
problema lo dividíamos en subproblemas independientes, los cuales se resolvían de
manera recursiva para combinar finalmente las soluciones y así resolver el
problema original. 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 de cá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 tabla 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 resolver de manera
eficiente problemas cuya solución ha sido abordada por otras técnicas y ha
fracasado.
Donde tiene mayor aplicación la Programación Dinámica 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).
La solución de problemas mediante esta técnica se basa en el llamado principio
de óptimo enunciado por Bellman en 1957 y que dice:
“En una secuencia de decisiones óptima toda subsecuencia ha de ser también
óptima”.
Hemos de observar que aunque este principio parece evidente no siempre es
...