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:
Organização do trabalho escrito:
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.
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.
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.