Skip to content

Latest commit

 

History

History
39 lines (28 loc) · 1.54 KB

README.md

File metadata and controls

39 lines (28 loc) · 1.54 KB
Raw

Implementação de 5 heuristicas para TSP:

Foram implementadas as heuristicas :

  • Bellmore & Nemhauser,
  • Twice-Around,
  • Christofides,
  • Insere Vértice 1
  • e Insere Vértice 2

IMPORTANTE: Na implementação do Christofides, foi utilizado uma library apenas especificamente na parte do 'matching perfeito'. Fora isso, todo o resto foi feito inteiramente por mim.

Código:

Separo abaixo entre pastas, textos e arquivos interessantes para essa implementação.

Pastas:

  • "src" : Todo o código e textos então nesas pasta <\br>
  • "data" : Os dados da base de dado e serialização do grafos
  • "exgraph": As implementações dos Grafos, DiGrafos, MultiGrafos, além de algums algortimos uteis como 'hierholzer' e 'prims'
  • "ds" : Estrutura de dados auxiliares

Textos:

  • "TSP Heuristic Tours Info {nome da heuristica}.txt" : Ciclos encontrados, informações sobre tempo de excução, custos e outras info.

Arquivos:

  • "tspheuristics.py" : Algoritmos implementados para cada Heuristica
  • "tspgraphs.py" : Coleta e serialização dos grafos retirados da base de dados fornecida.
  • "main.py" : Começo do programa
  • "utils.py" : Funções uteis

Artigo:

Basta abrir o file "Everton Santos de Andrade Júnior - Uso de Heuristicas para o Problema de TSP.pdf" Contém detalhes da implementação, explicação teorica, tabela informando tempo de execução, complexidade computacional, e custos encontrados pelas heuristicas

OBS:

Qualquer esclarecimento ou problemas, por favor fale comigo, email: [email protected]