Atividade Estudo Dirigido - Inteligência Artificial

Prévia do material em texto

Universidade Federal de Rondônia 
Inteligência Artificial – Estudo Dirigido 
Busca com informação e exploração – Seção 4.1 do livro texto 
 
Discente: Aden Hercules Pinto de Azevedo 
Docente: Carolina Watanabe 
 
1. O que é busca com informação? 
Utiliza conhecimento específico sobre o problema para encontrar soluções de forma 
mais eficiente do que a busca cega. 
 -Utiliza uma função de avaliação para cada nó. 
 – Expande o nó que tem a função de avaliação mais baixa. 
 – Dependendo da função de avaliação, a estratégia de busca muda. 
2. O que é uma função heurística? 
Ela estima o custo do caminho mais barato do estado atual até o estado final mais 
próximo, ou seja, é a simplicaficação de busca que pode ajudar no algoritmo, 
dependendo de cada problema. Resumidade, é uma função que retorna(transforma) o 
estado em um número. 
 
3. Descreva a abordagem de busca pela melhor escolha. 
Busca genérica onde o nó de menor custo “aparente” na fronteira do espaço de 
estados é expandido primeiro. Ela ordena os nós na borda em ordem decrescente de 
acordo com a função de avaliação, assim como usa uma função de avaliação para cada 
nó. 
 
4. Com relação à busca gulosa pela melhor escolha, avalie o desempenho do algoritmo 
considerando os aspectos de completeza, otimização, complexidade de tempo e de 
espaço. 
Completeza: não é completa, pois pode ficar presa em loops. 
Otimização: não possui. 
Complexidade de tempo: O(bm) no pior caso, mas uma boa função heurística pode 
levar a uma redução substancial. 
Complexidade de espaço: O(bm) – mantém todos os nós na memória 
 
5. Encontre o caminho de s até t usando busca gulosa pela melhor escolha do grafo a 
seguir. Diga qual foi o custo da solução encontrada e compare com o custo da solução 
ótima. 
 
 
1ª 
 
 H(s)=9 
 
 
 
 H(e) = 7 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 Destino 
 
 
 
 
 
 
 
 
 
 
6. O algoritmo de busca A* avalia nós combinando o custo para alcançar cada nó (g(n)) e 
o custo para ir do nó até o objetivo (h(n)): 
f(n) = g(n) + h(n). 
s 
e 
a 
f(a)=7 
a 
b 
b 
c 
c 
d 
d 
t 
f(b)=8 
f(c)=10 
f(d)=12 
f(t)=12 
2ª 
3ª 
4ª 
5ª 
Busca gulosa pela melhor escolha expande o nó que parece mais próximo ao 
objetivo de acordo com a função heurística. O custo do grafo cima, saindo de S->A-
>B->C-> e chegando em T, com base nos pesos dos caminhos foi de 12, e o valor de 
f(h)=12 
 
A idéia deste algoritmo foi combinar as estratégias de busca de custo uniforme, que 
considera g(n), e a de busca gulosa pela melhor escolha, que considera h(n). 
a. Diga se a busca A* é um algoritmo que satisfaz completeza e se encontra a solução 
ótima. Discuta as afirmações com base em análises feitas sobre g(n) e h(n). 
 
Completeza: Satisfaz a completeza (a não ser que exista uma quantidade infinita 
de nós com f ≤ f(G)). 
b. Discuta sobre a complexidade de tempo e de espaço da busca A*. 
 
A complexidade de tempo é exponencial no pior caso, e de espaço mantém todos os 
nós na memória. 
 
7. Encontre o caminho entre s e t mostrando os estágios em uma busca A* exibindo o 
valor de f(n) em cada estágio. 
 
 
 
Irei utilizar a mesma imagem para ficar melhor a explicação, e pincel... 
 
 
 
 
 
 
f(e)=9 
f(a)=7 
1º estágio 
Valor f de a é menor do 
que de e, por isso o 
precesso 1 via a 
permace caminhando 
enquando o via e fica 
em estado de espera 
até ele ser menor que o 
de a. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
f(e)=9 
f(a)=7 
2º estágio 
f(b)=8 
f(e)=9 
f(a)=7 
3º estágio 
f(b)=8 
f(c)=10 
Novamente o valor da 
busca por f(a) é menor 
que buscar por f(e), por 
isso o processo 
continua. Igualmente 
no estágio seguinte 3. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
f(e)=9 
f(a)=7 
4º estágio 
f(b)=8 
f(c)=10 f(f)=11 
f(e)=9 
f(a)=7 
5º estágio 
f(b)=8 
f(c)=10 f(f)=11 
f(d)=12 
Como f(e) é menor que 
f(c) o processo vai para 
a cidade f. 
Como f(d) é maior que 
f(d) o processo vai para 
a cidade d. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
f(e)=9 
f(a)=7 
6º estágio 
f(b)=8 
f(c)=10 f(f)=11 
f(d)=12 
f(g)=11 
f(e)=9 
f(a)=7 
7º estágio e último 
f(b)=8 
f(c)=10 f(f)=11 
f(d)=12 
f(g)=11 
f(t)=11 
Como f(f) é menor que 
f(d) o processo vai para 
a cidade g. 
E por fim, f(g) é menor 
que f(d) chegando ao 
destino primeiro. 
Conclui-se que saindo 
de S e indo por S(e) é 
mais em conta do que 
indo por S(a). 
 
