Busca A*
Dijkstra com senso de direção. Ao custo de cada lugar ele soma uma estimativa do custo que falta, então tenta primeiro os lugares que parecem mais perto da meta.
- tempo O((V + E) log V)
- memória O(V)
- usa uma fila de prioridade
O que significam esses termos?
- Custo: quanto custa um movimento. No labirinto, pisar no chão custa 1, na lama 3 e na água 9; no grafo, é o número na aresta.
- Fila de prioridade: uma fila em que passa primeiro o mais barato, não quem chegou antes.
- Estimativa (h): um palpite do custo que falta. O A* só continua exato se ela nunca for alta demais.
- Relaxar uma aresta: conferir se passar pelo lugar atual dá a um vizinho um custo menor e, se der, ficar com ele.
- na fila
- atual
- pronto
- caminho mais barato
- chão · 1
- lama · 3
- água · 9
- parede
Novo: Início em A1 com custo 0 e estimativa 26 até a meta. É o único na fila.
Espaço: reproduzir ou pausar. Setas esquerda e direita: avançar passo a passo. Home e End: pular.
Experimente: Escolha o campo aberto e alterne entre Dijkstra e A*: os dois acham um caminho de mesmo custo, mas o A* tira muito menos casas da fila.
Como funciona
A* funciona como Dijkstra, mas ordena a fila por f = custo acumulado + h, em que h estima o custo que falta. No labirinto, h é o número de movimentos até M ignorando paredes e lama; no grafo, a distância em linha reta dividida por 10. Enquanto h nunca exagerar, o caminho que o A* tem ao pegar a meta é o mais barato, exatamente como no Dijkstra. Quanto melhor a estimativa, menos lugares ele precisa olhar.
Quando é uma boa escolha
Use A* quando você procura uma única meta e consegue estimar a que distância ela está: pathfinding em jogos, robôs, planejadores de rota num mapa. Com h = 0 é exatamente Dijkstra. Uma estimativa que pode exagerar deixa o A* mais rápido, mas pode custar o caminho mais barato.