Quebra-Cabeças de Loyd: um estudo de paralelização

• Júlia A. S. Oliveira UFSCar
• João P. Trevisan UFSCar
• Jayme S. R. Furuyama UFSCar
• Hélio Guardia UFSCar

DOI: https://doi.org/10.5753/eradsp.2024.239923

Resumo

Este artigo apresenta um estudo sobre a implementação de solução paralela para o Loyd's Tile Puzzle (LTP), um desafio de complexidade NP-hard. Para tanto, propõe-se uma abordagem de paralelização usando múltiplas threads em ambiente com memória compartilhada. Também é abordada a viabilidade de uso de GPUs para otimizar o processo, discute-se o potencial das GPUs como alternativas promissoras para a paralelização e otimização do problema, explorando extensivamente o espaço de caminhos possíveis.

Referências

APPROBATO, Daví Carlos Uehara. (2019) Distância, na matemática e no cotidiano. Tese (Doutorado) - Universidade de São Paulo, São Paulo, 2019.

BOROVSKA, Plamenka. (2006). Parallel Combinatorial Search on Computer Cluster: Sam Loyd’s Puzzle. In: International Conference on Computer Systems and Technologies-CompSysTech.

BRÜNGGER, Adrian. (1997). Solving hard combinatorial optimization problems in parallel: two case studies. ETH Zurich.

BRÜNGGER, A.; MARZETTA, A.; FUKUDA, K. et al. (1999). The parallel search bench ZRAM and its applications. Annals of Operations Research, v. 90, p. 45-63. Disponível em: DOI: 10.1023/A:1018972901171. Acesso em: 10 mar. 2024.

RODRIGUES, Rodrigo Matheus da Costa. (2009). Uma comparação experimental entre algoritmos para seleção de características. Monografia (BI) - Centro de Ciências Exatas e Tecnológicas, Universidade Estadual do Oeste do Paraná, Cascavel.

TRAPA, Peter. (2004). Permutations and the 15-Puzzle. Math Circle Notes, v. 2, n. 02, University of Utah. Disponível em: [link]. Acesso em: 10 mar. 2024.

Marathon of Parallel Programming. (2008). Disponível em: [link]. Acesso em: 7 abr. 2024