Please enable JavaScript.

Coggle requires JavaScript to display documents.

Dynamic programming, Approximation algorithms for NP -Hard problems -…

- - - - 1 = moeda
      - 0 = sem moeda
- - - - criação de uma tabela para armazenar os valores
        
        todas as entradas são iniadas com um símbolo que corresponde a "nulo"
        
        sempre que um valor precisar ser calculado, verifica-se a tabela antes
        
        se posição for nula: calcula e armazena o valor
        
        se posição não nula, pega o valor já calculado
- - - - 1 - escolhe uma cidade inicial
      - 2 - sempre visita a mais próxima
      - 3 - após todos serem visitados retorna ao vértice inicial
    - - 1 - ordena as aréstas em ordem crescente
      - 2 - adiciona a solução evitando vértices de 3° grau e ciclos<n
      - 3 - repete nx (n = número de cidaes)
      - 4 - retorna o set de cidades
  - - - 1 - construir a MST correspondendo a instância
      - 2 - percorrer eliminando repetições
    - - 1 - adicione arestas de um emparelhamento mínimo dos vértices de grau ímpar
        na MST
      - 2 - encontre o circuito euleriano e faça atalhos para o hamiltoniano
  - - - melhoram a performance substituindo pares/trios para encontrar a solução
    - - é o mais complexo e mais eficiente dos algorítimos
        
        combina 2-opt e 3-opt
- - - - 1 - calcule a razão (valor/peso) para cada item
      - 2 - ordene em ordem decrescente
      - 3 - adicione os itens na ordem enquanto couber
    - - 1 - calcule a razão (valor/peso) para cada item
      - 2 - ordene em ordem decrescente
      - 3 - adicione os itens, podendo usar frações até a mochila encher
  - - - 1 - gera todas as combinações possíveis ate K itens
      - 2 - para cada combinação usa um "greedy algorithm" para adicionar os itens restastes a mochila
      - garante aproximação com qualquer precisão desejada
        
        desempenho = 1+(1/k)