Primeiro Trabalho de Sistemas Inteligentes

Entrega: 23/03/2015

6 de Março de 2015

Este trabalho vale nota e será utilizado para calcular a média final junto com as notas das provas e dos outros trabalhos. Para saber o método e critério de avaliação, por favor consulte a ficha da unidade curricular na página do sigarra.

O jogo dos 8 é representado por uma matriz 3x3 onde há 8 células numeradas e uma célula em branco. Variações deste jogo podem conter parte de uma imagem em cada célula. O problema consiste em partir de uma configuração inicial embaralhada das células e chegar a uma configuração final com uma ordenação determinada de algarismos (no caso da matriz de números) ou de imagens (no caso da matriz onde as células representam partes de uma imagem). Os movimentos/operadores possíveis para se chegar de uma configuração a outra são: 1) mover a célula em branco para cima, 2) mover a célula em branco para baixo, 3) mover a célula em branco para a direita e 4) mover a célula em branco para a esquerda.

Dada a descrição do problema acima, implemente uma solução usando:

• as estratégias de busca não informadas busca em profundidade, busca em largura e busca em profundidade iterativa e aplique a este problema.
• as estratégias de busca informadas busca gulosa e busca A* e aplique a este problema.

A implementação pode ser em qualquer linguagem.

Para cada estratégia, analise:

• tempo para chegar a uma solução,
• quantidade de espaço gasto (número de nós gerados e armazenados),
• completude (o algoritmo consegue encontrar uma solução?) e
• otimalidade (o algoritmo consegue encontrar a solução no menor número de passos ou com menor custo em tempo hábil e utilizando pouca memória? Qual é a profundidade da solução?)

Utilize as seguintes configurações iniciais:

3	4	2		6	2	7
5	1	7		5		3
6		8		8	1	4

A primeira configuração tem solução ótima em profundidade 23 (menor número de movimentos possível para chegar da configuração inicial à configuração final).

A segunda configuração inicial não leva à configuração final proposta. No seu relatório explique o porque.

Apesar de propor apenas uma configuração inicial e final para teste, prepare o seu programa de forma a ser possível entrar com diversas configurações iniciais e finais. Portanto, escreva o seu código de forma que o utilizador possa escolher as configurações inicial e final. O seu código deve verificar se há solução para chegar do estado inicial ao estado final antes de iniciar a busca, e deve emitir uma mensagem de erro se não houver caminho entre a solução inicial e a final.

A configuração final de teste deve ser a seguinte:

1	2	3
8		4
7	6	5

Utilize o algoritmo 1 como base para implementar todas as buscas:

Este algoritmo recebe como parâmetro uma função de enfileiramento que será utilizada para ordenar a lista de nós (configurações) abertos (ainda não explorados).