Programação dinâmica – Wikipédia a enciclopédia livre

Prévia do material em texto

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 a problemas nos quais 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 muitas vezes.
Exemplos
Como exemplo simples de programação dinâmica, com alguma frequência, alguns textos, utilizam a
determinação da
Sequência de Fibonacci, quando implementada de forma recursiva. Isso porque quando a forma recursiva é
implementada
sem maiores cuidados, sem memorização, o seu cálculo de tempo cresce exponencialmente. Observe que a
rigor esse caso não é um problema de programação dinâmica, visto que o cálculo do n-ésimo número
de Fibonacci cresce linearmente, e não exponencialmente. Porém este exemplo ainda assim é utilizado, pois a
simplicidade é grande.
 Se n <= 1 então F(n) := 1
 caso contrário F(n) := F(n-1) + F(n-2)
Quando implementada de forma recursiva "ingênua" (naive), sem memorização, a dupla chamada à F na
segunda linha,
causa a necessidade da repetição de cálculos, que cresce exponencialmente.
Referências
1. ↑ Grafos e Algoritmos Computacionais, Jayme Luiz Szwarccfiter, 1984 Editora Campus Ltda.
Obtida de "http://pt.wikipedia.org/w/index.php?title=Programação_dinâmica&oldid=33243073"
Categoria: Algoritmos de otimização
Menu de navegação
[1]
Esta página foi modificada pela última vez à(s) 12h34min de 10 de dezembro de 2012.
Este texto é disponibilizado nos termos da licença Atribuição-Partilha nos Mesmos Termos 3.0 não
Adaptada (CC BY-SA 3.0); pode estar sujeito a condições adicionais. Consulte as condições de uso
para mais detalhes.