Programação dinâmica

Origem: Wikipédia, a enciclopédia livre.

Programação dinâmica é um método para a construção de algoritmos para a resolução de problemas computacionais, em especial os de otimização combinatória. Ela é aplicável à problemas no qual a solução ótima pode ser computada a partir da solução ótima previamente calculada e memorizada - de forma a evitar recálculo - de outros subproblemas que, sobrepostos, compõem o problema original.

O que um problema de otimização deve ter para que a programação dinâmica seja aplicável são duas principais características: subestrutura ótima e superposição de subproblemas. Um problema apresenta uma subestrutura ótima quando uma solução ótima para o problema contém em seu interior soluções ótimas para subproblemas. A superposição de subproblemas acontece quando um algoritmo recursivo reexamina o mesmo problema muita vezes.

[editar] Exemplos

O exemplo clássico para o entendimento do método é o algoritmo para o cálculo da sequência de Fibonacci:

   declara mem <-- mapeamento(0 → 0, 1 → 1)
   função fib(n)
   {
       se' n não está em índices(mem)
           mem[n] <-- fib(n − 1) + fib(n − 2)
       retorna' mem[n]
   }

No algoritmo acima, baseado em programação dinâmica, o mapeamento mem contém a memorização de cada membro calculado da sequência. Para fib(5), a os passos de computação seriam:

1. fib(5)
2. mem[5]= fib(4) + fib(3)
3. mem[4]= fib(3) + fib(2)
4. mem[3]= fib(2) + fib(1)
5. mem[2]= fib(1) + fib(0)
6. fib(1)= mem[1]
7. fib(0)= mem[0]
8. mem[2]= mem[1] + mem[0]
9. fib(2)= mem[2]
10. fib(1)= mem[1]
11. mem[3]= mem[2] + mem[1]
12. fib(3)= mem[3]
13. fib(2)= mem[2]
14. mem[4]= mem[3] + mem[2]
15. fib(4)= mem[4]
16. fib(3)= mem[3]
17. mem[5]= mem[4] + mem[3]
18. fib(5)= mem[5]

Se um algoritmo recursivo simples como

   função fib(n)
       se n = 0 ou n = 1
           retorna n
       senão
           retorna fib(n − 1) + fib(n − 2)

fosse aplicado, uma sequência maior de passos seria necessária:

1. fib(5)
2. fib(5) = fib(4) + fib(3)
3. fib(4) = fib(3) + fib(2)
4. fib(3) = fib(2) + fib(1)
5. fib(2) = fib(1) + fib(0)
6. fib(1) = 1
7. fib(0) = 0
8. fib(2) = 1 + 0 = 1
9. fib(1) = 1
10. fib(3) = 1 + 1 = 2
11. fib(2) = fib(1) + fib(0)
12. fib(1) = 1
13. fib(0) = 0
14. fib(2) = 1 + 0 = 1
15. fib(4) = 2 + 1 = 3
16. fib(3) = fib(2) + fib(1)
17. fib(2) = fib(1) + fib(0)
18. fib(1) = 1
19. fib(0) = 0
20. fib(2) = 1 + 0 = 1
21. fib(1) = 1
22. fib(3) = 1 + 1 = 2
23. fib(5) = 3 + 2 = 5

Este artigo é um esboço sobre Informática. Você pode ajudar a Wikipédia expandindo-o.