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

Prévia do material em texto

As definições a seguir representam, respectivamente, os métodos de busca:
1) Inicialmente, o método expande o nó raíz, gerando todos os seus filhos. Se um desses filhos for a solução do problema,
o método é interrompido. Caso contrário,um deles é escolhido, segundo algum critério, para ser expandido e seus filhos são
novamente testados. O processo continua até qua soluçõa seja encontrada ou até que um nó selecionado não possa mais
ser expandido. A solução é alcançada (se ela existir), mas não se pode garantir que seja a melhor.
2) A partir do nó raíz os operadores são aplicados, sucessivamente, de acordo com a estratégia definida, até que a solução
seja encontrada ou até o momento em o método não puder mais continuar. Não garante que a solução do problema seja
encontrada.
3) Expande os nós na ordem em que são gerados fazendo com que os nós de um determinado nível somente sejam
gerados e avaliados se os nós do nível anterior já tiverem sido abordados. Avalia todos os ramos da árvore, portanto, além
de garantir a determinação da solução do problema (se ela existir), garante que a solução é ótima.
 
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
INTELIGÊNCIA ARTIFICIAL 
Lupa Calc.
 
 
CCT0296_A2_201908665361_V2 
 
Aluno: THIAGO HENRIQUE DE JESUS PEREIRA Matr.: 201908665361
Disc.: INTEL.ARTIFICIAL 2020.2 (G) / EX
 
Prezado (a) Aluno(a),
 
Você fará agora seu TESTE DE CONHECIMENTO! Lembre-se que este exercício é opcional, mas não valerá ponto para sua
avaliação. O mesmo será composto de questões de múltipla escolha.
Após responde cada questão, você terá acesso ao gabarito comentado e/ou à explicação da mesma. Aproveite para se
familiarizar com este modelo de questões que será usado na sua AV e AVS.
 
1.
(1) Busca revogável em profundidade - (2) Busca irrevogável - (3) Busca revogável em largura.
(1) Busca revogável em largura - (2) Busca revogável em profundidade - (3) Busca irrevogável
(1) Busca revogável em profundidade - (2) Busca revogável em profundidade - (3) Busca irrevogável
(1) Busca revogável em profundidade - (2) Busca revogável em largura - (3) Busca irrevogável
(1) Busca revogável em largura - (2) Busca revogável em largura - (3) Busca irrevogável
 
Gabarito
Comentado
 
 
 
2.
javascript:voltar();
javascript:voltar();
javascript:duvidas('115292','7158','1','3626968','1');
javascript:duvidas('135723','7158','2','3626968','2');
javascript:diminui();
javascript:aumenta();
javascript:calculadora_on();
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:
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:
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
Utilizando-se a busca gulosa, a rota encontrada no problema acima é ACDFLM
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 ente A e M encontrada no problema acima é ACDFLM e o custo do caminho é 56
Utilizando-se o algoritmo A*, a rota ente A e M encontrada no problema acima é ABHGIJM e o custo do caminho é 85
Utilizando-se o algoritmo A*, a rota ente A e M encontrada no problema acima é ACDFLM e o custo do caminho é 56
 
 
 
 
3.
em Largura
gulosa
em profundidade
A*
ordenada
 
Gabarito
Comentado
 
 
 
4.
Apenas as afirmativas I e V são corretas.
Apenas as afirmativas II e V são corretas.
Apenas a afirmativa V é correta.
Apenas as afirmativas I, IV e V são corretas.
Apenas as afirmativas I e IV são corretas.
 
Gabarito
Comentado
javascript:duvidas('228966','7158','3','3626968','3');
javascript:duvidas('269345','7158','4','3626968','4');
Considerando que h(N) é o custo estimado do nó N até o objetivo, em relação à busca informada, pode-se afirmar que:
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
 As definições a seguir representam, respectivamente, os métodos de busca:
(1) A estratégia de busca guarda a soma do custo de cada caminho e procura, a cada passo, o caminho que 
implicará na menor soma.
(2) A estratégia de busca utiliza uma estimativa do custo do caminho até o nó destino, calculando o caminho de menor
custo ou que implicará na menor soma.
 
 
 
5.
A busca gulosa minimiza h(N).
A busca gulosa minimiza h(N) somente se a heurística for admissível.
A busca A∗ minimiza h(N).
A busca A∗ minimiza h(N) somente se a heurística for admissível.
A busca de custo uniforme minimiza h(N).
 
Gabarito
Comentado
 
 
 
6.
Utilizando-se a busca gulosa, a rota entre B e L encontrada no problema acima é BEHL e o custo do caminho é 19
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 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 ordenada, a rota ente B e L encontrada no problema acima é BFIL e o custo do caminho é 19
 
 
 
 
7.
javascript:duvidas('235207','7158','5','3626968','5');
javascript:duvidas('187429','7158','6','3626968','6');
javascript:duvidas('115343','7158','7','3626968','7');
(3) A estratégia de busca é visitar o nó com menor custo vinculado ao percurso.
 
Os métodos de busca informada ao fazerem uso de heurística possuem como vantagem. Assinale a altenativa CORRETA.
(1) Busca Ordenada - (2) Busca Simples - (3) Busca pelo vizinho mais próximo
(1) Busca Heurística - (2) Busca pelo vizinho mais próximo - (3) Busca Ordenada
(1) Busca Ordenada - (2) Busca Heurística - (3) Busca pelo vizinho mais próximo
(1) Busca Heurística - (2) Busca Ordenada - (3) Busca pelo vizinho mais próximo
(1) Busca Simples - (2) Busca Completa - (3) Busca pelo vizinho mais próximo
 
 
 
 
8.
poder examinar o espaço de busca de forma mais eficiente.
ter a complexidade do seu algoritmo reduzida.
poder fazer pesquisas em redes semânticas.
permitir com que o seu algoritmo seja programado mais facilmente.
poder fazer pesquisas em árvores semânticas.
 
Gabarito
Comentado
 
 
 
 
 
 
 Não Respondida Não Gravada Gravada
 
 
Exercício inciado em 28/10/2020 09:58:26. 
 
 
 
 
javascript:duvidas('765894','7158','8','3626968','8');javascript:abre_colabore('39100','211536544','4259157310');