8. Prove cada uma das afirmações a seguir: 
a. A busca em extensão é um caso especial de busca de custo uniforme. 
Quando todos os custos são iguais, temos g (n) proporcional à 
profundidade (n), de forma que a busca de custo uniforme reproduz a busca em 
extensão porque os nós se expandem em ordem de profundidade menor (custo 
menor) para profundidade maior. 
b. A busca em extensão, a busca em profundidade e a busca de custo uniforme 
são casos especiais de busca pela melhor escolha. 
Busca em extensão equivale a busca pela melhor escolha com 
f(n)=profundidade(n); busca em profundidade e busca pela melhor escolha 
com f(n)=-profundidade(n); busca de custo uniforme e busca pela melhor 
escolha com f(n) = g(n). 
c. A busca de custo uniforme é um caso especial de busca A*. 
Busca de custo uniforme equivale a A* com h(n) = 0. 
 
9. Discuta as vantagens e desvantagens dos métodos heurísticos e não informados de 
busca em grafos. 
No método heurístico possui informação (estimativa) de qual sucessor é mais 
promissor para atingir a meta, já na busca não informada (ou busca cega) não tem 
informação sobre qual sucessor é mais promissor para atingir a meta. 
 
10. Compare o algoritmo A* de aprofundamento iterativo (AIA* ou IDA*, em inglês) com o 
algoritmo de aprofundamento iterativo padrão. 
No algoritmo de aprofundamento interativo é uma combinaçao de busca em 
largura e profundidade, ele faz a busca em profundidade, que aumeta gradualmente o 
limite de profundade. É ótima e completa. Piora o tempo de busca, porém melhora o 
custo de memória, e tem bons resultados quando o espaço de estados é grande e de 
profundidade desconhecidas. Na A* também combina vantagens da busca em largura 
e profundidade. Ela busca onde o nó de menor custo “aparente” na fronteira do 
espaço de estados é expandido primeiro, assim como ela usa uma função de avaliação 
para cada nó, e expande o nós que tem a função de avaliação mais baixa. 
 
11. Descreva a busca recursiva pelo melhor (BRPM ou RBFS, em inglês). 
BRPM sofre de excessiva geração repetida de nós. É um algoritmo recursivo que 
tenta limitar a operação de busca pela melhor escolha. BPRM é um pouco mais eficiente 
do que AIA *, mas mantém todas as informações na memória. 
 
12. Quais são as vantagens e as desvantagens do LMSA* comparado ao A*? 
A* limitado pela memória e LMSA* é simplificado: pussui sensatez em utilizar a 
memória, descartando o pior nó de folha mais antiga. O LMS* prossegue exatamente 
como o A*, expandindo a melhor filha até completar a memória. O LMSA* sempre 
descarta o pior nó folha, ele só regera a subárvore quando todos os outros caminhos se 
mostram piores que o caminho que foi esquecido por ele, haja vista que ele copia esse 
valor do nó esquecido em seu pai. 
 
 
 
 
 
 
13. Assinale a alternativa correta. Considerando que h(n) é o custo estimado do nó n até o 
objetivo, em relação à busca informada, pode‐se afirmar que 
a. a busca gulosa minimiza h(n). 
b. a busca A* minimiza h(n). 
c. a busca de custo uniforme minimiza h(n). 
d. a busca gulosa minimiza h(n) somente se a heurística for admissível. 
e. a busca A* minimiza h(n) somente se a heurística for admissível. 
 
VERDE=VERDADEIRAS* 
VERMELHAS=FALSAS* 
14. Verifique se as afirmações a seguir são verdadeiras ou falsas. Caso seja falsa, explique. 
a. A estratégia de busca em largura encontra a solução ótima quando todos os 
operadores de mudança de estado têm o mesmo custo. 
 
 CORRETAb. A estratégia de busca em profundidade sempre expande um menor número 
de nós que a estratégia de busca em largura, quando aplicadas ao mesmo 
problema. 
 
FALSA – Errada, a busca em profundidade fica indo até encontrar um nó final, 
mas nem por isso ela “sempre” vai expandir uma quantidade de nó menor que 
a busca em largura quando aplicada ao mesmo exemplo, pois há casos que 
quantidade é igual. Então a questão está errada por isso, por causa desse 
“sempre”. 
 
c. A estratégia de busca heurística encontra sempre a solução de menor custo. 
 
FALSA - tudo que tem “sempre” no enunciado é suspeito. A busca heurística 
estima custo do caminho de menor custo de n até um nó objetivo. 
Primeiramente ela faz uma tentativa de expandir o nós mais promissores 
primeiro, ou seja, não SEMPRE encontrará a solução com menor custa. Por isso 
da alternativa está errada. 
 
d. A estratégia de busca heurística expande um número de nós em geral menor 
que o algoritmo de busca em largura, mas não garante encontrar a solução 
ótima. 
 
CORRETA 
 
e. O algoritmo de busca heurística que utiliza uma função heurística admissível 
encontra a solução ótima. 
 
CORRETA