Inteligência Artificial
Instituto Superior Técnico
LEIC 2009/2010
Enunciado do Projecto
1 Introdução
Este documento descreve o projecto a realizar na cadeira de Inteligência
Artificial no ano lectivo de 2009/2010.
O trabalho proposto tem de ser implementado na linguagem Common Lisp 1
e deve ser realizado em grupos de um, dois ou três alunos. A inscrição de grupos e entrega do projecto deverá ser realizada através do sistema Fénix. Para
o efeito, os grupos de alunos terão obrigatoriamente que proceder à inscrição
no sistema Fénix até ao final do dia 6 de Novembro de 2009.
2 Descrição do Puzzle H IDATO
O puzzle H IDATO é um puzzle introduzido por uma matemático Israelita,
Gyora Benedek.
Cada puzzle é caracterizado por um tabuleiro que vamos assumir ser rectangular 2 , com a dimensão n × m. Cada célula do tabuleiro pode conter um
número inteiro de 1 a n × m. Inicialmente estão sempre colocados os números
1 e n × m no tabuleiro, mas podem estar colocados outros números para além
destes.
Um puzzle H IDATO é resolvido colocando um número inteiro de 1 a n ×
m em cada célula não vazia, de tal modo que as seguintes regras não sejam
violadas:
• Cada número inteiro de 1 a n × m é associado a uma única célula do
tabuleiro.
• Os números colocados nas células do tabuleiro são consecutivos, ou seja,
na vizinhança (horizontal, vertical ou diagonal) de cada célula existe
1
O projecto será avaliado usando o CLISP (http://clisp.cons.org/) versão 2.47 com a opção
-ansi num servidor Intel Xeon 5160 (3.0GHz, 1333Mhz, 4MB) com o sistema operativo Red
Hat Enterprise Linux WS 4.
2
Na realidade o tabuleiro não tem necessariamente de ser rectangular, mas vamos considerar
que é rectangular por uma questão de simplicidade.
1
6
9
6 7 9
2 8
5 2 8
1
1 4 3
Figura 1: O puzzle H IDATO - exemplo
uma célula que contém o sucessor e uma célula que contém antecessor
do número contido nessa célula. São excepção o número 1, em relação ao
qual só existe o sucessor, e o número n × m, em relação ao qual só existe
o antecessor.
Os puzzles de H IDATO bem construı́dos contêm apenas uma solução.
A figura 1 apresenta o tabuleiro inicial e o tabuleiro final para uma instância
do puzzle H IDATO.
3 Função resolve-hidato
Deverá ser implementada a função resolve-hidato que recebe um tabuleiro inicial de H IDATO e devolve um tabuleiro solução. Para implementar
esta função podem ser escolhidas as estratégias que forem mais apropriadas
de modo a garantir que os problemas são resolvidos de um modo eficiente.
Devem no total ser implementadas três estratégias diferentes.
Um exemplo de execução para o exemplo anterior seria:
> (resolve-hidato ’((6 0 9)(0 2 8)(1 0 0)))
((6 7 9)(5 2 8)(1 4 3))
Repare que a função resolve-hidato recebe uma lista de listas, em que
cada lista corresponde a uma linha do tabuleiro, e em que uma célula vazia
contém o número 0 e uma célula não vazia contém um número inteiro entre 1
e n×m. (Pode assumir que esta função recebe sempre um tabuleiro de H IDATO,
pelo que não será testada com argumentos inválidos.)
O tabuleiro devolvido pela função resolve-hidato é um tabuleiro cujas
células inicialmente não vazias se mantêm inalteradas e cujas células inicialmente vazias contêm um número inteiro entre 1 e n × m de tal modo que não
são violadas as regras do jogo.
4 Prazos e Entrega
O projecto deverá ser entregue através do sistema Fénix em formato electrónico
até às 15:00 do dia 30 de Novembro de 2009. A entrega electrónica consistirá na entrega de um ficheiro <num-grupo>.zip que deverá conter um ficheiro <num-grupo>.lisp e um ficheiro <num-grupo>.pdf. O ficheiro
2
<num-grupo>.lisp deverá conter todo o código implementado, incluindo a
função resolve-hidato que deverá utilizar a estratégia mais competitiva. (Note
que o código das restantes estratégias também deve estar contido neste ficheiro.) O ficheiro <num-grupo>.pdf deverá conter o relatório do projecto.
Entregas que não estejam nestas condições (por exemplo: ficheiros .rar, ficheiros contidos numa directoria, extensões .lsp ou .doc) não serão avaliados.
O código a ser entregue deverá observar rigorosamente o formato descrito na secção anterior. Projectos que não observem este formato serão classificados com 0 valores.
Eventuais atrasos na entrega serão penalizados com 2 valores para entregas realizadas entre as 15:01 do dia 30 de Novembro e as 15:00 do dia 1 de
Dezembro e com 4 valores para entregas realizadas entre as 15:01 do dia 1 de
Dezembro e as 15:00 do dia 2 de Dezembro. Excedido este prazo não serão
aceites mais projectos.
5 Avaliação
Ao relatório será atribuı́da uma cotação entre 0 e 6 valores, e ao código será
atribuı́da uma cotação entre 0 e 14 valores.
O relatório será avaliado em função da clareza e do conteúdo. O conteúdo
deverá descrever essencialmente: (1) as estruturas de dados implementadas,
(2) as três estratégias utilizadas para resolver o problema, as quais devem ser
relacionadas com a matéria leccionada na cadeira, e (3) uma tabela com os
resultados obtidos 3 para a aplicação das três estratégias nos exemplos disponibilizados, seguida de um comentário aos resultados que constam na tabela.
O relatório está limitado a 10.000 caracteres (incluindo espaços).
O código será avaliado em função da qualidade e correcção (4 valores) e
do número de instâncias que conseguir resolver (10 valores). Será oportunamente disponibilizado um conjunto de instâncias. Parte destas instâncias
serão usadas na avaliação final, juntamente com outras instâncias não revelados antecipadamente. (Note que cada uma destas instâncias terá apenas uma
solução.)
6 Detecção de Cópias
A avaliação dos projectos inclui a utilização de um sistema para detecção
de cópias. Os alunos cujos projectos sejam detectados como cópias (seja de
outros alunos, seja de código disponibilizado na internet ou afim) serão chamados a reunir com o corpo docente. Caso o corpo docente considere que
ficou provado que houve cópia entre dois ou mais projectos, esses projectos
serão anulados e os alunos envolvidos reprovarão automaticamente.
3
Indicar o tempo de CPU, limitado a 1000s por instância, e as caracterı́sticas da máquina
onde foram obtidos os resultados.
3