Fibonacci e programação dinâmica
Peça a um computador o 40.º número de Fibonacci da forma mais óbvia e ele faz mais de 331 milhões de chamadas. Peça-lho com uma tabela e bastam-lhe 39 adições. A diferença é a programação dinâmica, e é com os números de Fibonacci que quase toda a gente a conhece pela primeira vez.
O problema
Os números de Fibonacci começam por 0, 1, e cada número seguinte é a soma dos dois anteriores: 0, 1, 1, 2, 3, 5, 8, 13, 21 e assim por diante. Escrito como regra: F(0) = 0, F(1) = 1 e F(n) = F(n − 1) + F(n − 2). A regra é recursiva, e transformá-la diretamente num programa recursivo é fácil, mas esse programa revela-se muito lento.
Porque é que a recursão se repete
Para encontrar F(5), o programa pede F(4) e F(3). F(4) pede F(3) e F(2), por isso F(3) é calculado duas vezes, F(2) três vezes e F(1) cinco vezes. Desenhadas como uma árvore, as chamadas quase duplicam em cada nível, e o total para F(n) é de 2·F(n + 1) − 1 chamadas. Os problemas mais pequenos sobrepõem-se: os mesmos voltam vezes sem conta. É esse o sinal de que a programação dinâmica vai ajudar.
Duas formas de lembrar
A memoização mantém a recursão mas escreve cada resposta numa tabela, e cada chamada consulta a tabela antes de fazer qualquer cálculo. A tabulação preenche a tabela de baixo para cima: primeiro F(0) e F(1), depois F(2) a partir deles, F(3) a partir de F(2) e F(1), e assim por diante até F(n). De qualquer forma, cada termo é calculado uma vez, por isso F(n) custa n − 1 adições em vez de um número exponencial de chamadas.
Um exemplo
Com o método ascendente para F(7): comece com 0 e 1. Depois 0 + 1 = 1, 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8 e 5 + 8 = 13, por isso F(7) = 13 após seis adições. A recursão simples faria 2·F(8) − 1 = 41 chamadas para a mesma resposta. Com o método descendente, as primeiras chamadas descem até F(1) pela margem esquerda da árvore; no caminho de volta, quase uma em cada duas chamadas encontra a resposta já na tabela.
De onde vem o nome
Richard Bellman deu o nome à programação dinâmica no início dos anos 1950, quando trabalhava na RAND Corporation. Mais tarde escreveu que escolheu «programação» no sentido antigo de planeamento, e «dinâmica» porque soava impressionante e era difícil de contestar. O método em si, resolver um problema através das respostas a versões mais pequenas dele, funciona hoje em corretores ortográficos, planeadores de rotas e na comparação de ADN.
Explore
Abra a aplicação e prima Avançar. Com Ascendente, a célula laranja é a que está a ser preenchida e as duas células azuis são os termos que ela soma. Mude para Descendente e veja a pilha de chamadas por baixo da tabela crescer até n e depois encolher à medida que as respostas regressam; a indicação por baixo de Adições conta quantas chamadas foram respondidas diretamente pela tabela.
Perguntas frequentes
O que são subproblemas sobrepostos?
Problemas mais pequenos de que uma solução precisa mais do que uma vez. F(n) e F(n − 1) precisam ambos de F(n − 2), por isso a recursão simples calcula-o duas vezes, e o desperdício multiplica-se mais abaixo. A programação dinâmica resolve cada um apenas uma vez e guarda a resposta.
A memoização é mais rápida do que a tabulação?
Fazem as mesmas adições. A tabulação costuma ser um pouco mais rápida porque não faz chamadas, e não pode ficar sem espaço na pilha; a memoização dá jeito quando só são precisas algumas das respostas mais pequenas, porque só calcula essas.
É possível calcular os números de Fibonacci ainda mais depressa?
Sim. Usando F(2k) = F(k)·(2·F(k + 1) − F(k)) e F(2k + 1) = F(k)² + F(k + 1)², o método da duplicação rápida precisa apenas de cerca de log₂ n passos. A fórmula de Binet com a razão de ouro dá os mesmos números, mas os erros de arredondamento tornam-na pouco fiável para n grande.
De quanta memória precisa a tabela?
Uma tabela completa guarda n + 1 números, mas cada novo termo só precisa dos dois anteriores, por isso um ciclo que guarde dois números faz o mesmo trabalho com memória constante. Guardar a tabela inteira é útil quando quer todos os termos, ou para ver como o método funciona.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Experimente Fibonacci com programação dinâmica