UNIVERSIDADE FEDERAL DO MATO GROSSO DO SUL
Autor: José Augusto Lajo Vieira Vital
Orientador: Edson Takashi Matsubara
Estudo: Implementação de diferentes métodos para a resolução do jogo 8Puzzle utilizando busca heurística.
Linguagem: Python
https://colab.research.google.com/drive/1Lqd1mlu298JAl9877Nk01XP8n7Dj6p6t?usp=sharing
Inicialmente um tabuleiro com 9 posições (3x3) é gerado com 8 números em posições aleatórias. O objetivo do jogador é utilizar o espaço vazio para movimentar as peças com determinado número de passos e obter a sequência numérica em ordem crescente de 1 até 8, e o vazio na ultima posição do tabuleiro. Cada movimentação é contabilizada como um passo.
O desenvolvimento foi com base em 4 modelos matemáticos:
Método que utiliza a quantidade de posições erradas em relação ao goal, ou seja, conta quantas peças estão na posição errada quando comparado com o estado resolução do problema. Essa função retorna a quantidade de elementos estão fora da sua posição correta.
A distância de Manhattan (“City Block” ou “Geometria do Táxi”) é um modelo geométrico em que a distância entre dois pontos é a soma das diferenças absolutas de suas coordenadas. Essa função retorna a distância da posição atual até a posição correta com base na métrica da Distância de Manhattan.
O método usa como parâmetro de resolução do puzze a função heurística (Heurística 1 ou 2) chamada de h(n).
f(n) = h1(n)
f(n) = h2(n)
O método usa como parâmetros de resolução do puzzle as funções h(n), e uma função g(n) que retorna o custo de determinado estado até o nó n.
f(n) = h1(n) + g(n)
f(n) = h2(n) + g(n)
