Algoritmos de Busca em Python
Os algoritmos de busca são fundamentais em ciência da computação para resolver
problemas que envolvem navegar em espaços de estados ou encontrar caminhos em
grafos. Abaixo, explicamos como implementar cada um dos algoritmos de busca
mencionados em Python, utilizando um exemplo simplificado de um grafo representado
como um dicionário de adjacências. O grafo utilizado será:
1. Busca em Largura (Breadth-First Search - BFS)
A busca em largura explora o grafo camada por camada, expandindo todos os vizinhos de
um nó antes de passar para os nós no próximo nível do grafo.
grafo = {'A': {'B', 'C'}, 'B': {'A', 'D'}, 'C': {'A', 'E'}, 'D': {'B'}, 'E': {'C'}}
bfs(grafo, 'A')
2. Busca em Custo Uniforme
É uma generalização do BFS que considera os custos dos caminhos. Assim, em vez de
expandir o nó mais "velho" primeiro, ele expande o nó com o menor custo de caminho
acumulado.
heapq.heappush(fila, (custo_acumulado + custos[(vertice, vizinho)], vizinho))
grafo = {'A': {'B', 'C'}, 'B': {'A', 'D'}, 'C': {'A', 'E'}, 'D': {'B'}, 'E': {'C'}}
3. Busca em Profundidade (Depth-First Search - DFS)
Este algoritmo explora o grafo seguindo caminhos tão fundos quanto possível antes de
retroceder.
grafo = {'A': {'B', 'C'}, 'B': {'A', 'D'}, 'C': {'A', 'E'}, 'D': {'B'}, 'E': {'C'}}
4. Busca em Aprofundamento Limitado (Depth-Limited Search)
É uma versão do DFS que limita a profundidade até a qual o algoritmo busca.
grafo = {'A': {'B', 'C'}, 'B': {'A', 'D'}, 'C': {'A', 'E'}, 'D': {'B'}, 'E': {'C'}}
5. Busca em Aprofundamento Iterativo (Iterative Deepening Search - IDS)
Este método combina a profundidade limitada da busca em profundidade com a
abrangência da busca em largura. Ele realiza repetidamente a busca em profundidade,
aumentando o limite de profundidade a cada iteração até encontrar o objetivo.
if vizinho not in visitados and dfs_limitado(vizinho, limite - 1, visitados):
grafo = {'A': {'B', 'C'}, 'B': {'A', 'D'}, 'C': {'A', 'E'}, 'D': {'B'}, 'E': {'C'}}
6. Busca Gulosa pela Melhor Escolha (Greedy Best-First Search)
Este algoritmo seleciona o caminho que parece ser o melhor em cada passo. Ele usa uma
função heurística para estimar o custo do caminho do nó atual até o objetivo e escolhe o
nó com o menor custo estimado.
grafo = {'A': {'B', 'C'}, 'B': {'A', 'D'}, 'C': {'A', 'E'}, 'D': {'B'}, 'E': {'C'}}
heuristicas = {'A': 3, 'B': 2, 'C': 2, 'D': 1, 'E': 0}
# Exemplo de heurísticas para o objetivo 'E'
7. Busca em A* (A-Star Search)
A* é um algoritmo de busca que encontra o caminho mais curto entre o nó inicial e o nó
objetivo enquanto tenta minimizar o custo total do caminho e o custo estimado para
chegar ao objetivo. Usa tanto o custo real do caminho até o momento (g) quanto uma
função heurística (h) que estima o custo para chegar ao objetivo.
heappush(fila, (heuristicas[inicio], 0, inicio, [])) # (f, g, vertice, caminho)
grafo = {'A': {'B', 'C'}, 'B': {'A', 'D'}, 'C': {'A', 'E'}, 'D': {'B'}, 'E': {'C'}}
custos = {('A', 'B'): 1, ('A',
