1º TP :

Neste 1º Trabalho Prático, a ser realizado em dupla, vocês deverão implementar em Prolog os seguintes algoritmos de procura em grafos para o problema do quebra-cabeça de 15 números para duas heurísticas diferentes e comparar sua eficiência em tempo e espaço:

1- Procura em largura e em profundidade 1º.

2- Subida do morro (gradiente), melhor 1º e procura por feixe (beam search).

3- A* e IDA*.

As implementações deverão comparar a proporção do grafo procurada, para instâncias aleatórias do quebra-cabeça de 15 números, e a quantidade de nós expandidos e visitados (tamanho das listas de nós abertos e fechados), assim como o tempo e a memória efetivamente gastos na execução dos algoritmos para cada instância do problema (Utilizem o meta-predicado statistics no GNU Prolog ou equivalente em outras implementações).

Vocês deverão apresentar seus resultados em uma palestra de 10 minutos em que ambos membros da dupla farão intervenções complementares. Durante a palestra, ou ao fim dela, vocês deverão executar cada um dos algoritmos para uma instância do quebra-cabeça gerada aleatoriamente imediatamente antes da execução (uma instância para cada algoritmo ou uma única instância para todos algoritmos).

A avaliação será feita com base nas implementações dos algoritmos e quantidade de dados de teste feitos (12 pontos), assim como na apresentação (8 pontos).