Grafos Aplicados ao Problema do Caixeiro Viajante
Palavras-chave:
Teoria dos GrafosResumo
O Problema do Caixeiro Viajante é um problema clássico de otimização combinatória. Tendo em vista isso, surgiram diversos algoritmos que visam solucionar esse problema. Assim, este estudo tem o objetivo de realizar uma análise comparativa entre alguns algoritmos utilizando grafos, observando a diferença no tempo que cada algoritmo demora para solucionar o problema com a mesma entrada de Grafo.
Referências
Bovet, D. P., Crescenzi, P., and Bovet, D. (1994). Introduction to the Theory of Complexity, volume 7. Prentice Hall London.
Burguetti, R. (2022). Alguns tipos de grafos e aplicações.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2022). Introduction to algorithms. MIT press.
Cunha, C. B., de Oliveira Bonasser, U., and Abrahão, F. T. M. (2002). Experimentos computacionais com heurísticas de melhorias para o problema do caixeiro viajante. In XVI Congresso da Anpet.
Feofiloff, P., Kohayakawa, Y., and Wakabayashi, Y. (2011). Uma introdução sucinta à teoria dos grafos.
Laporte, G., Mercure, H., and Nobert, Y. (1986). An exact algorithm for the asymmetrical capacitated vehicle routing problem. Networks, 16(1):33–46.
Lima, A. d. S. C. (2014). Aproximação experimental da complexidade assintótica de shaders para dispositivos móveis utilizando opengl es.
Martinez, J. G. A. et al. (2019). Caracterização teórica e limites assintóticos para o problema da geração de redes candidatas na busca por palavras-chave em bancos de dados relacionais.
Silva, G. A. N. d., Silva, F. A. d., Russi, D. T. A., Pazoti, M. A., and Siscoutto, R. A. (2013). Algoritmos heurísticos construtivos aplicados ao problema do caixeiro viajante para a definição de rotas otimizadas. Colloquium Exactarum. ISSN: 2178-8332, 5(2):30–46.
Downloads
Publicado
Edição
Seção
Categorias
Licença
Este trabalho está licenciado sob uma licença Creative Commons Attribution-ShareAlike 4.0 International License.
Os autores mantêm os direitos autorais sobre os trabalhos publicados nesta revista, concedendo à SETIF o direito de primeira publicação. O conteúdo está licenciado sob uma Licença Creative Commons Atribuição-CompartilhaIgual 4.0 Internacional (CC BY-SA 4.0), que permite copiar, redistribuir, remixar, transformar e criar a partir do material para qualquer finalidade, inclusive comercial, desde que seja atribuída a autoria e feita referência à publicação original nesta revista.
Os autores concordam que qualquer reutilização de seu trabalho por terceiros deve incluir o nome dos autores, o título do artigo, o nome da revista, o DOI (quando disponível) e o link para a licença.
É permitido e incentivado que os autores disponibilizem a versão publicada do trabalho em repositórios institucionais, sites pessoais ou redes acadêmicas imediatamente após a publicação, com menção à publicação inicial nesta revista.
