Please enable JavaScript.

Coggle requires JavaScript to display documents.

Programação Dinâmica, Algoritmos de Aproximação para Problemas NP Hard -…

- - - - A ideia é que ao chegar em uma moeda, há duas possibilidades, selecioná-la ou não
        
        Porém, isso tornará a próxima moeda inselecionável. Então é preciso saber qual das duas aumentará mais o valor total
        
        Isso pode ser feito registrando o valor total caso a moeda seja selecionada em uma array. Assim, ao analisar uma moeda, as opções seriam selecioná-la e agregar seu valor ao total sem a anterior ou manter o valor se a moeda anterior fosse selecionada
        
        Se não, o valor total será o valor já conhecido
        
        Se e moeda for selecionada, o valor total será o valor conhecido mais o valor da moeda
  - - - Para uma posição (i, j) no tabuleiro, o maior número de moedas que pode ser levado a ela é o número de moedas na posição acima ou à direita
        
        Para as células do topo e do extremo direito da tabela, esse número é 0
        
        O maior número de moedas que uma célula pode ter é o maior valor trazível se ela mesma não tiver uma moeda, ou mais um se tiver
        
        Assim, podemos registrar os maiores valores que cada célula pode ter em uma array bidimensional e usar os valores encontrados anteriormente para determinar os próximos
  - - - Primeiro, é preciso encontrar uma relação recursiva para derivar
        
        Escolhendo um subconjunto dos i primeiros itens da mochila, com pesos dew1 a wi e uma mochila de capacidade j, podemos separar os elementos desse subconjunto em duas categorias
        
        Os que incluem o i-ésimo item
        
        A solução ótima para essa categoria é a solução ótima para os i-1 primeiros itens da mochila
        
        O valor dessa solução vai ser _V, onde V é o valor da solução para os i-1 primeiros itens
        
        Os que não incluem o i-ésimo item
        
        A solução para essa categoria é a solução ótima para os i-1 primeiros itens da mochila mais o i-ésimo item
        
        O valor dessa solução vai ser vi + V, onde V é o valor da solução para os i-1 primeiros itens
        
        O valor ótimo para os i primeiros itens é o maior valor das duas categorias se o i-ésimo item couber na mochila ou o segundo se não couber
        
        Com isso, é possível preencher uma tabela com as possibilidades de subconjuntos de itens da mochila até encontrar a solução final
    - - As soluções top-down da programação dinâmica são mais eficientes que as clássicas bottom-up porque não realizam o mesmo processo múltiplas vezes. Entretanto, elas tem um problema
        
        Elas guardam os resultados dos subproblemas para não ter que repetí-los, mas nem todos esses resultados são relevantes para a solução final
        
        Para conciliar o melhor das duas versões, existem as memory functions
        
        Elas são executadas como as funções bottom-tup normais, mas tem uma tabela onde podem guardar resultados de subproblemas
        
        Nessa tabela, os itens são iniciados com um valor especial nulo e alterados quando um processo é realizado
        
        Assim, antes de realizar um processo, basta verificar se o resultado já não foi determinado
        
        1 more item...
        
        Essa tabela pode causar uma eficiência espacial inferior à versão bottom-up de algumas soluções
- - - - Exemplo: O cálculo do n-ésimo número de Fibonacci
        
        Programação dinâmica pode ser usada para evitar usar recursão
        
        Uso de uma recursão faria os mesmo valores serem recalculados múltiplas vezes
        
        Uma opção é salvar os valores dos números de Fibonacci anteriores ao n-ésimo em uma array unidimensional, para que eles possam ser reutilizados nos cálculos dos posteriores
        
        Aqui pode-se perceber um paralelo entre programação dinâmica e troca de espaço por velocidade (space-for-time trade-off)
        
        Uma opção mais refinada é salvar apenas os dois últimos números de Fibonacci calculados a partir do caso base
      - Essa divisão significa gerar otimizações para os subproblemas gera uma otimização para o problema original
        
        Isso é chamado Princípio da Otimalidade
        
        É importante comentar que, apesar de ser verdadeiro para a maioria dos casos, ele não se aplica sempre
      - Programação dinâmica oferece uma solução top-down para os problemas
- - - - Estes algoritmos podem ter alto grau de sofisticação, mas geralmente são baseados em uma heurística
        
        Uma heurística é uma regra baseada em experiências empíricas e senso comum
      - Para medir o quão correta essa solução aproximada está, é utilizado um accurancy ratio (razão de precisão) igual à razão dos valores de uma função f para a solução aproximada e a correta
        
        Na verdade, esse accurancy ratio é utilizado para problemas de minimização. Em problemas de maximização, é utilizada uma razão parecida, mas com denominador e numerador trocados de lugar
        
        Essa inversão é feita para uniformizar as escalas, mantendo a razão menor ou igual a 1
        
        O quão mais próxima essa razão for de 1, maior a precisão do algoritmo
