Lista 2 Inteligência Artificial

Prévia do material em texto

Inteligência Artificial 
Profa. Heloisa - Lista de Exercícios - Resolução de Problemas por Busca 
==================================================================== 
1) Considere o seguinte grafo, representando o espaço de estados para certo problema: 
 
 
Sendo o nó A inicial, e o nó N o objetivo, percorra este grafo usando os algoritmos de busca 
em largura e de busca em profundidade e apresente o conteúdo das listas OPEN e 
CLOSED a cada passo do algoritmo. Indicar as ações tomadas quando um nó gerado já 
estiver em uma das duas listas. 
 
2) O Problema dos baldes de água pode ser definido como: Existem dois baldes de água, o 
primeiro com capacidade para 5 litros e o segundo com capacidade para 3 litros. É possível 
encher qualquer um dos baldes totalmente de uma torneira ou esvaziá-los totalmente 
independente da quantidade de água que eles tenham, e despejar água de um para o outro, até 
que o que recebe a água esteja totalmente cheio ou até que aquele do qual se despeja a água 
esteja totalmente vazio. Supondo que os baldes estão inicialmente cheios, o objetivo é deixar 
4 litros de água no balde maior e qualquer quantidade de água no balde menor. Construa a 
formulação do problema definindo a representação dos estados, o estado inicial, final e os 
operadores. Aplique o método de busca em profundidade e mostre o conteúdo das listas 
OPEN e CLOSED passo a passo. Indique as ações tomadas quando um nó gerado já estiver 
em uma das duas listas. Mostre a sequência de movimentos que determina a solução. 
 
3) Considere o problema dos baldes de água e assuma que os operadores são aplicados na 
ordem: 1) esvaziar balde maior; 2) esvaziar balde menor; 3) encher balde maior; 4) encher 
balde menor; 5) despejar do balde maior para o menor; 6) despejar do balde menor para o 
maior. Aplique o método de busca em profundidade e mostre o conteúdo das listas OPEN e 
CLOSED passo a passo. Indique as ações tomadas quando um nó gerado já estiver em uma 
das duas listas. Mostre a sequência de movimentos que determina a solução. 
 
4) Considere outra versão para o problema dos baldes de água em que a capacidade dos baldes 
maior e menor é 7 e 5 litros, respectivamente. 
a) Construa a árvore de busca para o método de Busca em Profundidade. 
b) Mostre a sequência de movimentos que determina a solução. 
 
5) O problema dos jarros é definido como: Existem 3 jarros com capacidade para 12, 8 e 3 litros, 
respectivamente, e uma torneira. É possível encher os jarros de uma torneira (um de cada 
vez), esvaziá-los totalmente (um de cada vez) ou despejar água de um para o outro até encher 
o vaso de destino ou até esvaziar totalmente o vaso de origem. Supondo que os jarros estão 
A 
C B D 
E F G H I 
J K L M N O P Q 
inicialmente cheios, o objetivo é deixar um litro de água em qualquer um dos jarros. Defina 
uma formulação para esse problema e aplique o método de busca em largura até o nível 2. 
 
6) O problema do mundo do aspirador de pó simplificado é descrito como um cenário que tem 
dois quadrados, sendo que cada um deles pode conter sujeira ou não. Existe um aspirador de 
pó que pode se mover para a esquerda ou para a direita e aspirar sujeira. Partindo de uma 
situação inicial onde o aspirador de pó está no quadrado da esquerda e os dois quadrados tem 
sujeira, encontre a seqüência de movimentos para limpar todos os quadrados. O aspirador de 
pó pode ficar em qualquer um dos quadrados. Considerando a seguinte seqüência de 
movimentos: 1) andar para esquerda; 2)andar para direita; 3)sugar, construa a árvore de 
execução para o método de Busca em Largura e para o método de Busca em Profundidade. 
 
7) O problema do mundo do aspirador de pó pode ser também formulado como: Um cenário é 
representado por uma grade de 2X2, sendo que cada quadrado pode ter ou não sujeira. Um 
aspirador de pó pode se mover nesse cenário, com movimentos que tem os seguintes custos: 
aspirar a sujeira - custo 1; andar para a esquerda ou para a direita - custo 2; andar para cima 
ou para baixo - custo 3. Uma função heurística para esse problema pode ser definida como 
h(n)=número de quadrados sujos em n. Os operadores devem ser aplicados na ordem: 
1)aspirar; 2)mover à direita; 3)mover para baixo; 4) mover à esquerda; 5) mover para cima. 
Encontre a sequencia de movimentos para chegar a um estado onde todos os quadrados estão 
limpos, supondo que no início, e o aspirador de pó está no quadrado superior esquerdo e que 
os dois quadrados da direita estão sujos. Construa as árvores de busca para o Algoritmo 
Greedy e para o Algoritmo A, mostrando para cada nó, o valor da função de avaliação, função 
heurística e de custo (quando houver). Enumerar os nós de acordo com a sequência em que 
foram expandidos. Indique as ações tomadas quando um nó gerado já estiver em uma das 
duas listas. Mostre a sequência de movimentos que determina a solução. 
 
