Primeiro Trabalho de IA/SI

Estimativa de término: 03/03/2017 (3 semanas)

13 de Fevereiro de 2017

Este trabalho é para ser submetido via Moodle. Será desenvolvido principalmente durante as aulas práticas, mas espera-se que o estudante complemente com trabalho extra-classe. Os testes e exames terão perguntas relacionadas com este trabalho. 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 15 é representado por uma matriz 4x4 onde há 15 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 os algoritmos A* e guloso. Dadas as configurações inicial e final, o seu program deve imprimir os operadores utilizados no caminho que leva à solução ótima (caminho que contém o menor número de passos desde a configuração inicial até a configuração final). Apresente uma função de custo para este problema e utilize-a na sua implementação.

Para um conjunto de configurações iniciais e finais, este problema, assim como a sua versão reduzida - jogo dos oito, não tem solução. Investigue sobre este assunto e escreva um código que verifique se, para uma dada configuração inicial do jogo dos 16, há um caminho que leve à solução final, SEM fazer nenhuma busca.

Compare a sua implementação com os resultados produzidos pelos seguintes métodos de procura:

• busca em profundidade
• busca em largura
• busca em profundidade iterativa

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 (Qual é a profundidade da solução encontrada? A solução encontrada corresponde ao menor número de passos para chegar da configuração inicial à final ou com menor custo utilizando pouco tempo e pouca memória?)

Utilize as seguintes configurações iniciais:

1	2	3	4		1	2	3	4
5	6	8	12		13	6	8	12
13	9		7		5	9		7
14	11	10	15		14	11	10	15

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

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15

A primeira configuração tem solução ótima em profundidade 12 (menor nmero 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. 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.

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).