Lista-de-Exercicio-busca-gabarito

Prévia do material em texto

Lista de Exercício 1 - Gabarito 
1 - Qual é a diferença entre uma busca informada e uma busca não informada? 
A diferença é que a busca não informada não sabe qual o melhor nó da fronteira a ser 
expendido, apenas distingue os nós objetivos dos não objetivos. Já a busca informada 
estima qual o melhor nó da fronteira a ser expandido com base em funções heurísticas. 
2 - Como se avalia, geralmente, as estratégias de busca (critérios)? 
Completeza: O algoritmo oferece a garantia de encontrar uma solução quando ela 
existir? 
Otimização: A estratégia encontra a solução ótima (tem o menor custo de caminho entre 
todas as soluções)? 
Complexidade de tempo: Quanto tempo ele leva para encontrar uma solução? 
Complexidade de espaço: Quanto de memória é necessário para executar a busca? 
3 - Quais são os principais métodos de busca cega? Porque são chamados “métodos 
de busca cega”? 
Os principais métodos de busca cega são Busca em largura e Busca em profundidade. 
São chamados de busca cega, pois não tem informação sobre qual sucessor é mais 
promissor para atingir a meta. 
4 - Explique rapidamente cada uma das estratégias de busca abaixo e o 
desempenho de cada uma delas. 
a) Busca em profundidade: Expande os nós da vizinhança até o nó mais profundo. 
b) Busca em largura (ou em amplitude, ou em extensão): O nó raiz é expandido, em 
seguida todos os nós sucessores são expandidos, então todos próximos nós sucessores 
são expandidos, e assim em diante. 
c) Busca heurística pelo melhor primeiro (gulosa): Expande os nós que se encontram 
mais próximos do objetivo (uma linha reta conectando os dois pontos no caso de 
distancias), desta maneira é provável que a busca encontre uma solução rapidamente. 
d) Busca A*: expande o nó de menor valor de f na fronteira do espaço de estados 
(distância (custo) do nó inicial ao nó n mais a distância (custo) estimada de n ao nó 
final). Nenhum outro algoritmo ótimo garante expandir menos nós. Guarda todos os nós 
expandidos na memória. 
5 - Dê um exemplo de problema em que a “busca em largura” funcionaria melhor 
do que a “busca em profundidade”. Dê um exemplo de problema em que a “busca 
em profundidade” funcionaria melhor do que a “busca em largura”. Justifique os 
exemplos. 
A principal vantagem do algoritmo de busca em largura é que este encontra o MENOR 
caminho do nodo inicial até o nodo final mais próximo. Exemplo: busca de uma cidade 
dentro do mesmo Estado. O algoritmo de busca em profundidade não encontra 
necessariamente a solução mais próxima, mas pode ser MAIS EFICIENTE se o 
problema possui um grande número de soluções ou se a maioria dos caminhos pode 
levar a uma solução. Exemplo: busca de uma cidade em países diferentes. 
6 – Em uma estratégia de busca com informação, qual o objetivo do uso de 
heurísticas? 
Uma forma de uso da informação heurística sobre um problema consiste em computar 
estimativas numéricas para os nós no espaço de estados; Uma estimativa indica o 
quanto um nó é promissor com relação ao alcance de um nó-objetivo; A idéia é 
continuar a busca sempre a partir do nó mais promissor no conjunto de candidatos; 
7 – Quais são as condições para que a busca A* seja ótima e completa? 
Tem o objetivo de minimizar o custo total estimado da solução. Entre as várias soluções 
possíveis encontra sempre primeiro a melhor. 
 
8 - 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 abaixo. 
Em sua resposta forneça o seguinte: 
1. A árvore de busca que é produzida, mostrando a função de custo em cada nó. 
2. Defina a ordem em que os nós serão expandidos. 
3. Defina a rota que será tomada e o custo total. 
 
Distância em linha reta até R