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 (M) de meio metro de altura está em uma jaula
onde algumas bananas (B) estão suspensas a três metros e meio do chão. Ele quer
pegar as bananas. A jaula contém dois caixotes (C1 e C2) de um metro e meio que
podem ser movidos e sobrepostos. A posição inicial dos elementos e o formato da
jaula (visão de cima) são ilustrados na figura abaixo:
M
C1
B
C2
(
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) Jogo da Velha: O tabuleiro do jogo é definido por uma matriz de 3 linhas por 3 colunas
onde dois jogadores escolhem uma marcação (X ou O). Os jogadores jogam
alternadamente colocando uma marcação por vez em numa lacuna que esteja vazia. O
objetivo é conseguir colocar 3 símbolos iguais em linha horizontal, vertical ou diagonal.
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.
(
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.
1
E
2
3
4
5
S
1
2
3
4
(
b) Construa um grafo do espaço de
estados rotulando os arcos com os
operadores de transição adequados.
3
. Considerando o seguinte labirinto e dispondo os estados sucessores na seguinte ordem:
norte, leste, oeste, sul.
A
F
B
G
L
C
H
M
E
D
I
E
Goal
J
O
T
Z
K
P
N
S
Y
Q
V
U
Start
X
(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?
4
. Considerando o seguinte mapa:
C
D
H
K
1
0
1
2
8
6
1
8
1
0
Start
A
2
5
G
Goal
F
2
0
10
20
1
2
8
B
I
J
1
5
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.