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.
Ferramentas pessoais
Criar um livro