Quebra-Cabeças de Loyd: um estudo de paralelização
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
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
Publicado
16/05/2024
Como Citar
OLIVEIRA, Júlia A. S.; TREVISAN, João P.; FURUYAMA, Jayme S. R.; GUARDIA, Hélio.
Quebra-Cabeças de Loyd: um estudo de paralelização. In: ESCOLA REGIONAL DE ALTO DESEMPENHO DE SÃO PAULO (ERAD-SP), 15. , 2024, Rio Claro/SP.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2024
.
p. 17-20.
DOI: https://doi.org/10.5753/eradsp.2024.239923.
