Primeiro Trabalho de Sistemas Inteligentes
Entrega: 04 de Março de 2013
22 de Fevereiro de 2013

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

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 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:

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

A configuração final é a seguinte:

1 2 3
8   4
7 6 5

O seu programa deve verificar se há solução para chegar do estado inicial ao estado final antes de começar a busca.

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.
      • Organização do trabalho (No capítulo 2...No Capítulo 3....)
    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

      Incluir 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. Referencias Bibliográficas

  2. enviar através do MoodleUP um arquivo zip ou similar contendo o código fonte dos programas, instruções de como compilar e executar cada problema, isto é, um pequeno manual de como correr os programas (pode ser um 'help' ou 'readme'). Além disso, devem incluir uma pequena documentação explicando em que ambiente seu programa foi compilado (tipos e versões do SO e da linguagem). Seu programa deve correr na minha máquina (com fedora core 17 instalado). Não assuma que eu tenho uma IDE (Integrated Development Environment) de qualquer tipo. O programa deve correr na linha de comando.

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.



Inês Dutra 2013-02-23