ESTUDO COMPARATIVO DOS MÉTODOS DE BUSCA POR LARGURA, PROFUNDIDADE, A* HAMMING E MANHATTAN PARA SOLUÇÃO DO 8-PUZZLE

Resumo

Dentro da área de computação observa-se muitas sub-áreas entre elas destaca-se a de inteligência artificial. Dentro dessa, nota-se os métodos de busca inteligentes. O objetivo deste estudo é comparar o desempenho de quatro desses, sendo eles: busca por largura, profundidade, A* Hamming e A* Manhattan para a solução do 8-puzzle. Para implementação foi utilizado a linguagem Java. Os resultados obtidos indicaram que os métodos de busca por largura e ambos A* sempre encontraram a melhor solução. O método A* Manhattan sempre obteve os melhores resultados, seguido do A* Hamming. A busca por profundidade somente encontrou a solução para o primeiro caso testado, sendo não significativo para os demais testes. Através do estudo concluiu-se que os métodos baseados em heurísticas são mais complexos para implementar, porém apresentam performance significativamente melhor que os demais métodos. A busca por largura, apesar de não ser otimizada se mostrou relativamente eficiente para solução de problemas mais simples.