O algoritmo A* (estrela A) é um algoritmo de busca heurística usado em ciência da computação para encontrar o caminho mais curto entre dois nós em um gráfico. É uma extensão do algoritmo de Dijkstra, que encontra o caminho mais curto mas não utiliza heurística.

Intuição

A* utiliza heurísticas, informações sobre o domínio do problema que ajudam a orientar sua busca. Essas heurísticas são frequentemente chamadas de heurísticas admissíveis ou de distância, porque nunca superestimam o custo real para atingir a meta. Em muitos casos, A* encontra soluções ótimas, embora nem sempre seja garantido que o faça.

Como funciona A*?

A* mantém dois conjuntos de nós durante sua busca:OPEN (Fringe) e CLOSED

ABRIR contém todos os nós que foram gerados, mas ainda não totalmente avaliados. É ordenado pela pontuação F (discutida abaixo) de seus membros, com a pontuação F mais baixa na frente.

FECHADO contém todos os nós que foram totalmente avaliados.

O algoritmo começa colocando o nó inicial em OPEN, enquanto o nó objetivo reside inicialmente em CLOSED. A cada passo do algoritmo, A* remove o nó em OPEN com a pontuação F mais baixa, expande-o e adiciona todos os seus vizinhos a OPEN. Se um vizinho ainda não estiver em ABERTO ou FECHADO, A* calcula uma pontuação G (o custo real para alcançar o vizinho a partir do nó inicial) e uma pontuação H (uma estimativa do custo para alcançar a meta do vizinho) para ele. e adiciona-o a OPEN. Se um vizinho já estiver em OPEN, a nova pontuação G é comparada com a pontuação G atual e, se a nova pontuação G for menor, o vizinho é atualizado. Se um vizinho já estiver em FECHADO, a nova pontuação G é comparada com a pontuação G atual, e se a nova pontuação G for menor, o vizinho é movido de FECHADO para ABERTO e atualizado.

Rescisão

O algoritmo termina de duas maneiras. Primeiro, se um vizinho do nó que está sendo expandido for o objetivo, o algoritmo retorna o caminho para o objetivo. Segundo, se OPEN ficar vazio, o algoritmo termina sem sucesso, indicando que não há caminho válido do nó inicial até o destino.

Complexidade

A complexidade de tempo do pior caso do algoritmo A* é exponencial no tamanho do gráfico. Entretanto, na prática, A* tem um bom desempenho em muitos problemas e muitas vezes encontra soluções ótimas em um período de tempo razoável.