3. O Algoritmo A*
- Estrutura principal do A*
- Papel do open set e do closed set
- Como nós são selecionados e expandidos
- Como as atualizações de caminho são feitas
- Template clássico em pseudocódigo
Uma vez definidos o modelo do problema e a função heurística, o próximo passo é entender como o A* executa a busca.
No núcleo do algoritmo, o A* seleciona repetidamente o nó mais promissor, expande seus vizinhos e atualiza a fronteira usando custos exatos e estimativas heurísticas.
3.1 Fronteira e Estados Explorados
O A* mantém dois conjuntos principais durante a execução:
- open set: nós descobertos mas ainda não explorados
- closed set: nós já expandidos
O open set representa a fronteira da busca.
O closed set evita a reexploração de estados já processados.
3.2 Regra de Seleção
Em cada passo, o A* seleciona o nó com menor valor de f(n) = g(n) + h(n).
Essa escolha equilibra o custo já percorrido com a estimativa do custo restante.
Na prática, isso é implementado com uma fila de prioridade.
3.3 Expansão de Nós
Ao expandir um nó, o algoritmo analisa todos os seus vizinhos.
Para cada vizinho, calcula-se:
Esse valor representa o custo de alcançar o nó vizinho passando pelo nó atual.
3.4 Atualização de Caminho
Se o novo caminho para um vizinho for melhor, o algoritmo atualiza:
- o pai (predecessor)
- o valor de g(n)
- o valor de f(n)
O nó é então inserido ou atualizado no open set.
3.5 Detecção do Objetivo
A busca termina quando o nó objetivo é selecionado para expansão.
O caminho ótimo é reconstruído seguindo os ponteiros de predecessores do objetivo até a origem.
3.6 Template do A*
A*(início, objetivo):
open_set = fila de prioridade ordenada por f
closed_set = conjunto vazio
g(início) = 0
f(início) = h(início)
enquanto open_set não estiver vazio:
n = extrair nó com menor f
se n é objetivo:
retornar caminho
para cada vizinho m:
custo = g(n) + c(n, m)
se melhor caminho:
atualizar m
retornar falha
3.7 Fila de Prioridade
A eficiência do A* depende diretamente da estrutura usada no open set.
- heap binário
- Fibonacci heap
3.8 Resumo Operacional
- selecionar o melhor nó
- expandir vizinhos
- atualizar custos
Próximo: Parte 4 — Otimalidade & Complexidade
Agora que entendemos como o algoritmo funciona, vamos analisar suas garantias teóricas.