4. Otimalidade & Complexidade
- Quando o A* retorna soluções ótimas
- O papel da admissibilidade
- O papel da consistência
- Como analisar sua complexidade
- Por que a qualidade da heurística importa
O A* não é apenas um algoritmo prático de busca, mas também um algoritmo com fortes garantias teóricas.
Essas garantias dependem diretamente das propriedades da heurística e da estrutura do espaço de busca.
4.1 O que significa otimalidade
O A* é ótimo se sempre retorna um caminho de custo mínimo do nó inicial até o objetivo.
Se C* é o custo do caminho ótimo, então a solução retornada pelo A* tem custo C*.
A pergunta central é: sob quais condições isso é garantido?
4.2 Admissibilidade
Uma heurística é admissível se nunca superestima o custo real restante.
Isso garante que f(n) = g(n) + h(n) nunca seja uma subestimação otimista indevida do custo real de uma solução.
Com heurísticas admissíveis, o A* (em busca em árvore) é garantido encontrar uma solução ótima.
4.3 Consistência
Consistência é uma condição mais forte do que admissibilidade.
para toda aresta (n, n').
Isso impõe uma propriedade análoga à desigualdade triangular sobre a heurística.
Com consistência, os valores de f(n) são não decrescentes ao longo dos caminhos.
4.4 Busca em árvore vs busca em grafo
Em busca em árvore, estados podem ser revisitados várias vezes.
Em busca em grafo, um closed set é usado para evitar expansões redundantes.
A consistência garante que, uma vez que um nó é expandido com valor mínimo de f, seu custo ótimo já foi encontrado.
4.5 Completeza
O A* também é completo sob hipóteses padrão.
Isso significa que, se uma solução existir, o algoritmo eventualmente irá encontrá-la.
Isso normalmente vale em grafos finitos com custos de arestas positivos.
4.6 Complexidade de tempo
No pior caso, o A* pode explorar um número exponencial de nós.
Assim, a complexidade de tempo no pior caso permanece exponencial na profundidade da solução.
No entanto, boas heurísticas reduzem drasticamente o número de estados explorados na prática.
4.7 Complexidade de espaço
O A* possui exigências significativas de memória.
Ele armazena a fronteira, custos, predecessores e, muitas vezes, o conjunto de estados explorados.
Portanto, a complexidade de espaço também é tipicamente exponencial.
4.8 Qualidade da heurística
A eficiência do A* depende fortemente de quão informativa a heurística é.
- heurística fraca → mais exploração
- heurística forte → menos exploração
Idealmente, a heurística deve ser o mais próxima possível do custo real, permanecendo admissível.
4.9 Casos extremos
- h(n) = 0 → A* se torna Dijkstra
- h(n) = h*(n) → heurística perfeita
Esses casos ilustram o espectro entre busca não informada e busca perfeitamente informada.
Próximo: Parte 5 — Comparações & Aplicações
Agora que entendemos correção e complexidade, o próximo passo é posicionar o A* entre outros algoritmos.
Na Parte 5, comparamos o A* com algoritmos clássicos de busca e exploramos aplicações do mundo real.