·
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:
Postar um comentário