Uma proposta de uma variante otimizada do algoritmo A* para sistemas multi-núcleo

Resumo

Este artigo propõe uma variante otimizada do algoritmo A* para melhorar o desempenho em sistemas multi-núcleo. A abordagem proposta envolve a utilização de filas prioritárias locais (min-heaps) em cada tarefa ou núcleo, permitindo o processamento em paralelo. A comunicação entre as tarefas é realizada por meio de um buffer compartilhado do tipo produtor/consumidor, permitindo a troca de informações sobre os nós sucessores. Um protótipo é descrito, envolvendo a implementação das estruturas de dados, a lógica das tarefas, a comunicação entre as tarefas e a avaliação do desempenho em sistemas multi-núcleo. Os resultados preliminares mostram um ganho de desempenho em comparação com a versão sequencial do algoritmo A*.