Artigo n-puzzle

Utilização da heurística de Manhattan na solução do problema N-Puzzle
Ricardo Ferreira1, Sandro Menezes2
Centro de Ciências Tecnológicas – Universidade do Estado de Santa Catarina (UDESC)
89.219-710 – Joinville – SC – Brasil
{ricardo_ferreiratj,sandrolmenezes}@hotmail.com
Abstract. The n-puzzle problem is computationally classified as intractable in the NP-Hard problem class, having its brute force solution with O(3ⁿ) complexity. This article shows that with the use of Manhattan heuristics through some algorithms, A* and IDA*, in solving small instances of N-Puzzle, 8-Puzzle and 15-Puzzle problems, it is possible to find an optimal solution in exponential time. Furthermore, it is covered an algorithm involving agents concept, which also uses Manhattan heuristics to find acceptable solutions in O(N² √N)) time.
Resumo. Computacionalmente o problema n-puzzle é classificado como intratável estando na classe de problemas NP-Hard, tendo assim sua solução de força bruta com complexidade O(3ⁿ). Esse artigo demonstra que com a utilização da heurística de Manhattan por alguns algoritmos, A* e IDA*, na solução de pequenas instâncias do problema N-Puzzle, 8-Puzzle e 15-Puzzle, é possível encontrar a solução ótima em tempo exponencial. É abordado também um algoritmo que envolve o conceito de agentes, que também se utiliza da heurística de Manhattan para o problema em questão encontrando soluções aceitáveis em tempo O(N² √N)).
1. Introdução
Para uma melhor compreensão do contexto do problema, inicialmente podemos mencionar um jogo que a maioria das pessoas já conhece, o quebra cabeça de 15 peças onde cada peça possui um valor único de 1 a 15 e inicialmente as peças estão numa disposição não ordenada e o objetivo do jogo é deixar as peças na ordem correta. Esse jogo é uma instância do problema N-Puzzle, onde n = 15. O problema vem sendo escolhido para ser utilizado como estudo de caso ao longo dos anos para testes de algoritmos de busca considerando o