Avaliação comparativa do desempenho entre processadores CPU e GPU para o problema do caixeiro viajante
um estudo de benchmarking computacional utilizando algoritmo de força bruta
DOI:
https://doi.org/10.47385/cadunifoa.v21.n56.5758Palavras-chave:
Problema do Caixeiro Viajante, CUDA, Computação Paralela, GPU, Otimização CombinatóriaResumo
O Problema do Caixeiro Viajante (PCV) é um dos problemas de otimização combinatória mais estudados na ciência da computação e pertence à classe NP-difícil. Este trabalho apresenta uma análise comparativa entre implementações sequenciais em CPU e implementações paralelas em GPU utilizando CUDA para resolver o PCV por meio do algoritmo de força bruta. O estudo foi realizado em Python com as bibliotecas NumPy e CuPy no ambiente do Google Colab. Para um grafo com 10 vértices, totalizando 362.880 permutações, a implementação em GPU apresentou um speedup de 1,30x em relação à CPU, reduzindo o tempo de execução de 1,3622 segundos para 1,0450 segundos. Os resultados destacam o potencial da computação paralela em GPU para problemas de otimização combinatória, especialmente quando o volume computacional justifica a sobrecarga de transferência de dados entre CPU e GPU.
Downloads
Referências
APPLEGATE, D. L. et al. The traveling salesman problem: a computational study. Princeton: Princeton University Press, 2007.
GUTIN, G.; PUNNEN, A. P. The traveling salesman problem and its variations. Boston: Springer, 2006. DOI: https://doi.org/10.1007/b101971
KIRK, D. B.; HWEU, W. W. Programming massively parallel processors: a hands-on approach. 3. ed. Burlington: Morgan Kaufmann, 2016.
LAWLER, E. L. et al. The traveling salesman problem: a guided tour of combinatorial optimization. Chichester: Wiley, 1985. DOI: https://doi.org/10.2307/2582681
MITTAL, S.; VETTER, J. S. A survey of CPU-GPU heterogeneous computing techniques. ACM Computing Surveys, v. 47, n. 4, p. 1-35, 2015. Available at: https://dl.acm.org/doi/10.1145/2788396. Accessed on: 20 maio 2025. DOI: https://doi.org/10.1145/2788396
SANDERS, J.; KANDROT, E. CUDA by example: an introduction to general-purpose GPU programming. Boston: Addison-Wesley, 2010.
Binjubeir, Mohammed Mahfoudh & Ismail, Mohd Arfian & Tusher, Ekramul Haque & Aljanabi, Mohammad. (2024). A GPU Accelerated Parallel Genetic Algorithm for the Traveling Salesman Problem. Journal of Soft Computing and Data Mining. 5. 137-150. Available at: http://umpir.ump.edu.my/id/eprint/43901/. Accessed on: 26 maio 2025.
EKER, Musa; ŞEN, Baha; KUMRU, Pinar Yildiz. An efficient solving of the traveling salesman problem: the ant colony system having parameters optimized by the Taguchi method. Turkish Journal of Electrical Engineering and Computer Sciences, v. 21, n. 7, art. 15, 2013. DOI: https://doi.org/10.3906/elk-1109-44. Available at: https://journals.tubitak.gov.tr/elektrik/vol21/iss7/15. Accessed on: 6 jun. 2025.
K. Rocki and R. Suda. High Performance GPU Accelerated Local Optimization in TSP. 2013 IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum, Cambridge, MA, USA, 2013, pp. 1788-1796, doi: 10.1109/IPDPSW.2013.227. Accessed on: 6 mai. 2025. DOI: https://doi.org/10.1109/IPDPSW.2013.227
FUJIMOTO, N. TSUTSUI, S. A highly-parallel TSP solver for a GPU computing platform. In: INTERNATIONAL CONFERENCE ON PARALLEL PROCESSING AND APPLIED MATHEMATICS, 2010. Available at: https://link.springer.com/chapter/10.1007/978-3-642-18466-6_31. Accessed on: 1 mai. 2025.
FOSIN, J.; DAVIDOVIĆ, D.; CARIĆ, T. A GPU implementation of local search operators for symmetric travelling salesman problem. Promet - Traffic & Transportation, v. 25, n. 3, p. 225-234, 2013. Available at: https://hrcak.srce.hr/clanak/164448. Accessed on: 10 mai. 2025. DOI: https://doi.org/10.7307/ptt.v25i3.300
Downloads
Publicado
Como Citar
Edição
Seção
Licença
Copyright (c) 2026 Cadernos UniFOA
Este trabalho está licenciado sob uma licença Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Declaração de Transferência de Direitos Autorais - Cadernos UniFOA como autor(es) do artigo abaixo intitulado, declaro(amos) que em caso de aceitação do artigo por parte da Revista Cadernos UniFOA, concordo(amos) que os direitos autorais e ele referentes se tornarão propriedade exclusiva desta revista, vedada qualquer produção, total ou parcial, em qualquer outra parte ou meio de divulgação, impressa ou eletrônica, sem que a prévia e necessária autorização seja solicitada e, se obtida, farei(emos) constar o agradecimento à Revista Cadernos UniFOA, e os créditos correspondentes. Declaro(emos) também que este artigo é original na sua forma e conteúdo, não tendo sido publicado em outro periódico, completo ou em parte, e certifico(amos) que não se encontra sob análise em qualquer outro veículo de comunicação científica.
O AUTOR desde já está ciente e de acordo que:
- A obra não poderá ser comercializada e sua contribuição não gerará ônus para a FOA/UniFOA;
- A obra será disponibilizada em formato digital no sítio eletrônico do UniFOA para pesquisas e downloads de forma gratuita;
- Todo o conteúdo é de total responsabilidade dos autores na sua forma e originalidade;
- Todas as imagens utilizadas (fotos, ilustrações, vetores e etc.) devem possuir autorização para uso;
- Que a obra não se encontra sob a análise em qualquer outro veículo de comunicação científica, caso contrário o Autor deverá justificar a submissão à Editora da FOA, que analisará o pedido, podendo ser autorizado ou não.
O AUTOR está ciente e de acordo que tem por obrigação solicitar a autorização expressa dos coautores da obra/artigo, bem como dos professores orientadores antes da submissão do mesmo, se obrigando inclusive a mencioná-los no corpo da obra, sob pena de responder exclusivamente pelos danos causados.
