Algoritmo A* Paralelo para a Solução Ótima dos Problemas do Cubo Mágico e Sliding Puzzle

• Leonardo Machado UnB
• Daniel Sundfeld UnB

DOI: https://doi.org/10.5753/eradco.2026.34578

Resumo

Algoritmos paralelos estão se tornando cada vez mais importantes para a computação, considerando o caminho seguido pela evolução do hardware. Por essa razão, o estudo de paralelismo torna-se necessário para que os softwares acompanhem essa evolução. O Algoritmo A* é um dos mais famosos algoritmos de busca e pode ser utilizado para solucionar uma quantidade enorme de problemas. No entanto, obter o paralelismo nesse algoritmo pode ser um desafio. Uma das estratégias de maior sucesso na literatura são algoritmos que usam funções de hash para distribuir os nós entre as threads. O presente trabalho, adapta essa estratégia para resolver o problema do Sliding Puzzle e Cubo Mágico. Os resultados experimentais foram obtidos em uma estação de 24 núcleos e 768 GB de RAM e foi possível obter um speedup médio de até 9,90× usando 24 threads.

Referências

Hart, P., Nilsson, N., and Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Trans Sys Sci and Cybernetics, SSC-4(2):100–107.

Khemani, C., Doshi, J., Duseja, J., Shah, K., Udmale, S., and Sambhe, V. (2018). Solving rubik’s cube using graph theory. In Computational Intelligence: Theories, Applications and Future Directions-Volume I: ICCI-2017, pages 301–317. Springer.

Kobayashi, Y., Kishimoto, A., and Watanabe, O. (2011). Evaluations of hash distributed a* in optimal sequence alignment. In IJCAI, pages 584–590.

Kouti, A. M. and Refanidis, I. (2023). Cpu and gpu parallelism of the a* algorithm on solving n-puzzle problems. In Proceedings of the 27th Pan-Hellenic Conference on Progress in Computing and Informatics, pages 21–25.

Sundfeld, D., Teodoro, G., and Melo, A. C. (2025). Pa-star2: fast optimal multiple sequence alignment for asymmetric multicore processors. In 2025 33rd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP), pages 146–153. IEEE.

Tanenbaum, A. S. and Bos, H. (2015). Modern operating systems. Pearson Education, Inc.