Implementação do Algoritmo A* aplicado na Resolução do Problema do Puzzle8

Departamento de Sistema de Informação e Engenharia de Computação
Pontifícia Universidade Católica de Minas Gerais (PUCMINAS) – BH – MG – Brasil
Márcia B. de Almeida, Matheus M. de O. Paschoal e Rafael Moreira da Silva
Implementação do Algoritmo A* aplicado na Resolução do Problema do Puzzle8

I. INTRODUÇÃO
Este trabalho tem por objetivo implementar o algoritmo A *(A-estrela) para resolução do problema do Puzzle8. O algoritmo de busca informada A* é muito utilizado em aplicações que varia entre aplicativos para encontrar rotas de deslocamento entre localidades a resolução de problemas como o Puzzle8, dentre outros jogos.
O Algoritmo de busca bidirecional tem o potencial de serem os mais eficientes quando comparados com algoritmos unidirecionais. Algumas pesquisas mostram que através de algoritmos bidirecionais são encontrados espaços de procura menores. Tem–se ainda que a implementação da bidirecional em paralelo realiza uma redução substancial no tempo de funcionamento, gerando assim outra motivação. Por outro lado, isso não significa que o algoritmo unidirecional rodará mais rapidamente, isto dependerá do computacional overheads envolvido no algoritmo bidireccional, que são observados neste trabalho.
Através do Compilador Eclipse, foi desenvolvido em Java a implementação deste trabalho, onde foram exploradas a admissibilidade das heurísticas aplicadas.

ALGORITMO A* O algoritmo