Please enable JavaScript.
Coggle requires JavaScript to display documents.
Programação dinâmica, Algoritmos de aproximação - Coggle Diagram
Programação dinâmica
Problema da mochila e funções de memória
(-) (nW)
Optimal solution: o(n)
Memory functions
Top-down + botton-up
Antes de calcular vê se não já tem a resposta pro problema
Mesma classe do bottom-up
Princípio da otimalidade
Uma solução ótima é composta de outas soluções ótimas
Falha pra achar o menor caminho em um grafo
Problemas com subproblemas sobrepostos
Resolver problemas pequenos e usar os resultados nos grandes
Não ter que ficar calculando recursões de fibonacci é um bom exemplo
TopDown
Só calcula o necessário mas faz isso várias vezes
BottonUp
Calcula tudo mas só uma vez
Algoritmos de aproximação
Uma forma de resolver problemas NP hard
Encontra soluções corretas mas não as melhores
Heurísticas
Regras definidas a partir da observação para um determinado problema
Precisão
Quanto mais perto de 1 melhor
Pode tender a infinito
c-approximation algorithm
Um algoritmo polinomial cuja precisão não ultrapassa C
Teoremas
Se P != NP não existe um algoritmo de aproximação polinomial para todos os casos do vendedor viajante
O twice-around-the-tree é um 2-aproximação para o problema do viajante com distancias euclideanas
problemas
vendedor viajante
Vizinho mais próximo
Multifragmentos
Cristofides
2-opt
3-opt
Lin-Kernighan
Mochila
Escolher pelos raios (não optimal)
Escolher pelos raios e poder partir elementos (optimal)