Primeiro Trabalho de Sistemas Inteligentes

Entrega: 13/03/2012

4 de Março de 2012

Este trabalho vale nota e será utilizado para computar a média junto com as notas das provas e dos outros trabalhos.

O jogo dos 8 pode ser representado por um quadrado 3x3 onde há 8 quadrados numerados e um quadrado em branco. O problema é sair de uma configuração inicial de algarismos (estado inicial) e chegar a um dado estado final com outra configuração de algarismos. Os movimentos possíveis para se chegar de uma configuração a outra são: 1) mover o branco para cima, 2) mover o branco para baixo, 3) mover o branco para a direita e 4) mover o branco para a esquerda.

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

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

As estratégias podem ser implementadas em qualquer linguagem.

Para cada estratégia, analise complexidade temporal (tempo para chegar a uma solução), complexidade espacial (número de nós armazenados), completude (o algoritmo consegue encontrar uma solução?) e otimalidade (o algoritmo consegue encontrar a solução ótima em tempo hábil e utilizando pouca memória? Qual a profundidade da solução?)

Utilize as seguintes configurações iniciais:

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

A configuração final é a seguinte:

1	2	3
8		4
7	6	5

Todos (grupos e individuais) devem entregar:

1. trabalho escrito com o estudo das estratégias;

   Organização do trabalho escrito:

   1. Introdução
      • O que são algoritmos de busca não informados e para que servem.
      • O que são algoritmos de busca informados e para que servem.
   2. Estratégias
      • Busca em Profundidade (O que é e quando se aplica)
      • Busca em Largura (O que é e quando se aplica)
      • Busca Iterativa Limitada em Profundidade (O que é e quando se aplica)
      • Busca Gulosa
        • O que é e quando se aplica
        • Qual foi a heurística utilizada para cada problema resolvido e por que esta heurística foi escolhida?
      • Busca A*
        • O que é e quando se aplica
        • Qual foi a heurística utilizada para cada problema resolvido e por que esta heurística foi escolhida?
   3. Resultados

      Tabela com tempos de execução, utilização de memória e se encontrou a solução, para cada configuração, para cada estratégia, além da profundidade da solução encontrada.

   4. Comentários Finais e Conclusões

      Comentar sobre as estratégias fazendo uma comparação entre o seu desempenho e eficácia para encontrar as soluções. Concluir dizendo qual foi a melhor estratégia.

   5. Bibliografia

2. enviar por email o código fonte dos programas, como compilar e formato da entrada para cada problema, isto é, um pequeno manual de como rodar os programas (pode ser um 'help' ou 'readme'). Além disso, em que ambiente foi compilado (tipos e versões do SO e da linguagem). Seu programa deve correr na minha máquina (com mandriva instalado). Não assuma que eu tenho uma IDE (Integrated Development Environment) de qualquer tipo. O programa deve correr na linha de comando.

   Enviar para: ines@dcc.fc.up.pt com o seguinte ``subject'': PRIMEIRO TRABALHO DE SI - BUSCAS

   Por favor, utilize este ``subject'' na sua mensagem.

   Pode também enviar seu trabalho através de dropbox.

O trabalho pode ser feito em grupo de no máximo três pessoas. Todos os trabalhos deverão ser apresentados em data a combinar. Todos os componentes do grupo deverão estar presentes durante a demonstração. Um dos componentes do grupo será aleatoriamente escolhido para responder perguntas. Quem não estiver presente vai ter nota zero! Cada componente do grupo deverá comentar sobre sua contribuição no trabalho.