programaçao

Disciplina: Inteligência Artificial
Professora: Inês Dutra
Alunas: Aline Marins Paes
Paula Fernanda M. V. de Carvalho

Algoritmos de busca aplicados ao jogo dos oito

Introdução

Os algoritmos de busca são utilizados para encontrar uma sequencia de ações que, partindo de um estado inicial, levem a uma determinada configuração desejada. Assim, estes algoritmos geram novos estados a partir da aplicação de operadores no estado corrente, até que seja alcançada a solução. Portanto, dado um problema, deve ser definido seu estado inicial, final e os operadores que serão aplicados para gerar novos estados.
Normalmente estes algoritmos são avaliados de acordo com a completude, ou seja, se conseguem chegar a uma solução, otimalidade, que diz respeito a encontrar a solução ótima e complexidades de tempo e de espaço.
Este trabalho se propõe a exibir o funcionamento de alguns métodos de busca conhecidos aplicados ao jogo dos oito. O jogo dos oito, bastante popular, consiste em um tabuleiro de 3 linhas por 3 colunas que, partindo de qualquer estado inicial que contenha algarismos de 1 a 8 e mais um quadrado vazio chegue ao seguinte estado final:

1
2
3
8

4
7
6
5

Os operadores podem ser representados como mover o espaço em branco para cima, para a esquerda, para a direita ou para baixo.
A seguir será explicado como funciona o programa e os métodos de busca implementados.

Algoritmos de busca

Métodos de busca informados

Os algoritmos de busca que utilizam alguma informação específica do problema para gerar um novo estado são chamados de métodos de busca informados. Geralmente é utilizada uma função de avaliação heurística que procura estimar quantos passos são necessários para chegar à solução. No caso específico do jogo dos oito implementado neste trabalho, a heurística utilizada foi a quantidade de peças que estão fora do lugar em relação ao estado objetivo. Foram implementados os seguintes métodos de busca informados:

Busca