Please enable JavaScript.

Coggle requires JavaScript to display documents.

Programação dinâmica, Algoritmos de aproximação para problemas NP-hard -…

- - - - algoritmo do vizinho mais próximo
        
        sempre ir para a cidade vizinha não-visitada mais próxima
        
        razão de performance infinita
      - algoritmo de multifragmentos
        
        encontrar um conjunto de arrestas mínimas com vértices de grau 2
        
        razão de performance infinita
    - - desigualdade triangular
        
        a distância do caminho entre i e j não pode exceder a distância entre elas passando por uma terceira cidade k intermediária
      - simetria
        
        a distância de i até j é a mesma de j até
      - heurísticas de busca local
        
        algoritmo 2-opt
        
        deleta duas arestas não-adjacentes e reconecta suas extremidades gerando um caminho diferente do que se possuía anteriormente
        
        algoritmo 3-opt
        
        funcionamento análogo ao 2-opt
        
        algoritmo de Lin-Kernighan
        
        um algoritmo de opt variável
    - - algoritmo twice-around-the-tree
      - algoritmo de Christofides
        
        produz aproximações significativamente melhores que o twice-around-the-tree
  - - - famílias paramétricas de algoritmos que permitem aproximações com qualquer de nível de precisão predefinido
      - tempo para determinar os subconjuntos em Ohm(n)
      - eficiência temporal em Ohm(kn^k+1)
        
        polinomial em n, mas exponencial em k
    - - esquemas sem a relação exponencial de k