Informatica
Páginas: 5 (1134 palabras)
Publicado: 22 de julio de 2010
PROGRAMACION DINAMICA
INTRODUCCIÓN
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 substancialmentemediante 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 solapamientoentre 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ólotiene 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, ylo 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 aplicable y por tanto esnecesario 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.
Para que un problema pueda ser abordado por esta técnica ha de cumplir dos condiciones:
* La solución al problema ha de ser alcanzada a través de una secuencia dedecisiones, una en cada etapa.
* Dicha secuencia de decisiones ha de cumplir el principio de óptimo.
En grandes líneas, el diseño de un algoritmo de Programación Dinámica consta de los siguientes pasos:
1. Planteamiento de la solución como una sucesión de decisiones y verificación de que ésta cumple el principio de óptimo.
2. Definición recursiva de la solución.
3. Cálculo delvalor de la solución óptima mediante una tabla en donde se almacenan soluciones a problemas parciales para reutilizar los cálculos.
4. Construcción de la solución óptima haciendo uso de la información contenida en la tabla anterior.
CÁLCULO DE LOS NÚMEROS DE FIBONACCI
Antes de abordar problemas más complejos veamos un primer ejemplo en el cual va a quedar reflejada toda esta problemática. Setrata del cálculo de los términos de la sucesión de números de Fibonacci. Dicha sucesión podemos expresarla recursivamente en términos matemáticos de la siguiente manera:
Fib(n) = 1 si n = 0,1
Fib(n−1)+ Fib(n− 2) si n >1
Por tanto, la forma más natural de calcular los términos de esa sucesión es mediante un programa recursivo:
PROCEDURE FibRec(n:CARDINAL):CARDINAL;
BEGIN
IFn<=1 THEN RETURN 1
ELSE
RETURN FibRec(n-1) + FibRec(n-2)
END
END FibRec;
El inconveniente es que el algoritmo resultante es poco eficiente ya que su tiempo de ejecución es de orden exponencial, como se vió en el primer capítulo.
Como podemos observar, la falta de eficiencia del algoritmo se debe a que se producen llamadas recursivas repetidas para calcular valores de la sucesión, que...
INTRODUCCIÓN
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 substancialmentemediante 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 solapamientoentre 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ólotiene 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, ylo 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 aplicable y por tanto esnecesario 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.
Para que un problema pueda ser abordado por esta técnica ha de cumplir dos condiciones:
* La solución al problema ha de ser alcanzada a través de una secuencia dedecisiones, una en cada etapa.
* Dicha secuencia de decisiones ha de cumplir el principio de óptimo.
En grandes líneas, el diseño de un algoritmo de Programación Dinámica consta de los siguientes pasos:
1. Planteamiento de la solución como una sucesión de decisiones y verificación de que ésta cumple el principio de óptimo.
2. Definición recursiva de la solución.
3. Cálculo delvalor de la solución óptima mediante una tabla en donde se almacenan soluciones a problemas parciales para reutilizar los cálculos.
4. Construcción de la solución óptima haciendo uso de la información contenida en la tabla anterior.
CÁLCULO DE LOS NÚMEROS DE FIBONACCI
Antes de abordar problemas más complejos veamos un primer ejemplo en el cual va a quedar reflejada toda esta problemática. Setrata del cálculo de los términos de la sucesión de números de Fibonacci. Dicha sucesión podemos expresarla recursivamente en términos matemáticos de la siguiente manera:
Fib(n) = 1 si n = 0,1
Fib(n−1)+ Fib(n− 2) si n >1
Por tanto, la forma más natural de calcular los términos de esa sucesión es mediante un programa recursivo:
PROCEDURE FibRec(n:CARDINAL):CARDINAL;
BEGIN
IFn<=1 THEN RETURN 1
ELSE
RETURN FibRec(n-1) + FibRec(n-2)
END
END FibRec;
El inconveniente es que el algoritmo resultante es poco eficiente ya que su tiempo de ejecución es de orden exponencial, como se vió en el primer capítulo.
Como podemos observar, la falta de eficiencia del algoritmo se debe a que se producen llamadas recursivas repetidas para calcular valores de la sucesión, que...
Leer documento completo
Regístrate para leer el documento completo.