2. Funções Heurísticas
- O que é uma função heurística
- Por que heurísticas são importantes no A*
- A diferença entre custo exato e custo estimado
- O conceito de admissibilidade
- O conceito de consistência
A função heurística é o componente que transforma o A* de uma busca de caminho mínimo não informada em uma busca informada.
Ela fornece conhecimento direcional sobre o objetivo, ajudando o algoritmo a priorizar estados mais promissores.
2.1 Definição de Heurística
Uma heurística é uma função h(n) que estima o custo do caminho mais barato do nó n até um nó objetivo.
Trata-se de uma estimativa, não de um valor exato.
Seu objetivo é guiar a busca em direção ao objetivo sem explorar completamente o grafo restante.
2.2 Papel no A*
O A* avalia estados usando:
Aqui, g(n) mede o custo exato acumulado até o momento, enquanto h(n) estima o custo restante.
A heurística, portanto, influencia qual nó será explorado a seguir.
2.3 Intuição
Sem heurística, o algoritmo não possui preferência direcional em relação ao objetivo.
Com uma heurística, a busca passa a ter uma noção de quão distante um estado está do sucesso.
Heurísticas melhores geralmente reduzem o número de nós explorados.
2.4 Exemplos Típicos
Em problemas de pathfinding em grids, heurísticas comuns incluem:
- Distância de Manhattan
- Distância Euclidiana
- Distância de Chebyshev
Essas funções não calculam o custo exato do caminho restante, mas fornecem uma boa aproximação baseada em geometria.
2.5 Admissibilidade
Uma heurística é admissível se nunca superestima o custo real restante.
onde h*(n) representa o custo ótimo real de n até o objetivo.
A admissibilidade é uma condição fundamental para a otimalidade do A*.
2.6 Consistência
Uma heurística é consistente se, para toda aresta (n, n'), vale:
Essa condição é análoga à desigualdade triangular.
A consistência garante que o custo estimado total não diminua inesperadamente ao longo de um caminho.
2.7 Heurísticas Fracas vs Fortes
Nem todas as heurísticas admissíveis são igualmente informativas.
Uma heurística é considerada mais forte quando se aproxima mais do custo real sem violar a admissibilidade.
- heurística fraca → mais nós explorados
- heurística forte → menos nós explorados
2.8 Casos Extremos
Alguns casos especiais ajudam a entender o papel da heurística:
- h(n) = 0 para todo n → A* se reduz ao algoritmo de Dijkstra
- g(n) ignorado → a busca se comporta como busca gulosa (Greedy Best-First Search)
O A* equilibra esses extremos combinando custo exato com custo estimado futuro.
Próximo: Parte 3 — O Algoritmo A*
Agora que as funções heurísticas foram definidas, o próximo passo é estudar como o A* realmente opera.
Na Parte 3, apresentamos a estrutura do algoritmo A*, incluindo expansão de nós, seleção baseada em prioridade e o papel das estruturas open e closed.