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:
# Dividir o problema en subproblemas máis pequenos.
# Resolver estes problemas de xeito óptimo usando este proceso de tres pasos recursivamente.
# 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, F3 = F1 + F2 e F4 = F2 + F3 — calcular cada termo supón calcular F2. Como ambos os F3 e F4 fan falta para calcular F5, unha mala implementación para calcular F5 acabará calculando F2 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:
# `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)` 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.