algoritmos de Busca-Inteligência Artificial

UNIVERSIDADE FEDERAL DO PIAUÍ
CENTRO DE CIÊNCIAS DA NATUREZA
DEPARTAMENTO DE COMPUTAÇÃO
DISCIPLINA: INTELIGÊNCIA ARTIFICIAL
PERÍODO: 2014.1

RELATÓRIO

João Paulo Albuquerque
Paulo Sérgio Queiroz de O. Filho

TERESINA, MAIO DE 2014.

1. Introdução
Esse presente relatório tem por objetivo mostrar o resultado da implementação dos algoritmos de busca (busca em largura, profundidade, gulosa e A*) para solucionar o problema dos missionários e canibais e discutir os resultados obtidos. Foi utilizada a linguagem Java para a implementação dos mesmos, por já ter muitas funções de operações sobre listas, pilhas e filas prontas, e a IDE Eclipse.

2. Desenvolvimento
A abstração utilizada para resolver o problema foi a seguinte: (m, c, b), onde m é o número de missionários na margem esquerda, c é o número de canibais na margem esquerda e b representa o lado onde o barco está, que pode ser o caractere
‘e’ (esquerda) e o caractere ‘d’ (direita). Foi considerado inicialmente que o barco e todos os missionários estariam do lado esquerdo. Sendo assim o estado inicial seria representado por (3,3, e). O estado final (objetivo) é o estado (0, 0, d), com nenhum missionário e canibal na margem esquerda e o barco do lado direito do rio.
Para resolver o problema dos missionários e canibais a primeira coisa que foi pensada seria em quais os possíveis estados poderiam ser gerados a partir do estado atual. Então foi observado que seriam os seguintes:






Levar um missionário e um canibal para o outro lado;
Levar dois missionários para o outro lado;
Levar dois canibais para o outro lado;
Levar somente um missionário;
Levar somente um canibal.

Estados repetidos e estados inválidos (com maior número de canibais que missionários do mesmo lado) não são gerados, pois foi utilizada uma lista de estados já visitados para guardar os estados já visitados e antes de gerar um estado, é realizado um teste para verificar se o estado que será gerado é