Please enable JavaScript.
Coggle requires JavaScript to display documents.
MAIS TÉCNICAS PARA REMEDIAR BAIXA EFICIÊNCIA DE ALGORITMOS EM PROBLEMAS…
MAIS TÉCNICAS PARA REMEDIAR BAIXA EFICIÊNCIA DE ALGORITMOS EM PROBLEMAS COMPLEXOS
Programação Dinâmica
Pode ser vista como um tipo de space-time trade-off
Em alguns casos, o uso adicional de espaço pode ser evitado completamente, em especial com soluções iterativas no lugar de abordagens recursivas
Aplicável em problemas com sub-problemas que se entrelaçam
Aplicações
Problema da fileira de moedas
Problema do câmbio de moedas
Problema do robô que coleta moedas
Problema da mochila
Aproximações pra implementação da programação dinâmica
Bottom-up
Vantagem: computa os sub-problemas apenas uma vez
Existe alguma maneira de combinar as vantagens das duas aproximações?
FUNÇÕES DE MEMÓRIA
Faz uso de uma tabela (space-time trade-off) para armazenar os resultados dos sub-problemas
Realiza a abordagem top-down, buscando apenas as soluções dos sub-problemas necessários na tabela
Necessita de uma solução inicial nula para os sub-problemas, para o algoritmo conseguir diferenciar se uma solução já foi calculada ou não
Desvantagem: computa sub-problemas que não são necessários na solução final
Top-down
Vantagem: computa apenas os sub-problemas necessários para a solução final
Desvantagem: está associada às estruturas recursivas que acabam computando sub-problemas mais de uma vez
Aplicação no desenvolvimento de importantes algoritmos polinomiais
Algoritmo de Floyd
Algoritmo de Warshall
Algoritmos de aproximação
Usados em problemas de otimização, quando uma resposta relativamente próxima da mais óptima é aceitável
Calcular a acurácia e a margem de erro desses algoritmos é uma problemática à parte, que varia de complexidade
Cálculo da acurácia de um algoritmo de aproximação
valor da solução óptima dividido pelo valor da solução obtida
Problema óbvio: não se sabe a solução óptima
Possível solução:
Limite de Held-Karp
Problema da Mochila
Contínuo
Muito mais fácil do que o padrão
Faz uso de algoritmos gulosos como algoritmos de aproximação
Usa a divisão de valor do item pelo seu peso como critério
Problema do Caixeiro-viajante
Todos os algoritmos aplicados à versão padrão deste problema têm uma margem de erro infinita
Por isso, a real aplicação dos algoritmos de aproximação se dá nos casos
Euclidianos
Exemplos de técnicas
Algoritmo do vizinho mais próximo
Algoritmo do Multi-fragmento
Algoritmo das duas voltas pela árvore
Algoritmo de Christofides
2-opt
3-opt
Algoritmo de Lin-Kernighan