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.
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.
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*