Please enable JavaScript.
Coggle requires JavaScript to display documents.
Programação dinâmica, Algoritmos de aproximação para problemas NP-Hard -…
Programação dinâmica
-
-
Memory functions → Tenta combinar o melhor dos dois mundos do método top-down e bottom-up de dynamic programming. Com isso, os problemas que resolvemos temos a certeza de que seus resultados serão úteis, aumentando a eficiência temporal, e ao mesmo tempo, continuando fazendo uso da tabela que armazena os resultados das instâncias anteriores do problema
Dessa forma, resolvemos uma instância do problema à medida em que vamos precisando dela, e nunca fazemos isso duas vezes
Se um problema aparecer 2 vezes, na segunda vez já haverá uma resposta computada e armazenada
Sempre que estamos tratando de programação dinâmica, haverá sempre uma tendência a derivar uma relação de recorrência de um determinado problema que o relacione com subproblemas menores
Principle of optimality → Uma solução ótima para qualquer instância de um problema é composta por soluções ótimas para suas sub-instâncias
-