8) A figura dada a seguir representa o espaço de estados para um dado problema, tal que os 
números dentro dos retângulos ao lado dos nós indicam o valor da função heurística (h(x)) 
aplicada ao nó e os números ao lado dos arcos representam o custo de aplicação do operador 
correspondente a esse arco. O nó Z, com bordas escuras e valor heurístico zero, é o nó 
objetivo. Construa a árvore que resulta da aplicação dos algoritmos de busca heurística: 
 Algoritmo A, onde a função de avaliação deve ser f(x) = g(x) + h(x) 
 greedy, onde a função de avaliação deve ser f(x) = h(x) 
Para cada um dos algoritmos, indique o caminho de solução. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1 2 1 2 2 
2 2 2 2 2 2 2 2 2 
2 2 2 1 
2 
2 
5 
2 
4 
2 
3 
A 
C B D 
4 5 
E 
7 
4 4 
4 5 
G F H 
6 6 
I 
6 
4 
J K L M 
10 4 9 3 
N O P Q 
5 
5 
6 5 
R S 
T U V X 
5 
5 3 2 0 5 3 4 
Z A1 B1 C1 F1 E1 D1 G1 
4 3 
5 
9) Construa a árvore de busca resultante da aplicação do Algoritmo A ao problema de 
determinação de rotas, para ir da cidade L até a cidade B, usando como função heurística a 
distância em linha reta entre cada cidade e a cidade B. O custo de cada operação (ir de uma 
cidade a outra) é a distância em quilômetros da estrada que liga as duas cidades. Consulte o 
mapa das cidades e estradas e a tabela de distâncias do material de aula. Mostre os valores de 
g, h e f para cada nó e indique o caminho da solução. 
 
10) Construa a árvore de busca resultante da aplicação Algoritmo de Custo Uniforme ao 
problema de determinação de rotas, para ir da cidade S até a cidade B. O custo de cada 
operação (ir de uma cidade a outra) é a distância em quilômetros da estrada que liga as duas 
cidades. Consulte o mapa das cidades e estradas e a tabela de distâncias do material de aula. 
Mostre os valores de g, h e f para cada nó e indique o caminho da solução. 
 
11) A figura dada a seguir representa o espaço de estados para um dado problema, tal que os 
números ao lado dos arcos representam o custo de aplicação do operador correspondente a 
esse arco. O nó com bordas escuras é o nó objetivo. Construa a árvore que resulta da 
aplicação do Algoritmo de Custo Uniforme a este problema. Mostre o conteúdo das listas 
OPEN e CLOSED a cada passo e indique o caminho da solução. 
 
 
 
 
 
 
 
 
 
 
 
 
 
12) O algoritmo de caminho heurístico é uma busca pela melhor escolha na qual a função 
objetivo é f(n) = (2-w)g(n) + wh(n). Para que valores de w esse algoritmo oferece a garantia 
de ser ótimo? Que espécie de busca ele executa quando w=0? E quando w=1? E quando w=2? 
 
13) Aplique o algoritmo de Subida da Encosta (Hil-Climbing) no grafo do Exercício 8, 
considerando os valores heurísticos (ignorando oscustos das operações). Explique porque o 
algoritmo não permite atingir a solução ótima. Construa o grafo de busca. 
 
14) Aplique o algoritmo de Subida da Encosta (Hill-Climbing) no problema do Exercício 9. 
 
15) Aplique o algoritmo de Têmpera Simulada no problema do Exercício 9 utilizando valor 
inicial de T=1000 e escolha os valores aleatórios livremente. 
 
 
 
 
 
 
 
 
5 2 3 
1 
3 4 
2 2 
2 3 2 
9 
5 
12 
A 
B C D 
E F G H I 
J K M N O P Q R S 
2 
7 
4 
3 
5 
5 
4 
 
16) O problema das 4 rainhas consiste em posicionar 4 rainhas em um tabuleiro 4X4 de tal forma 
que não possam atacar umas as outras. Os tabuleiros abaixo representam duas situações 
distintas para esse problema. Suponha que essas duas configurações estão representadas como 
dois indivíduos de uma população de um algoritmo genético que está sendo usado para 
resolver o problema. A função de avaliação que o algoritmo utiliza é o número de pares de 
rainhas que não atacam umas as outras. Calcule o valor da função heurística para cada uma 
dessas situações. Aplique o cruzamento de um ponto nesses dois indivíduos a calcule 
novamente o valor heurístico dos indivíduos resultantes.