Pesquisa A*

O algoritmo de Dijkstra encontra o caminho mais curto até um destino, mas procura em todas as direções ao mesmo tempo, mesmo para longe do destino. A pesquisa A* acrescenta um dado, uma estimativa de quão longe o destino ainda está, e de repente a pesquisa segue direta para ele.

Um grafo em que os nós concluídos formam uma faixa estreita da origem em direção ao destino, com uma linha reta tracejada a apontar para o destino e uma fila desenhada por baixo
Um grafo em que os nós concluídos formam uma faixa estreita da origem em direção ao destino, com uma linha reta tracejada a apontar para o destino e uma fila desenhada por baixo

A ideia

Quando procura uma rota num mapa, não explora as estradas que se afastam do seu destino com o mesmo cuidado que as que se aproximam dele. A pesquisa A* faz o mesmo. Cada nó recebe uma pontuação: a distância desde a origem até agora, g, mais uma estimativa da distância restante, h. A pesquisa continua sempre a partir do nó com a pontuação mais baixa, por isso os nós que ficam na direção do destino vêm primeiro.

Passo a passo

Dê à origem a distância 0 e coloque-a numa fila com a pontuação h(origem). Repita: retire o nó com a pontuação mais baixa e marque a sua distância como definitiva. Se for o destino, pare: seguir para trás os nós guardados dá o caminho. Caso contrário, para cada vizinho que não seja definitivo, calcule a sua distância através deste nó. Se for menor do que a sua distância até agora, baixe-a, guarde este nó como o caminho até lá e dê ao vizinho como pontuação a sua nova distância mais a sua estimativa. Quando duas pontuações são iguais, retirar primeiro o nó com a estimativa menor costuma chegar mais cedo ao destino.

Um exemplo

Tome uma origem A e um destino D. A–B mede 2 e B–D 2, enquanto A–C mede 1 e C–D 5. As estimativas em linha reta até D são 3 a partir de A, 2 a partir de B e 3 a partir de C. A começa com a pontuação 0 + 3 = 3. Retirar A dá a B a pontuação 2 + 2 = 4 e a C a pontuação 1 + 3 = 4. Com um empate, o A* retira B, o nó com a estimativa menor, e B dá a D a pontuação 4 + 0 = 4. D tem agora a pontuação mais baixa com a estimativa menor, por isso é retirado: o caminho mais curto é A → B → D, de comprimento 4, e C, que leva na direção errada, nunca fica definitivo. O algoritmo de Dijkstra teria tornado C definitivo primeiro, porque é o nó mais próximo de A.

Uma boa estimativa

A estimativa nunca pode ser maior do que a distância real até ao destino; uma estimativa assim chama-se admissível, e com ela o A* encontra sempre um caminho mais curto. A linha reta é admissível porque nenhuma rota é mais curta do que uma linha reta. Se, além disso, a estimativa nunca descer mais do que o comprimento de uma aresta de um nó para o seguinte, é consistente, e nenhum nó definitivo precisa de ser revisto. Quanto mais perto da verdade estiver a estimativa, de menos nós o A* precisa. Uma estimativa de 0 é admissível mas inútil: o A* passa então a ser o algoritmo de Dijkstra. Uma estimativa demasiado grande torna o A* mais rápido, mas pode falhar o caminho mais curto.

História e utilizações

Peter Hart, Nils Nilsson e Bertram Raphael, do Stanford Research Institute, publicaram o A* em 1968, enquanto trabalhavam no Shakey, um dos primeiros robôs móveis. As suas versões anteriores chamavam-se A1 e A2; a estrela marcava a versão que provaram ser ótima. Hoje, o A* move personagens à volta de obstáculos em videojogos, planeia rotas e movimentos de robôs, e resolve quebra-cabeças como o 15-puzzle, onde a estimativa soma a que distância cada peça está do seu lugar.

Shakey, o robô móvel do Stanford Research Institute, fotografado no Computer History Museum. Peter Hart, Nils Nilsson e Bertram Raphael publicaram o A* em 1968 enquanto trabalhavam nele.
Shakey, o robô móvel do Stanford Research Institute, fotografado no Computer History Museum. Peter Hart, Nils Nilsson e Bertram Raphael publicaram o A* em 1968 enquanto trabalhavam nele.

Experimente

Abra a app e prima Avançar. Os números nas arestas são os seus comprimentos, que aqui correspondem ao comprimento com que estão desenhadas, e a linha tracejada mostra a estimativa em linha reta até ao destino. A fila por baixo do grafo lista os nós por pontuação, a mais baixa primeiro. Quando o destino fica definitivo, a linha de estado compara quantos nós o A* tornou definitivos com quantos o algoritmo de Dijkstra teria precisado. Experimente um destino num canto afastado de um grafo grande para ver a maior diferença.

Perguntas frequentes

O que significa a estrela em A*?

Hart, Nilsson e Raphael descreveram primeiro algoritmos a que chamaram A1 e A2. O A* («A estrela») foi a versão que provaram encontrar um caminho mais curto expandindo o menor número de nós entre os algoritmos comparáveis que usam a mesma estimativa, quando a estimativa é consistente.

Qual é a complexidade temporal do A*?

No pior caso, com uma estimativa inútil, o A* faz o mesmo trabalho que o algoritmo de Dijkstra: O((V + E) log V) com uma heap binária. Com uma boa estimativa, torna definitiva apenas uma fração dos nós, e é por isso que é rápido na prática.

O que torna boa uma heurística para o A*?

Deve ser rápida de calcular, nunca sobrestimar a distância real e ficar o mais perto possível dela. Numa grelha onde só se pode mover para cima, para baixo, para a esquerda e para a direita, a distância de Manhattan é uma escolha comum; num mapa, a distância em linha reta.

E se a heurística sobrestimar?

Então o A* pode devolver um caminho que não é o mais curto, porque pode terminar antes de examinar a rota melhor. Alguns programas fazem isto de propósito (A* ponderado) para trocar um pouco de qualidade do caminho por muita velocidade.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Experimentar a pesquisa A*