Implementação do algoritmo a* aplicado na resolução do problema do puzzle8

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 foi descrito pela primeira vez em 1968 por Peter Hart, Nils Nilsson, e Bertram Raphael. Em suas publicações, o algoritmo A foi o nome dado por eles; Ao longo do tempo começaram a usa-lo com uma heurística apropriada onde atingiu-se um comportamento ótimo, e passou a ser conhecido por A*.
Trata-se de uma busca pela melhor escolha, que avalia os estados de um problema, através de uma combinação de uma função que verifica o custo para alcançar cada estado com uma função que verifica o custo para ir