qr code

Problema 8-Puzzle: Análise da solução usando Backtracking e Algoritmos Genéticos
Nelson Florêncio Junior, Frederico Gadelha Guimarães
PPGCC - Programa de Pós-Graduação em Ciência da Computação
UFOP - Universidade Federal de Ouro Preto
Ouro Preto, Minas Gerais, Brasil email: [e-mail], [e-mail]

Resumo—Com jogos de tabuleiro, como o 8-Puzzle, onde existem regras bem definidas podemos gerar um espaço de busca bem definido, porém algumas soluções podem ser custosas para o desempenho de um determinado computador. Dado o problema podemos resolvê-lo com uma busca de estados em um grafo, onde cada nó do grafo representa um estado (configuração) do Puzzle. Deve-se então encontrar um caminho num grafo que leve ao estado final, no caso um puzzle ordenado. Os
Algoritmos Genéticos, pertencentes a Computação Evolutiva, proporcionam uma busca inteligente, evoluindo baseando-se nos resultados obtidos de testes anteriores, diferentimente do algoritmo baseado no paradigma Backtracking (Tentativa e
Erro), onde testamos todos os caminhos possíveis num grafo até encontrar a solução. Desenvolvendo os algoritmos e comparando seus resultados por meio de uma ánálise de compexidade podemos chegar a uma conclusão de qual paradigma se encaixa melhor ao problema ou em que situação cada um se encaixa melhor. Keywords-8-Puzzle, Algoritimos Genéticos, Backtracking e complexidade. I. I NTRODUÇÃO
A. 8-Puzzle
O jogo do 8-Puzzle é um jogo de tabuleiro de blocos deslizáveis. O problema é bastante abordado na disciplina de Inteligência Artifial, segundo [1], além do seu apelo intelectual inerente, os jogos de tabuleiro tem certas propriedades que os tornaram objetos de estudo ideal para trabalhos inicias. O objetivo do jogo é mover as peças a partir de um estado inicial até encontrar seu estado final, quando o Puzzle está ordenado de forma crescente, como na Figura 1. As regras do jogo são bastante simples, a peça vazia é a única que
pode