Diferencia entre revisiones de «Programación dinámica»

← Ir a diferencia anterior Ir a siguiente diferencia →

Contenido eliminado Contenido añadido

En renglón

Revisión del 16:33 15 sep 2009

En la Informática, la programación dinámica es un método para reducir el tiempo de ejecución de un algoritmo mediante la utilización de subproblemas superpuestos y subestructuras óptimas, como se describe a continuación.

El matemático Richard Bellman inventó la programación dinámica en 1953.

Introducción

Una subestructura óptima significa que soluciones óptimas de subproblemas pueden ser usadas para encontrar las soluciones óptimas del problema en su conjunto. Por ejemplo, el camino más corto entre dos vértices de un grafo se puede encontrar calculando primero el camino más corto al objetivo desde todos los vértices adyacentes al de partida, y después usando estas soluciones para elegir el mejor camino de todos ellos. En general, se pueden resolver problemas con subestructuras óptimas siguiendo estos tres pasos:

Dividir el problema en subproblemas más pequeños.
Resolver estos problemas de manera óptima usando este proceso de tres pasos recursivamente.
Usar estas soluciones óptimas para construir una solución óptima al problema original.

Los subproblemas se resuelven a su vez dividiéndolos ellos mismos en subproblemas más pequeños hasta que se alcance el caso fácil, donde la solución al problema es trivial.

Decir que un problema tiene subproblemas superpuestos es decir que un mismo subproblema es usado para resolver diferentes problemas mayores. Por ejemplo, en la sucesión de Fibonacci, F₃ = F₁ + F₂ y F₄ = F₂ + F₃ — calcular cada término supone calcular F₂. Como ambos F₃ y F₄ hacen falta para calcular F₅, una mala implementación para calcular F₅ acabará calculando F₂ dos o más veces. Esto ocurre siempre que haya subproblemas superpuestos: una mala implementación puede acabar desperdiciando tiempo recalculando las soluciones óptimas a subproblemas que ya han sido resueltos anteriormente.

Esto se puede evitar guardando las soluciones que ya hemos calculado. Entonces, si necesitamos resolver el mismo problema más tarde, podemos obtener la solución de la lista de soluciones calculadas y reutilizarla. Este acercamiento al problema se llama memorización (en inglés "memorization"). Si estamos seguros de que no volveremos a necesitar una solución en concreto, la podemos descartar para ahorrar espacio. En algunos casos, podemos calcular las soluciones a problemas que sabemos que vamos a necesitar de antemano.

En resumen, la programación dinámica hace uso de:

La programación dinámica toma normalmente uno de los dos siguientes enfoques:

Top-down: El problema se divide en subproblemas, y estos subproblemas se resuelven recordando las soluciones en caso de que sean necesarias nuevamente. Es una combinación de memorización y recursión.
Bottom-up: Todos los subproblemas que puedan ser necesarios se resuelven de antemano y después son usados para resolver las soluciones a problemas mayores. Este enfoque es ligeramente mejor en consumo de espacio y llamadas a funciones, pero a veces resulta poco intuitivo encontrar todos los subproblemas necesarios para resolver un problema dado.

Originalmente, el término de programación dinámica se refería a la resolución de ciertos problemas y operaciones fuera del ámbito de la Ingeniería Informática, como también lo hacía la programación lineal. Aquel contexto no tiene relación con la programación en absoluto; el nombre es una coincidencia. El término también se usaba en los años 40 por Richard Bellman, un matemático norteamericano, para describir el proceso de resolver problemas donde hace falta calcular la mejor solución consecutivamente.

Algunos lenguajes de programación funcionales, sobre todo Haskell, pueden usar la memorización automáticamente sobre funciones con un conjunto concreto de argumentos, para acelerar su proceso de evaluación. Esto sólo es posible en funciones que no tengan efectos secundarios, algo que ocurre en Haskell pero no tanto en otros lenguajes.

Principio de optimalidad

Cuando hablamos de optimizar nos referimos a buscar alguna de las mejores soluciones de entre muchas alternativas posibles. Dicho 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 cual 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 que dicta que «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 más pequeños y por lo tanto más fáciles de resolver como hacemos en Divide y Vencerás, técnica similar a la de Programación Dinámica. La programación dinámica se aplica cuando la subdivisión de un problema conduce a:

Una enorme cantidad de subproblemas.
Subproblemas cuyas soluciones parciales se solapan.
Grupos de subproblemas de muy distinta complejidad.

Ejemplos

Sucesión de Fibonacci

Esta sucesión puede ser expresada mediante la siguiente recurrencia:

          1    si n = 0, 1
Fib(n) =	
          Fib(n-1) + Fib(n-2)    si n > 1

