ESTRATÉGIAS DE BUSCAS EM GRAFOS SEM CUSTO E COM CUSTO

Prévia do material em texto

INTELIGÊNCIA ARTIFICIAL
2a aula
 Lupa 
 
Exercício: CCT0296_EX_A2_201908665361_V1 27/10/2020
Aluno(a): THIAGO HENRIQUE DE JESUS PEREIRA 2020.2
Disciplina: CCT0296 - INTELIGÊNCIA ARTIFICIAL 201908665361
 
As estradas que unem as cidades abaixo possuem distâncias cujos valores estão próximos às arestas. Um turista na
cidade B deseja realizar uma viagem até a cidade L, baseando-se em uma tabela de preços de passagens disponibilizada
por ums empresa de ônibus. Levando em consideração um determinado método de busca, qual é a rota a ser seguida
pelo turista de modo a REDUZIR o custo com passagens?
Nó-h(n)
A-18
B-16
C-12
D-14
E-11
F-16
G-09
H-03
I-07
J-10
K-05
L-00
Utilizando-se o algoritmo A*, a rota entre B e L encontrada no problema acima é BFIL e o custo do caminho é 20
Utilizando-se a busca ordenada, a rota ente B e L encontrada no problema acima é BFIL e o custo do caminho é
19
 Utilizando-se a busca gulosa, a rota entre B e L encontrada no problema acima é BEHL e o custo do caminho é 17
Utilizando-se o algoritmo A*, a rota ente B e L encontrada no problema acima é BEHL e o custo do caminho é 19
Utilizando-se a busca gulosa, a rota entre B e L encontrada no problema acima é BEHL e o custo do caminho é 19
Respondido em 27/10/2020 16:31:33
 
 
 Questão1
 Questão2
https://simulado.estacio.br/alunos/inicio.asp
javascript:voltar();
javascript:diminui();
javascript:aumenta();
Com relação ao desempenho dos algoritmos de busca em profundidade e de busca em largura é possível afirmar que
Algoritmos de busca em largura são sempre mais eficientes que os algoritmos de busca em profundidade.
 Algoritmos de busca em profundidade e de busca em largura apresentam bom desempenho em arvores onde
todos os caminhos têm comprimentos aproximados.
Algoritmos de busca em largura apresentam mau desempenho quando se deparam com caminhos extremamente
longos ou infinitos no espaço de estados.
Algoritmos de busca em profundidade são menos eficientes em arvores com alto fator de ramificação.
O desempenho tanto dos algoritmos de busca em profundidade como dos de busca em largura não depende do
comprimento caminhos e nem do fator de ramificação.
Respondido em 27/10/2020 16:33:00
Gabarito
Comentado
 
 
Analise as seguintes afirmativas. 
I. 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. 
II. 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. 
III. A estratégia de busca heurística encontra sempre a solução de menor custo. 
IV. 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. 
V. O algoritmo de busca heurística que utiliza uma função heurística admissível encontra a solução ótima. 
A esse respeito, pode-se concluir que: Escolha a alternativa correta
Apenas as afirmativas I e V são corretas.
Apenas as afirmativas I e IV são corretas.
 Apenas as afirmativas I, IV e V são corretas.
Apenas as afirmativas II e V são corretas.
Apenas a afirmativa V é correta.
Respondido em 27/10/2020 16:34:02
Gabarito
Comentado
 
 
Considerando que h(N) é o custo estimado do nó N até o objetivo, em relação à busca informada, pode-se afirmar que:
A busca A∗ minimiza h(N) somente se a heurística for admissível.
A busca A∗ minimiza h(N).
A busca gulosa minimiza h(N) somente se a heurística for admissível.
A busca de custo uniforme minimiza h(N).
 A busca gulosa minimiza h(N).
Respondido em 27/10/2020 16:35:10
Gabarito
Comentado
 
 
Em um determinado problema de busca envolvendo custos, há dados de custo real e de heurística. Deseja-se utilizar
ambos os dados com o objetivo de encontrar o melhor caminho entre o estado inicial e o estado final informados. Assinale
abaixo qual método de busca utiliza estes dois dados em conjunto:
ordenada
em profundidade
em Largura
gulosa
 A*
Respondido em 27/10/2020 16:49:23
 Questão3
 Questão4
 Questão5
Gabarito
Comentado
 
 
No grafo ilustrado abaixo, cada nó representa uma cidade dis�nta, e cada ramo, uma rodovia
que interliga as cidades representadas pelos nós que ele une, cujo peso indica a distância, em
km, entre essas cidades pela rodovia.
Suponha que se deseje encontrar a melhor rota entre as cidades A e M, indicadas nesse grafo.
Considere, ainda, os valores indicados na tabela abaixo como distância em linha reta, em km,
de cada cidade para a cidade M.
nó A B C D E F G H I J K L M
h(nó) 44 20 33 25 30 22 14 10 11 5 40 20 0
 
A par�r dessas informações, escolha a alterna�va CORRETA:
Utilizando-se o algoritmo A*, a rota ente A e M encontrada no problema acima é ABHGIJM e o custo do caminho
é 85
Utilizando-se a busca gulosa, a rota ente A e M encontrada no problema acima é ACDFLM e o custo do caminho é
56
Para utilizar algoritmos de busca heurística, deve-se definir uma heurística que superestime o custo da solução
Utilizando-se a busca gulosa, a rota encontrada no problema acima é ACDFLM
 Utilizando-se o algoritmo A*, a rota ente A e M encontrada no problema acima é ACDFLM e o custo do caminho é
56
Respondido em 27/10/2020 16:47:13
 
 
Avalie as afirmações abaixo:
(1) Em sistemas de produção cada regra representa uma ação que pode ser executada. A determinação da regra aplicada
se dá pela avaliação do estado atual do problema. Novos estados são colocados a disposição até que seja gerada uma
solução final.
 PORTANTO
(2) a resolução de um problema se dá pela aplicação sucessiva de regras que transformam estados em outros até que um
estado final (solução) seja encontrado.
 As afirmações (1) e (2) são verdadeiras e (2) justifica (1).
As afirmações (1) e (2) são falsas e (2) não justifica (1).
As afirmações (1) e (2) são falsas.
A afirmações (1) é verdadeira e a afirmação (2) é falsa.
As afirmações (1) e (2) são verdadeiras e (2) não justifica (1).
Respondido em 27/10/2020 16:46:43
 
 
Quando se tenta atravessar um labirinto, as pessoas vagam aleatoriamente, esperando encontrar o caminho da saída. Esta abordagem poderá ser bem-
 Questão6
 Questão7
 Questão8
sucedido, mas não é o mais racional e muitas vezes leva a que chamamos de "andar em círculos". Um método alterna�vo para a atravessar um labirinto
é tatear com a mão o lado direito do seu muro (ou parede), ou seja, seguir percorrendo o labirinto sempre em paralelo ao seu muro mantendo-se a
mão direita em contato com sua superficie.
A descrição acima é uma técnica ou método de busca não informada muito conhecido em Inteligência Ar�ficial. O nome dessa busca não informada é:
Busca A* (A estrela)
 Busca em Profundidade
Busca em Largura
Busca Hill Climbing
Busca Interativa
Respondido em 27/10/2020 16:47:33
Gabarito
Comentado
 
 
 
javascript:abre_colabore('38403','211456055','4256924553');