Lista 1 Busca

Prévia do material em texto

Inteligência Artificial 
Willian P. Amorim 
Lista de Exercícios 1 
 
 
1. Qual é a diferença de uma busca informada para uma busca não informada? 
2. Em que sentido a busca gulosa pela melhor escolha é parecida com a busca 
em profundidade? 
3. Porque a busca gulosa pela melhor escolha não é ótima? 
4. Defina o problema (espaço de estados, estado inicial, estado final, ações pos-
síveis, custo) para o caso listado a seguir: 
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. 
 
5. Fale sobre a busca bidirecional. Ela pode ser aplicada a qualquer problema? 
6. O que é uma heurística? 
 
Considere a árvore abaixo, na qual os nós objetivos são os nós l e m, marca-
dos em negrito. A função h(n) tem seus valores ao lado de cada nó, em azul, 
e a função g(n) tem seus valores dados com custo igual a um para cada nível, 
em vermelho. Em caso de empate na função de avaliação, expandir o nó mais 
antigo primeiro. 
 
 
7. Considerando a árvore apresentada na figura, responda: 
a. Qual o caminho que o algoritmo de busca A* percorre? 
b. Qual o caminho que a busca gulosa percorre? 
c. Qual o caminho que a busca em largura percorre? 
Resposta: 
d. Qual o caminho que a busca em profundidade percorre? 
 
8. Verdadeiro ou falso? Justifique a resposta. A busca em profundidade é mais 
adequada quando todos os caminhos na árvore de busca que levam até um 
nó objetivo tem comprimento semelhantes. 
9. Verdadeiro ou falso? Justifique a resposta. A busca em largura é mais ade-
quada quando o nó objetivo está mais próximo a raiz e a árvore possui cami-
nhos muito longos. 
10. Verdadeiro ou falso? Justifique a resposta. Considere um problema de 
busca em que o fator de ramificação é 2, a profundidade máxima da árvore 
é 5 e a profundidade da solução mais rasa é 2. Neste caso é mais indicado 
usar a busca em largura. 
11. Verdadeiro ou falso? Justifique a resposta. Considere um problema de 
busca em que o fator de ramificação é 5, a profundidade máxima da árvore 
é 5 e a profundidade da solução mais rasa é 2. Neste caso é mais indicado 
usar a busca em profundidade. 
12. Verdadeiro ou falso? Justifique a resposta. Considere um problema de 
busca em que o fator de ramificação é 2, a profundidade máxima da árvore 
é 5 e a profundidade da solução mais rasa é 5. Neste caso é mais indicado 
usar a busca em profundidade. 
a 
b d 
e f 
c 
l 
9 
8 7 9 
6 5 
0 
6 
i
o 
n 
8 
g 
7 
h 
j 
7
0 k m 
0 
8 
4 
0 
 
 
1 
 
 
2 
 
 
3 
 
 
13. A partir da figura abaixo apresente os seguintes pontos: Máximo global, 
Máximo local, Pico e Platô. 
 
 
14. Explique a técnica hill-climbing. Quais suas limitações? Como podemos 
resolver estas limitações? 
15. Considerando uma árvore com fator de ramificação 3, profundidade 
máxima 2 e profundidade da solução mais rasa 2, apresente a comple-
xidade tanto da busca em largura quanto busca em profundidade e apresente 
a melhor solução. 
16. Considere o seguinte mapa (fora de escala) 
 
Usando o algoritmo A* determine uma rota de A até R, usando as seguintes 
funções de custo g(n) = a distância entre cada cidade (mostrada no mapa) e 
h(n) = a distância em linha reta entre duas cidades. Estas distâncias são 
dadas na tabela a baixo: 
 
Em sua resposta forneça o seguinte: 
a) A árvore de busca que é produzida, mostrando a função de custo em cada 
nó. 
b) Defina a ordem em que os nós serão expandidos. 
c) Defina a rota que será tomada e o custo total. 
 
 
Distância em linha reta até R 
 
 
17. Considere o espaço de busca abaixo, onde S é o estado inicial e G é o 
único estado que satisfaz o teste de objetivo. Os rótulos nas arestas indicam 
o custo de percorrê-las e a tabela ao lado mostra o valor de três heurísticas 
h0, h1 e h2 para cada estado. 
 
 
 
 
 
Quais são os nós expandidos pela busca A* usando cada uma das heurísticas 
(h0, h1 e h2)? Qual é a solução (caminho) encontrado por cada uma delas?