Algoritmo A*

Introdução

O algoritmo A* é um algoritmo de busca em grafos, que se utiliza de uma heurística para auxiliar a ordem em que os nós são processados, com o intuito de diminuir o tempo de processamento.

Definição

A prioridade de processamento de um nó $x$ passa a ser definida como $f(x) = g(x) + h(x)$, onde $g(x)$ é a distância do nó a partir da origem no grafo e $h(x)$ é a distância prevista até o destino.

A função $h(x)$ deve sempre ser otimista, isto é, deve sempre retornar um valor que não seja maior que a distância real. Quanto mais próxima $h(x)$ estiver da real distância, mais rápido será o processamento.

Complexidade

A complexidade do A* depende diretamente da função $h(x)$ usada.
No pior caso, a quantidade de nós explorados é exponencial no tamanho do menor caminho, mas tem complexidade polinomial se $h^*(x) - h(x) \le O(\log h^*(x))$.

Quando usar?

O A* pode ser usado quando um caminho mais curto não é rápido o suficiente, embora seja a única opção válida para um dado problema.

Exemplos

  • Resolução de um 8-puzzle ou 15-puzzle, onde $h(x)$ é a distância de Manhattan entre a posição atual de $x$ e sua posição final.
  • Problemas de labirintos muito grandes, com $h(x)$ definida como a distância em linha reta ou sem obstáculos de $x$ até o destino.

Casos Especiais

Quando a função $h(x)$ tem valor constante (mais especificamente quando $h(x) = 0$), estaremos diante do algoritmo de Dijkstra para caminho mais curto.

Para praticar…

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License