Una implementación de una función que encuentre el n-ésimo término de la sucesión de Fibonacci basada directamente en la definición matemática de la sucesión realizando llamadas recursivas hace mucho trabajo redundante, obteniéndose una complejidad exponencial:

   FUNC fib(↓n: NATURAL): NATURAL
   INICIO
       SI n = 0 ENTONCES
           DEVOLVER 0
       SINOSI n = 1 ENTONCES
           DEVOLVER 1
       SINO
           devolver fib(n-1) + fib(n-2)
       FINSI
   FIN

Si llamamos, por ejemplo, a fib(5), produciremos un árbol de llamadas que contendrá funciones con los mismos parámetros varias veces:

fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + (fib(2) + fib(1))
((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

En particular, fib(2) ha sido calculado dos veces desde cero. En ejemplos mayores, muchos otros valores de fib, o subproblemas, son recalculados.

Para evitar este inconveniente, podemos resolver el problema mediante programación dinámica, y en particular, utilizando el enfoque de memorización (guardar los valores que ya han sido calculados para utilizarlos posteriormente). Así, rellenaríamos una tabla con los resultados de los distintos subproblemas, para reutilizarlos cuando haga falta en lugar de volver a calcularlos. La tabla resultante sería una tabla unidimensional con los resultados desde 0 hasta n.

Un programa que calculase esto, usando Bottom-up, tendría la siguiente estructura:

   FUNC Fibonacci (↓n: NATURAL): NATURAL
   VARIABLES
       tabla: ARRAY [0..n] DE NATURAL
       i: NATURAL
   INICIO
       SI n <= 1 ENTONCES
           devolver 1
       SINO
           tabla[0] ← 1
           tabla[1] ← 1
           PARA i ← 2 HASTA n HACER
               tabla[i] ← tabla[i-1] + tabla[i-2]
           FINPARA
           devolver tabla[n]
       FINSI
   FIN

La función resultante tiene complejidad O(n), en lugar de exponencial.

Otro nivel de refinamiento que optimizaría la solución sería quedarnos tan sólo con los dos últimos valores calculados en lugar de toda la tabla, que son realmente los que nos resultan útiles para calcular la solución a los subproblemas.

El mismo problema usando Top-down tendría la siguiente estructura:

   FUNC Fibonacci (↓n: NATURAL, ↨tabla: ARRAY [0..n] DE NATURAL): NATURAL
   VARIABLES
       i: NATURAL
   INICIO
       SI n <= 1 ENTONCES
           devolver 1
       FINSI
       SI tabla[n-1] = -1 ENTONCES
           tabla[n-1] ← Fibonacci(n-1, tabla)
       FINSI
       SI tabla[n-2] = -1 ENTONCES
           tabla[n-2] ← Fibonacci(n-2, tabla)
       FINSI
       tabla[n] ← tabla[n-1] + tabla[n-2]
       devolver tabla[n]
   FIN

Suponemos que la tabla se introduce por primera vez correctamente inicializada, con todas las posiciones con un valor inválido, como por ejemplo -1, que se distingue por no ser uno de los valores que computa la función.

Coeficientes binomiales

El algoritmo recursivo que calcula los coeficientes binomiales resulta ser de complejidad exponencial por la repetición de los cálculos que realiza. No obstante, es posible diseñar un algoritmo con un tiempo de ejecución de orden O(nk) basado en la idea del Triángulo de Pascal, idea claramente aplicable mediante programación dinámica. Para ello es necesaria la creación de una tabla bidimensional en la que ir almacenando los valores intermedios que se utilizan posteriormente.

La idea recursiva de los coeficientes binomiales es la siguiente:

${n \choose k}$ = ${n-1 \choose k-1}$ + ${n-1 \choose k}$ si 0 < k < n

${n \choose 0}$ = ${n \choose n}$ = 1

La idea para construir la tabla de manera eficiente y sin valores inútiles es la siguiente:

	0	1	2	3	...	k-1	k
0	1
1	1	1
2	1	2	1
3	1	3	3	1
...	...	...	...	...	...
...	...	...	...	...	...	...
n-1						C(n-1,k-1)	C(n-1,k)
n							C(n,k)

El siguiente algoritmo memorizado de estrategia Bottom-up tiene complejidad polinómica y va rellenando la tabla de izquierda a derecha y de arriba abajo:

   FUNC CoeficientesPolinomiales ( ↓ n, k: NATURAL): NATURAL
   Variables
       tabla: TABLA DE NATURAL
       i, j: NATURAL
   Inicio
       PARA i ← 0 HASTA n HACER
           tabla[i][0] ← 1
       FINPARA
       PARA i ← 1 HASTA n HACER
           tabla[i][1] ← i
       FINPARA
       PARA i ← 2 HASTA k HACER
           tabla[i][i] ← 1
       FINPARA
       PARA i ← 3 HASTA n HACER
           PARA j ← 2 HASTA i-1 HACER
               SI j <= k ENTONCES
                   tabla[i][j] ← tabla[i-1][j-1] + tabla[i-1][j]
               FINSI
           FINPARA
       FINPARA
       devolver tabla[n][k]
   Fin

Por supuesto, el problema de los Coeficientes Binomiales también puede resolverse mediante un enfoque Top-down.

El viaje más barato por río

En un río hay n embarcaderos, en cada uno de los cuales se puede alquilar un bote para ir a otro embarcadero que esté más abajo en el río. Suponemos que no se puede remontar el río. Una tabla de tarifas indica los costes de viajar entre los distintos embarcaderos. Se supone que puede ocurrir que un viaje entre i y j salga más barato haciendo escala en k embarcaderos que yendo directamente.

El problema consistirá en determinar el coste mínimo para par de embarcaderos.

Vamos a llamar a la tabla de tarifas, T. Así, T[i,j] será el coste de ir del embarcadero i al j. La matriz será triangular superior de orden n, donde n es el número de embarcaderos.

La idea recursiva es que el coste se calcula de la siguiente manera:

C(i, j) = T[i, k] + C(k, j)

A partir de esta idea, podemos elaborar una expresión recurrente para la solución:

          0   si i = j
C(i, j)=
           Min(T(i,k) + C(k,j), T(i,j))   si i < k <= j

Un algoritmo que resuelve este problema es el siguiente, donde T es la matriz de tarifas, origen y destino los embarcaderos del que se parte y al que se llega respectivamente, y C la matriz en la que almacenaremos los resultados de los costes. La función MenorDeLosCandidatos devuelve el menor coste entre dos puntos, utilizando como base la recurrencia anteriormente expuesta.

   FUNC Embarcaderos ( ↓ origen, destino, n: NATURAL, ↓ T: MATRIZ DE NATURAL): NATURAL
   Variables
       C: MATRIZ DE NATURAL
       i, j: NATURAL
   Inicio
       PARA i ← 1 HASTA n HACER
           C[i][i] ← 0
       FINPARA
       PARA i ← 1 HASTA n HACER
           PARA j ← 1 HASTA n HACER
               C[i][j] ← menorDeLosCandidatos(i, j, n, T, C)
           FINPARA
       FINPARA
       devolver C[n] [n]
   Fin

   FUNC menorDeLosCandidatos ( ↓ origen, destino, n: NATURAL, ↓ T, C: MATRIZ DE NATURAL): NATURAL
   Variables
       temp: NATURAL
   Inicio
       temp ← MAX_NATURAL
       PARA i ← origen+1 HASTA n HACER
           temp ← min(temp, T[origen][i] + C[i][destino]
       FINPARA
       devolver temp
   Fin

Ejercicios resueltos con Programación Dinámica

Referencias

Xumari, G.L. Introduction to dynamic programming. Wilwy & Sons Inc., New York. 1967.

@@ Línea 12: / Línea 12: @@
 Decir que un problema tiene ''subproblemas superpuestos'' es decir que un mismo subproblema es usado para resolver diferentes problemas mayores. Por ejemplo, en la [[sucesión de Fibonacci]], F<sub>3</sub> = F<sub>1</sub> + F<sub>2</sub> y F<sub>4</sub> = F<sub>2</sub> + F<sub>3</sub> — calcular cada término supone calcular F<sub>2</sub>. Como ambos F<sub>3</sub> y F<sub>4</sub> hacen falta para calcular F<sub>5</sub>, una mala implementación para calcular F<sub>5</sub> acabará calculando F<sub>2</sub> dos o más veces. Esto ocurre siempre que haya subproblemas superpuestos: una mala implementación puede acabar desperdiciando tiempo recalculando las soluciones óptimas a subproblemas que ya han sido resueltos anteriormente.
-Esto se puede evitar guardando las soluciones que ya hemos calculado. Entonces, si necesitamos resolver el mismo problema más tarde, podemos obtener la solución de la lista de soluciones calculadas y reutilizarla. Este acercamiento al problema se llama ''[[memoización]]'' (no es un error ortográfico) (en inglés "[[memorization]]"). Si estamos seguros de que no volveremos a necesitar una solución en concreto, la podemos descartar para ahorrar espacio. En algunos casos, podemos calcular las soluciones a problemas que sabemos que vamos a necesitar de antemano.
+Esto se puede evitar guardando las soluciones que ya hemos calculado. Entonces, si necesitamos resolver el mismo problema más tarde, podemos obtener la solución de la lista de soluciones calculadas y reutilizarla. Este acercamiento al problema se llama ''[[memorización]]'' (en inglés "[[memorization]]"). Si estamos seguros de que no volveremos a necesitar una solución en concreto, la podemos descartar para ahorrar espacio. En algunos casos, podemos calcular las soluciones a problemas que sabemos que vamos a necesitar de antemano.
 En resumen, la programación dinámica hace uso de:
 * [[suproblema superpuesto|Subproblemas superpuestos]]
 * [[estructura óptima|Subestructuras óptimas]]
-* [[Memoización]]
+* [[Memorización]]
 La programación dinámica toma normalmente uno de los dos siguientes enfoques:
-* '''[[Top-down]]''': El problema se divide en subproblemas, y estos subproblemas se resuelven recordando las soluciones en caso de que sean necesarias nuevamente. Es una combinación de [[memoización]] y [[recursión]].
+* '''[[Top-down]]''': El problema se divide en subproblemas, y estos subproblemas se resuelven recordando las soluciones en caso de que sean necesarias nuevamente. Es una combinación de [[memorización]] y [[recursión]].
 * '''[[Bottom-up]]''': Todos los subproblemas que puedan ser necesarios se resuelven de antemano y después son usados para resolver las soluciones a problemas mayores. Este enfoque es ligeramente mejor en consumo de espacio y llamadas a funciones, pero a veces resulta poco intuitivo encontrar todos los subproblemas necesarios para resolver un problema dado.
 Originalmente, el término de ''programación dinámica'' se refería a la resolución de ciertos problemas y operaciones fuera del ámbito de la [[Ingeniería Informática]], como también lo hacía la ''[[programación lineal]]''. Aquel contexto no tiene relación con la [[programación]] en absoluto; el nombre es una coincidencia. El término también se usaba en los [[Años 1940|años 40]] por [[Richard Bellman]], un matemático norteamericano, para describir el proceso de resolver problemas donde hace falta calcular la mejor solución consecutivamente.
-Algunos [[lenguaje de programación|lenguajes de programación]] [[Paradigma funcional|funcionales]], sobre todo [[Haskell]], pueden usar la [[memoización]] automáticamente sobre funciones con un conjunto concreto de argumentos, para acelerar su proceso de evaluación. Esto sólo es posible en funciones que no tengan [[Efecto secundario (computación)|efectos secundarios]], algo que ocurre en [[Haskell]] pero no tanto en otros lenguajes.
+Algunos [[lenguaje de programación|lenguajes de programación]] [[Paradigma funcional|funcionales]], sobre todo [[Haskell]], pueden usar la [[memorización]] automáticamente sobre funciones con un conjunto concreto de argumentos, para acelerar su proceso de evaluación. Esto sólo es posible en funciones que no tengan [[Efecto secundario (computación)|efectos secundarios]], algo que ocurre en [[Haskell]] pero no tanto en otros lenguajes.
 == Principio de optimalidad ==
@@ Línea 71: / Línea 71: @@
 En particular, <code>fib(2)</code> ha sido calculado dos veces desde cero. En ejemplos mayores, muchos otros valores de <code>fib</code>, o ''[[subproblema superpuesto|subproblemas]], son recalculados.
-Para evitar este inconveniente, podemos resolver el problema mediante programación dinámica, y en particular, utilizando el enfoque de memoización (guardar los valores que ya han sido calculados para utilizarlos posteriormente). Así, rellenaríamos una tabla con los resultados de los distintos subproblemas, para reutilizarlos cuando haga falta en lugar de volver a calcularlos. La tabla resultante sería una tabla unidimensional con los resultados desde 0 hasta n.
+Para evitar este inconveniente, podemos resolver el problema mediante programación dinámica, y en particular, utilizando el enfoque de memorización (guardar los valores que ya han sido calculados para utilizarlos posteriormente). Así, rellenaríamos una tabla con los resultados de los distintos subproblemas, para reutilizarlos cuando haga falta en lugar de volver a calcularlos. La tabla resultante sería una tabla unidimensional con los resultados desde 0 hasta n.
 Un programa que calculase esto, usando Bottom-up, tendría la siguiente estructura:
@@ Línea 153: / Línea 153: @@
 |}
-El siguiente algoritmo memoizado de estrategia Bottom-up tiene complejidad polinómica y va rellenando la tabla de izquierda a derecha y de arriba abajo:
+El siguiente algoritmo memorizado de estrategia Bottom-up tiene complejidad polinómica y va rellenando la tabla de izquierda a derecha y de arriba abajo:
     '''FUNC''' CoeficientesPolinomiales ( ↓ n, k: '''NATURAL'''): '''NATURAL'''