1. Modelo do Problema
- Como problemas de caminho mínimo são modelados
- Representação de estados na busca em grafos
- O papel do custo de caminho
- O papel da estimativa heurística
- A função de avaliação do A*
O A* opera sobre um modelo formal de busca cujo objetivo é encontrar um caminho ótimo entre dois nós em um grafo ponderado.
Compreender esse modelo é essencial antes de analisar o algoritmo em si.
1.1 Modelo de Grafo
O problema é definido sobre um grafo ponderado:
onde cada aresta possui um custo associado:
O objetivo é encontrar um caminho de custo mínimo de um nó inicial s até um nó objetivo t.
1.2 Representação de Estado
Cada nó do grafo corresponde a um estado no espaço de busca.
Um estado contém:
- nó atual
- custo acumulado do caminho
- referência ao pai (para reconstrução do caminho)
O algoritmo explora estados expandindo seus vizinhos.
1.3 Custo do Caminho
A função g(n) representa o custo exato do nó inicial até n.
Esse custo é calculado incrementalmente conforme a busca avança.
Essa componente é idêntica à utilizada no algoritmo de Dijkstra.
1.4 Estimativa Heurística
A função h(n) estima o custo restante de n até o objetivo.
Ela não é exata, mas fornece uma direção para a busca.
A eficiência do A* depende fortemente dessa estimativa.
1.5 Função de Avaliação
O A* avalia os nós usando:
Isso representa o custo total estimado de um caminho solução passando pelo nó n.
O algoritmo expande o nó com menor valor de f(n).
1.6 Intuição Principal
O A* equilibra dois componentes:
- g(n): custo já acumulado
- h(n): custo estimado restante
Isso permite que o A* se comporte como:
- Dijkstra (quando h(n) = 0)
- Busca Gulosa (quando g(n) é ignorado)
Próximo: Parte 2 — Funções Heurísticas
A função heurística é o componente central que torna o A* um algoritmo de busca informada.
Na próxima parte, formalizamos o que são heurísticas, como elas guiam a busca e introduzimos propriedades fundamentais como admissibilidade e consistência.