Please enable JavaScript.
Coggle requires JavaScript to display documents.
Dynamic Programming, Approximation Algorithms - Coggle Diagram
Dynamic Programming
-
A ideia da técnica é evitar cálculos repetidos na busca da solução ótima de um problema recursivo. Para isso, cria-se uma estrutura na memória a fim de guardar tais resultados
Abordagens :
Top-down: partimos da solução geral ótima que se deseja encontrar e, então, analisa-se quais subproblemas são necessários resolver até que se chegue em um subproblema com resolução trivial
-
-
Função de memória :
A função de memória combina a força das abordagens top-down e bottom-up. Resolvendo APENAS subproblemas necessários e APENAS UMA VEZ
-
:warning: Obs: Sempre que um novo valor precisa ser calculado, o método verifica primeiro a entrada correspondente na tabela (se é nula ou não)
-
-
Approximation Algorithms
Algoritmos de aproximação são algoritmos usados para encontrar soluções aproximadas em problemas de otimização
Algoritmos de aproximação são geralmente associados com problemas NP-difíceis, já que estes problemas não podem ser resolvidos em tempo polinomial
:warning: obs: Esta abordagem é particularmente atraente para aplicações em que uma solução boa, mas não necessariamente ótima, satisfaz o problema
:warning: Obs: É normalmente baseado em alguma heurística específica para o problema. Uma heurística é uma regra de senso comum extraída da experiência, ao invés de ser matematicamente comprovada
-
-