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 …exibir mais conteúdo…

Figura 2 – Exemplo estado inicial e final 15-Puzzle
3. Classificação do problema N-Puzzle
Se existisse um simples algoritmo que conseguisse achar a solução ótima para o problema, não faria sentido usarmos funções heurísticas como a de Manhatann. Dessa maneira temos que dizer de uma maneira convincente que esses algoritmos de fato ainda não existem, para isso baseia-se na teoria da complexidade. [Ratner e Warmuth, 1986]
Sendo assim o problema n-puzzle é classificado como NP-Hard segundo [Ratner e Warmuth, 1986], como ainda não se sabe se P=NP ou P≠NP faz-se o uso da heurística para encontrar a solução de uma instancia de n-puzzle.
4. Força Bruta
Dentre as maneiras para se resolver um problema n-puzzle, um dos métodos de mais fácil entendimento é denominado de força bruta, nesse caso não se faz o uso de nenhuma heurística para a busca da solução. O algoritmo verificará cada possibilidade de movimento até achar um caminho que chegue ao estado final. Para tanto podemos avaliar que só é possível realizar no máximo 3 movimentos distintos quando o espaço vazio encontra-se em algum lugar que não seja os cantos do tabuleiro, e no mínimo 1 movimento quando encontra-se nessa posição. Aqui estamos desconsiderando possíveis movimentos em loop, ou seja, movimentar o espaço em branco para o lugar que estava no estado