Please enable JavaScript.
Coggle requires JavaScript to display documents.
Outras otimizações algorítmicas - Coggle Diagram
Outras otimizações algorítmicas
Programação dinâmica
Usada para resolver problemas que tem subproblemas que se sobrepõem. Esses subproblemas tem soluções iguais para de alguns dos subproblemas.
Cada um dos subproblemas só precisa ser resolvido uma vez, e seus resultados guardados em uma tabela para conferência futura.
Exemplo de Fibonacci, onde a função F(n) = F(n-1) + F(n-2), para n>1, calcula algumas das subsoluções mais de uma vez. Estes valores poderiam ser calculados anteriormente e guardados em um array, o que agilizaria futuros cálculos.
Princípio da Otimidade: uma solução ótima para qualquer instância de um problema de otimização é composto das soluções ótimas de suas sub instâncias.
Exemplos
Change-making problem
Devolva o troco de valor
n
usando o menor número de moedas possíveis, considerando um conjunto e moedas disponíveis (todos os valores de moedas que existem naquele país).
Coin-collecting problem
Várias moedas são dispostas em casas de um tabuleiro de tamanho
n
x
m
, com não mais do que uma moeda por casa. Um robô no canto esquerdo superior do tabuleiro precisa coletar o maior número de moedas possível e trazer elas para o canto direito inferior. O robô só pode se movimentar 1 espaço pra direita ou 1 espaço pra baixo.
Coin row problem
Tendo uma fila de
n
moedas cujos valores são inteiros positivos, colete o maior número de moedas possíveis de modo que duas moedas adjacentes à linha inicial não podem ser coletadas.
Knapsack problem / Problema da mochila, já exposto antes
Funções de memória: nem todas as subsoluções são necessárias para resolver problemas, então é interessante usar funções de memórias para guardar
apenas
aquelas subsoluções que são necessárias.
Consiste em resolver um problema de maneira top-down, mas mantendo uma tabela que seria utilizada em um algoritmo de programação dinâmica bottom-up.
Todas as entradas da tabela são inicialmente NULL, e quando um novo valor precisa ser calculado, primeiro é checado se ele já existe na tabela. Se sim, busca ele, se não, ele é computado de maneira recursiva.
Objetivo de otimizar processos de decisão com multi estágios. "Programação" neste contexto se refere a "planejamento".
Algoritmos de aproximação para problemas NP-difíceis
Não existem algoritmos conhecidos que resolvem estes problemas em tempo polinomial, então quais são as nossas outras opções?
As vezes estes algoritmos podem ser resolvidos através de uma busca exaustiva, outros talvez utilizando programação dinâmica, mas somente para instâncias pequenas
A descoberta do método branch-and-bound foi importante porque ela possibilitou a solução de problemas de difícil otimização, mesmo com instâncicas grandes, em tempo aceitável, mesmo sabendo que a performance não pode ser garantida
Uma solução alternativa é usar um algoritmo rápido mas que nos dê uma solução boa, porém não necessariamente ótima, para aquele problema. Este caso é aceitável em alguns cenários.
Estes algoritmos rápidos são baseados em
heurísticas
, ou seja, são específicas em cada caso, então não provêm uma solução geral.
Algoritmos de aproximação para o problema do Caixeiro Viajante
Algoritmos gulosos
Heurística do vizinho mais próximo
Escolha uma cidade arbitrária para começar
Vá para a cidade não-visitada mais próxima da cidade atual
Repita o passo anterior até visitar todas as cidades
Retorne a cidade inicial
Não é uma boa solução, visto que a volta pode fazer com que o Caixeiro tenha que andar caminhos muito distantes
Algoritmo de heurística multi-fragmentado
Ordena as arestas em ordem de seus pesos
Repete
n
vezes, onde
n
é o número de cidades: adiciona a próxima aresta na lista de arestas ordenadas a um conjunto de arestas visitadas, desde que esta adição não crie um vértice de ordem 3 ou um cíclo de tamanho menor que
n
. Se não, pula a aresta.
Retorna o conjunto de arestas visitadas
Em geral, é melhor do que a heurística do vizinho mais próximo, mas ainda não é bom
Heurística de busca local
Em instâncias euclidianas, provê uma otimização surpreendentemente boa
3 algoritmos mais conhecidos: 2-opt, 3-opt, e algoritmo de Lin-Kernighan
Se as mudanças resultam em um caminho mais curto, o algoritmo faz deste caminho o caminho atual, e continua explorando a vizinhança deste da mesma forma. Se não, é retornado o caminho atual e o algoritmo para.
A cada iteração, o algoritmo explora a vizinhança em volta, substituindo arestas no caminho por outras arestas
Começam com uma primeira visita, que pode ser em uma escolha aleatória, ou a cidade mais próxima
2-opt trabalha deletando pares de arestas não-adjacentes no caminho e reconectando os seus pontos finais pelos diferentes pares de arestas, obtendo um outro caminho.