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.
[editar] Exemplos
O exemplo clássico para o entendimento do método é o algoritmo para o cálculo da seqüê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:
fib(5)mem[5]= fib(4) + fib(3)mem[4]= fib(3) + fib(2)mem[3]= fib(2) + fib(1)mem[2]= fib(1) + fib(0)fib(1)= mem[1]fib(0)= mem[0]mem[2]= mem[1] + mem[0]fib(2)= mem[2]fib(1)= mem[1]mem[3]= mem[2] + mem[1]fib(3)= mem[3]fib(2)= mem[2]mem[4]= mem[3] + mem[2]fib(4)= mem[4]fib(3)= mem[3]mem[5]= mem[4] + mem[3]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:
fib(5)fib(5) = fib(4) + fib(3)fib(4) = fib(3) + fib(2)fib(3) = fib(2) + fib(1)fib(2) = fib(1) + fib(0)fib(1) = 1fib(0) = 0fib(2) = 1 + 0 = 1fib(1) = 1fib(3) = 1 + 1 = 2fib(2) = fib(1) + fib(0)fib(1) = 1fib(0) = 0fib(2) = 1 + 0 = 1fib(4) = 2 + 1 = 3fib(3) = fib(2) + fib(1)fib(2) = fib(1) + fib(0)fib(1) = 1fib(0) = 0fib(2) = 1 + 0 = 1fib(1) = 1fib(3) = 1 + 1 = 2fib(5) = 3 + 2 = 5