- - - - Esse tipo de algoritmo é chamado c-aproximation algorithm (algoritmo de aproximação-c)
      - O menor valor de c para o qual as desigualdades se mantém é chamado performance ratio (razão de performance)
        
        Essa razão de performance é a principal forma de medir a qualidade de uma algoritmo de aproximação
        
        Idealmente, ele deve ser o mais próximo de 1 possível, mas há algoritmos de aproximação para os quais ele é infinitamente grande
  - - - Esse algoritmo procura resolver o Problema do Viajante com uma abordagem baseada na técnica gulosa. Ele se baseia em três passos:
        
        1- Escolher uma cidade arbitrária para começar
        
        2- Visitar a cidade não visitada mais próxima da última
        
        Essa etapa deve ser repetida até que todas as cidades tenham sido visitadas
        
        3- Voltar à cidade inicial
        
        Devido à simplicidade desse algoritmo, não há muito a se dizer de bom sobre ele ou sobre a precisão de soluções obtidas por ele
        
        Além disso, a razão de performance depende muito da última linha (o retorno à cidade inicial). Então, como ela pode ser infinitamente grande, a razão de performance também é infinita
    - - Esse algoritmo interpreta o Problema do Viajante como encontrar um conjunto de linhas de grafo com o menor peso possível de forma que todas tenham grau 2. Ele se baseia em três passos
        
        1- Ordenar as linhas do grafo de foram crescente de acordo com seus pesos
        
        2- Adicionar a próxima linha da lista ordenada à solução se ela não criar um vértice de grau 3
        
        Essa etapa deve ser repetida um número de vezes igual ao número de cidades na instância do problema
        
        3- Retornar a solução
        
        No geral, as soluções desse algoritmo são melhores que o do vizinho mais próximo, mas sua razão de performance também é infinita
        
        Apesar disso, vale mencionar que há um conjunto de instâncias para as quais a razão de aproximação é menor ou igual à metade do logaritmo do número de cidades na base 2 mais 1
        
        1 more item...
    - - Algoritmos baseados em minimum spanning tree é um conjunto de algoritmos que procura resolver o Problema do Viajante explorando a conexão entre ciclos hamiltonianos e as minimum spanning trees de um mesmo grafo
        
        Twice Around The Tree
        
        Este algoritmo é um exemplo de algoritmo baseado em minimum spanning tree. Ele também tem três etapas
        
        1- Construir a minimum spanning tree de um grafo correspondente à instância do problema
        
        2- Realizar uma travessia pelas mst a partir de um vértice arbitrário registrando os vértices visitados
        
        3- Iterar pela lista de vértices visitados e eliminar todas as repetições exceto a do vértice inicial no fim da lista
        
        1 more item...
        
        Isso pode ser feito uma travessia DFS
        
        Essa travessia é um ciclo Euleriano
        
        Algorimo de Christofides
        
        Este algoritmo tem uma razão de performance superior para a versão euclidiana do Problema do Viajante
        
        Enquanto o Twice Around The Tree garante que todos os vértices da mst tenham graus pares dobrando o número de linhas, o algorimto de Christofides adiciona linhas com um peso mínimo a todos os vértices de grau ímpar
        
        Assim, o algoritmo encontra um ciclo Euleriano e o transforma em um ciclo Hamiltoniano
        
        O algoritmo tem um processo semelhante ao Twice Around The Tree, mas faz um uso mais inteligente da minimum spanning tree
    - - Para instâncias euclidianas do Problema do Viajante, é possível obter aproximações melhores a partir das heurísitas de busca local
        
        Ele utiliza um percurso gerado por um algoritmo mais simples, como o do vizinho mais próximo, alterando-o em busca de um percurso melhor
        
        Essa alteração se trata de trocar as linhas usadas no caminho por outras
        
        Essa troca varia por implementação. No algoritmo de 2-opt ou 2-change, por exemplo, duas linhas não adjacentes são removidas e seus vértices são conectados aos vértices da outra linha
        
        Se o resultado da alteração for um percurso menor, o novo percurso é tratado como o atual e o algoritmo continua em busca de um menor
        
        Se o algoritmo não encontrar um percurso menor, ele retorna o atual como ouput
    - - Algoritmos Gulosos para o Knapsack Problem
        
        Esse algoritmo se baseia em três etapas
        
        1- Ordenar as razões dos valores pelos pesos dos itens
        
        2- Ordenar os itens em ordem decrescente de acordo com essas razões em uma lista
        
        Isso é feito porque tanto os valores quanto os pesos são importante para determinar a solução. Então não se pode usar um ignorando o outro
        
        3- Se o item atual da lista couber na mochila, inserí-lo lá, se não, passar para o próximo
        
        Essa etapa deve ser repetida até que não sobre itens na lista
        
        Esse algoritmo, é claro, nem sempre gera uma solução ótima
      - Algoritmo Guloso para o Continuous Knapsak Problem
        
        1- Computar as razões dos valores pelos pesos
        
        2- Ordenar os itens em uma lista em ordem não crescente
        
        3- Se o item atual couber inteiramente na mochila, inserí-lo inteiro e seguir para o próximo. Se não, inserir a maior fração que couber na mochila e parar
        
        Esse algoritmo sempre gera uma solução ótima para o problema