Pesquisa A*
O Dijkstra com sentido de orientação. Ao custo de cada lugar soma uma estimativa do custo que falta, por isso experimenta primeiro os lugares que parecem mais perto do destino.
- tempo O((V + E) log V)
- memória O(V)
- usa uma fila de prioridade
O que significam estes termos?
- Custo: quanto custa um movimento. No labirinto, pisar o chão custa 1, a lama 3 e a água 9; no grafo, é o número na aresta.
- Fila de prioridade: uma fila onde passa primeiro o mais barato, não quem chegou primeiro.
- Estimativa (h): uma previsão do custo que falta. O A* só se mantém exato se ela nunca for alta demais.
- Relaxar uma aresta: verificar se passar pelo lugar atual dá a um vizinho um custo mais baixo e, se der, ficar com ele.
- na fila
- atual
- terminado
- caminho mais barato
- chão · 1
- lama · 3
- água · 9
- parede
Novo: Início em A1 com custo 0 e estimativa 26 até ao destino. É o único na fila.
Espaço: reproduzir ou pausar. Setas esquerda e direita: avançar passo a passo. Home e End: saltar.
Experimente: Escolha o campo aberto e alterne entre Dijkstra e A*: ambos encontram um caminho com o mesmo custo, mas o A* tira muito menos casas da fila.
Como funciona
O A* funciona como o 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 a dividir por 10. Enquanto h nunca exagerar, o caminho que o A* tem ao tirar o destino é o mais barato, tal como no Dijkstra. Quanto melhor a estimativa, menos lugares precisa de ver.
Quando é uma boa escolha
Use o A* quando procura um único destino e consegue estimar a que distância está: pathfinding em jogos, robôs, planeadores de rotas num mapa. Com h = 0 é exatamente o Dijkstra. Uma estimativa que pode exagerar torna o A* mais rápido, mas pode custar o caminho mais barato.