Prévia do material em texto

112. Algoritmos de Busca 
Algoritmos de busca são fundamentais na ciência da computação, usados para encontrar 
soluções em espaços de busca. Esses algoritmos são aplicados em uma variedade de problemas, 
como navegação de robôs, resolução de quebra-cabeças, otimização de sistemas e em muitas 
outras áreas. Os algoritmos de busca podem ser classificados em duas categorias principais: 
busca cega e busca informada.1. Busca CegaA busca cega, também chamada de busca não 
informada, é um tipo de algoritmo de busca que explora o espaço de busca sem ter informações 
adicionais sobre a distância até a solução. Ou seja, a busca cega não usa heurísticas para guiar a 
pesquisa, e explora todos os estados possíveis até encontrar a solução. 
Os algoritmos mais comuns de busca cega incluem: 
• Busca em Largura (Breadth-First Search, BFS): A BFS explora todos os nós no 
nível atual antes de avançar para o próximo nível. Ela garante que a solução será 
encontrada no menor número de passos possíveis, desde que o caminho para a solução 
seja livre de ciclos. 
• Busca em Profundidade (Depth-First Search, DFS): A DFS explora cada ramificação 
do espaço de busca até o final antes de retroceder e explorar outras ramificações. 
Embora a DFS seja simples e eficiente em termos de memória, ela pode ficar presa em 
ciclos ou explorar áreas desnecessárias do espaço de busca. 
Vantagens da Busca Cega: 
• Simples de Implementar: A BFS e a DFS são relativamente fáceis de implementar. 
• Busca Completa: A BFS garante que a solução será encontrada, desde que exista uma 
solução no espaço de busca.Desvantagens da Busca Cega:Ineficiente em Termos de 
Memória e Tempo: Esses algoritmos podem ser ineficazes em termos de tempo e 
espaço, especialmente em problemas com grandes espaços de busca.Não Há Garantia 
de Solução Ótima: A BFS encontra a solução no menor número de passos, mas a DFS 
pode encontrar soluções subótimas. 
2. Busca InformadaA busca informada, ou busca heurística, utiliza informações adicionais 
(geralmente uma função de custo ou heurística) para guiar a exploração do espaço de busca. Ao 
contrário da busca cega, a busca informada foca nos nós que provavelmente levarão à solução 
mais rapidamente.. 
Questões:Qual é o principal objetivo dos algoritmos de busca informada? 
o (x) Guiar a busca usando informações adicionais, como heurísticas 
o ( ) Explorar todos os nós sem considerar heurísticas 
o ( ) Encontrar uma solução sem se preocupar com a eficiência 
o ( ) Garantir que a solução seja encontrada em um número mínimo de passos 
2. Qual algoritmo de busca é mais eficiente em termos de tempo e memória, pois utiliza 
heurísticas? 
o ( ) Busca em Largura 
o (x) Algoritmo A* 
o ( ) Busca em Profundidade 
o ( ) Busca Cega 
3. A busca em largura (BFS) garante que a solução será encontrada: 
o (x) No menor número de passos possíveis 
o ( ) Sem explorar nós desnecessários 
o ( ) Em todos os casos 
o ( ) Usando heurísticas para otimizar a busca