Programación dinámica (computación)

Na Informática, a programación dinámica é un método para reducir o tempo de execución dun algoritmo mediante a utilización de subproblemas superpostos e subestruturas óptimas, como se describe a continuación.

O matemático Richard Bellman inventou a programación dinámica en 1953.

Introdución

Unha subestructura óptima significa que solucións óptimas de subproblemas poden ser usadas para atopar as solucións óptimas do problema no seu conxunto. Por exemplo, o camiño máis curto entre dous vértices dun grafo pódese atopar calculando primeiro o camiño máis curto ao obxectivo desde todos os vértices adxacentes ao de partida, e despois usando estas solucións para elixir o mellor camiño de todos eles. En xeral, pódense resolver problemas con subestructuras óptimas seguindo estes tres pasos:

1. Dividir o problema en subproblemas máis pequenos.
2. Resolver estes problemas de xeito óptimo usando este proceso de tres pasos recursivamente.
3. Usar estas solucións óptimas para construír unha solución óptima ao problema orixinal.

Os subproblemas resólvense á súa vez dividíndoos en subproblemas máis pequenos ata que se alcance o caso fácil, onde a solución ao problema é trivial.

Dicir que un problema ten subproblemas superpostos é dicir que un mesmo subproblema é usado para resolver diferentes problemas maiores. Por exemplo, na sucesión de Fibonacci, F₃ = F₁ + F₂ e F₄ = F₂ + F₃ — calcular cada termo supón calcular F₂. Como ambos os F₃ e F₄ fan falta para calcular F₅, unha mala implementación para calcular F₅ acabará calculando F₂ dúas ou máis veces. Isto ocorre sempre que haxa subproblemas superpostos: unha mala implementación pode acabar desperdiciando tempo recalculando as solucións óptimas a subproblemas que xa foron resoltos anteriormente.

Isto pódese evitar gardando as solucións que xa calculamos. Entón, se necesitamos resolver o mesmo problema máis tarde, podemos obter a solución da lista de solucións calculadas e reutilizala. Este achegamento ao problema chámase memoización (que a pesar de non estar na lingua galega, o seu similar en inglés tampouco está e "é memoizing"). Se estamos seguros de que non volveremos necesitar unha solución en concreto, podémola descartar para aforrar espazo. Nalgúns casos, podemos calcular as solucións a problemas que sabemos que imos necesitar de antemán.

En resumo, a programación dinámica fai uso de:

• Subproblemas superpostos
• Subestruturas óptimas
• Memoización

A programación dinámica toma normalmente un dos dous seguintes enfoques:

• Top-down: O problema divídese en subproblemas, e estes subproblemas resólvense recordando as solucións no caso de que sexan necesarias novamente. É unha combinación de memoización e recursión.
• Bottom-up: Todos os subproblemas que poidan ser necesarios resólvense de antemán e despois son usados para resolver as solucións a problemas maiores. Este enfoque é lixeiramente mellor en consumo de espazo e chamadas a funcións, pero ás veces resulta pouco intuitivo atopar todos os subproblemas necesarios para resolver un problema dado.

Orixinalmente, o termo de programación dinámica designaba unicamente á resolución de certos problemas operacións fose do ámbito da Enxeñería Informática, do mesmo xeito que o facía programación lineal. Neste contexto non ten ningunha relación coa programación en absoluto; o nome é unha coincidencia. O termo tamén se usaba nos anos 40 por Richard Bellman, un matemático americano, para describir o proceso de resolver problemas onde fai falta calcular a mellor solución consecutivamente.

Algúns linguaxes de programación funcionais, sobre todo Haskell, poden usar a memoización automaticamente sobre funcións cun conxunto concreto de argumentos, para acelerar o seu proceso de avaliación. Isto só é posible en funcións que non teñan efectos secundarios, algo que ocorre en Haskell pero non tanto noutras linguaxes.

Principio de optimalidad

Cando falamos de optimizar referímonos a buscar a mellor solución de entre moitas alternativas posibles. Devandito proceso de optimización pode ser visto como unha secuencia de decisións que nos proporcionan a solución correcta. Se, dada unha subsecuencia de decisións, sempre se coñece cal é a decisión que debe tomarse a continuación para obter a secuencia óptima, o problema é elemental e resólvese trivialmente tomando unha decisión detrás doutra, o que se coñece como estratexia voraz.

A miúdo, aínda que non sexa posible aplicar a estratexia voraz, cúmprese o principio de optimalidad de Bellman que dita que «dada unha secuencia óptima de decisións, toda subsecuencia dela é, á súa vez, óptima». Neste caso segue sendo posible o ir tomando decisións elementais, na confianza de que a combinación delas seguirá sendo óptima, pero será entón necesario explorar moitas secuencias de decisións para dar coa correcta, sendo aquí onde intervén a programación dinámica.

Contemplar un problema como unha secuencia de decisións equivale a dividilo en subproblemas máis pequenos e polo tanto máis fáciles de resolver como facemos en Divide e Vencerás, técnica similar á de Programación Dinámica. A programación dinámica aplícase cando a subdivisión dun problema conduce a:

• Unha enorme cantidade de subproblemas.
• Subproblemas cuxas soluciones parciais se solapan.
• Grupos de subproblemas de moi distinta complexidade.

Exemplo

Sucesión de Fibonacci

Unha implementación dunha función que atope o n-ésimo termo da sucesión de Fibonacci baseada directamente na definición matemática da sucesión realiza moito traballo redundante:

   function fib(n)
       if n =0 or n= 1
           return n
       else
           return fib(n − 1) + fib(n − 2)

Se chamamos, por exemplo, a code fib (5), produciremos unha árbore de chamadas que conterá funcións cos mesmos parámetros varias veces:

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

En particular, fib(2) foi calculado dúas veces desde cero. En exemplos maiores, moitos outros valores de code <>fib, ou subproblemas, son recalculados, levando a un algoritmo de complexidade exponencial.

Agora supoñemos que temos un simple obxecto mapa, m, que garda cada valor de fib que xa foi calculado e modificamos a función para que o use e actualice. A función resultante ten complexidade Ou(n), no lugar de exponencial:

   var m := map(0 → 1, 1 → 1)
   function fib(n)
       if n not in keys(m)
           m[n] := fib(n − 1) + fib(n − 2)
       return m[n]

Esta técnica de gardar os valores que xa foron calculados chámase memorización; isto é unha implementación top-down, posto que primeiro dividimos o problema noutros máis pequenos e despois calculamos e almacenamos os valores. Neste caso, tamén podemos evitar que a función use unha cantidade de espazo lineal (Ou(n)) e use unha cantidade constante no seu lugar cambiando a definición da nosa función e usando unha implementación bottom-up que calculará valores pequenos de code fib primeiro para calcular outros maiores a partir destes:

   function fib(n)
       var currentFib := 0, nextFib := 1
       repeat n times
           var newFib := currentFib + nextFib
           currentFib := nextFib
           nextFib  := newFib
       return currentFib

En ámbolos dous exemplos, fib(2) só se calculou unha vez, e a continuación empregouse para calcular tanto fib(4) como fib(3), no lugar de calculalo cada vez que fora avaliado.

Véxase tamén

Bibliografía

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