INF1771 - INTELIGÊNCIA ARTIFICIAL  
LISTA DE EXERCÍCIOS 1  
Aluno:  
1
. Defina o problema (espaço de estados, estado inicial, estado final, ações possíveis, custo)  
para cada um dos casos listados a seguir:  
(
a) O macaco e as bananas: Um macaco de meio metro de altura está em uma jaula onde  
algumas bananas estão suspensas a três metros e meio do chão. Ele quer pegar as  
bananas. A jaula contém dois caixotes de um metro e meio que podem ser movidos e  
sobrepostos.  
(
b) O homem, o lobo, o carneiro e o cesto de alface: Uma pessoa, um lobo, um carneiro e  
um cesto de alface estão à beira de um rio. Dispondo de um barco no qual pode  
carregar apenas um dos outros três, a pessoa deve transportar tudo para a outra  
margem. Em nenhum momento devem ser deixados juntos e sozinhos o lobo e o  
carneiro ou o carneiro e o cesto de alface.  
(
c) Colorir mapa: Você tem que colorir um mapa plano usando apenas 4 cores, de tal  
modo que não haja duas regiões adjacentes com a mesma cor.  
2
. Em um labirinto, mostrado na figura a seguir, um robô é colocado na célula inicial indicada  
por “E” e deve encontrar um caminho até a saída, denotada pela letra “S”. O robô não  
pode se mover na diagonal, somente acima, abaixo, direita e esquerda. Ele também não  
pode atravessar paredes (as linhas mais grossas da grade) ou as bordas do labirinto, de  
modo que ele é forçado a contornar obstáculos. Felizmente, o robô possui um mapa do  
ambiente. A solução é o caminho mais curto até a saída e todos os movimentos do robô  
possuem os mesmos custos.  
1
E
2
3
4
S
1
2
3
4
(a) Descreva o problema em termos de um problema de busca definindo o espaço de  
estados, o estado inicial, o estado final, os operadores de transição entre os estados  
(ações) e o custo.  
(b) Construa um grafo do espaço de estados rotulando os arcos com os operadores de  
transição adequados.  
3
. Quatro pessoas precisam atravessar uma ponte que suporta no máximo duas pessoas ao  
mesmo tempo. É noite e eles não podem ver o caminho. Por sorte o grupo possui uma  
tocha que pode ser usada para iluminar o caminho enquanto eles atravessam a ponte. O  
tempo necessário para cada pessoa atravessar a ponte é respectivamente: 1, 2, 5 e 10  
minutos. É possível que eles atravessem a ponte em 17 minutos?  
(a) Descreva o problema em termos de um problema de busca definindo o espaço de  
estados, o estado inicial, estado final, os operadores de transição entre os estados  
(ações) e o custo.  
(
(
b) Quantas vezes eles precisam atravessar a ponte?  
c) Construa um grafo do espaço de estados rotulando os arcos com os operadores de  
transição adequados.  
4
. Considerando o seguinte labirinto e dispondo os estados sucessores na seguinte ordem:  
leste, oeste, norte, sul.  
(a) Em qual ordem uma busca em profundidade visita as salas do labirinto? A busca em  
profundidade é ótima?  
(b) Em qual ordem uma busca em largura visita as salas do labirinto? A busca em largura é  
ótima?  
5
. Considerando o seguinte mapa:  
Responda as questões abaixo considerando “Start” como o estado inicial e “Goal” o estado  
final buscado.  
(
a) Monte as árvores de busca que seriam geradas pelos algoritmos de busca cega vistos  
em aula (busca em largura, busca de custo uniforme, busca em profundidade, busca  
com aprofundamento iterativo, busca bidirecional).  
(b) Qual dos algoritmos apresentou melhor resultado? Considerando o custo do caminho  
e o número de nós avaliados até que a solução fosse encontrada.