Programação dinâmica

... by Raquel Minardi in Glossário 04 se setembro de 2019

Programação dinâmica é um paradigma de projeto de algoritmos. Paradigma é um exemplo que serve como modelo; um padrão. Em computação, paradigmas são formas ou técnicas de projeto de algoritmos comumente utilizadas, ou seja, para as quais há diversos exemplos de diferentes algoritmos. Alguns exemplos são: indução, recursividade, algoritmos de tentativa e erro, divisão e conquista, balanceamento, algoritmos gulosos e algoritmos aproximados [1].

A programação dinâmica é paradigma para projeto de algoritmos para a resolução de problemas de otimização combinatória, em particular.

É aplicável a problemas em que a solução ótima pode ser computada a partir das soluções de seus subproblemas que, previamente computadas e memorizadas, podem ser sobrepostas para gerar a solução do problema.

Dessa forma, a programação dinâmica consiste em computar a solução de todos os possíveis subproblemas de um problema, partindo dos menores para os maiores, armazenando os resultados em uma matriz ou tabela.

Uma grande vantagem desse paradigma é que uma vez que um subproblema é resolvido e sua resposta é armazenada na matriz, a solução desse subproblema nunca mais será recalculada [1].

Para que a programação dinâmica seja aplicável a um problema, duas características são necessárias [2]:

  • subestrutura ótima: um problema apresenta uma subestrutura ótima quando uma solução ótima para o problema contém soluções ótimas para seus subproblemas.
  • sobreposição de subproblemas: a sobreposição de subproblemas acontece quando um algoritmo recursivo reexamina o mesmo problema muitas vezes.

Exemplo: sequência de Fibonacci

Um exemplo comumente utilizado para explicar a programação dinâmica é o cálculo da sequência de Fibonacci.

A sequência de Fibonacci é a sequência numérica proposta pelo matemático Leonardo Pisa, mais conhecido como Fibonacci:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

A partir de um problema que ele criou, detectou a existência de uma regularidade matemática. Trata-se do exemplo clássico dos coelhos, em que Fibonacci descreve o crescimento de uma população desses animais.

A sequência é definida mediante a seguinte fórmula: Fn = Fn - 1 + Fn - 2.

Quando o cálculo da sequência de Fibonacci (ou mesmo de um termo) é solucionada por um algoritmo recursivo sem maiores cuidados e sem memorização, a dupla chamada à função F causa a necessidade da repetição de cálculos, que faz com que o tempo cresça exponencialmente.

Como um número da sequência é a soma dos dois números anteriores, uma solução muito mais eficiente envolve computar os termos desde o primeiro e armazenar os valores em um arranjo para posterior uso. Assim, ao calcular F3 que será a soma de F2 e F1, esses valores já terão sido previamente calculados e uma única vez.

A programação dinâmica em Bioinformática

Um problema clássico em Computação e um dos mais utilizados em Bioinformática é chamado de problema da máxima subsequência comum (do inglês Longest Common Subsequence - LCS). Para resolver o LCS, criamos uma matriz de programação dinâmica colocando a primeira sequência (de comprimento m) como as colunas e a segunda como as linhas (comprimento n). As células são preenchidas progressivamente do início da matriz (célula [0,0]) até o fim (célula [n, m]) usando programação dinâmica. Esse é a base para os algoritmos clássicos de alinhamento de sequência tão utilizados.

Só é possível usar a programação dinâmica para alinhamento de sequências pois o alinhamento ótimo entre um par de subsequências é parte do alinhamento final entre as sequências completas originais. Em outras palavras, o alinhamento de sequências é um problema que tem subestrutura ótima e cujos subproblemas podem ser sobrepostos.

Abordagem bottom-up ou top-down

Problemas de programação dinâmica podem ser abordados de forma top-down ou bottom-up. Como os termos sugerem, a abordagem top-down resolve o problema de forma recursiva, ou seja, no exemplo do algoritmo de Fibonacci, começamos pelo n-ésimo número e vamos calculando os valores menores recursivamente. Na abordagem bottom-up, vamos calculando os subproblemas menores e obtendo o resultado final como é o caso do alinhamento de sequências no qual vamos alinhamento as subsequências de tamanho 1, 2, 3, até chegar à sequência completa.

Referências

[1] Ziviani, Nivio. Projeto de algoritmos: com implementações em Pascal e C. Vol. 2. Luton: Thomson, 2004.
[2] Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2009.

Online Bioinfo

Redes Sociais