sábado, 26 de maio de 2012

Programação Dinâmica



·         Subestrutura ótima
Uma solução ótima para o problema contém em seu interior soluções ótimas para subproblemas. Constrói-se uma solução ótima para um problema a partir de soluções ótimas para subproblemas.
Exemplo: todo subcaminho de um caminho ótimo também é ótimo.
·         Superposição de problema
Ocorre quando um algoritmo recursivo reexamina o mesmo problema inúmeras vezes.
Exemplo: Sequência de Fibonacci
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)










Este problema tem subestrutura ótima?
Este problema tem superposição de subproblemas?
Eu preciso calcular todos os caminhos distintos para encontrar o menor caminho?
O menor caminho para chegar em um vértice depende do menor caminho previamente calculado de quais outros vértices?

Nenhum comentário: