Algoritmo A* (A-estrela)

O contexto que um programa de computador roda, afeta diretamente o tipo de algoritmo que será implementado. Uma simples tarefa como a busca de algum elemento dentro de uma lista pode ser realizada usando métodos de busca linear. Porém, programas que necessitam de mais eficiência podem optar pela busca binária.

Conforme o contexto do programa muda, os algoritmos precisam ser adaptados. Em aplicativos de navegação ou em jogos, algoritmos de busca também são implementados para encontrar o caminho mais curto entre dois objetos, como a distância atual do usuário até um determinado objeto. Um algoritmo bastante eficiente para encontrar o menor caminho entre dois pontos é o algoritmo A*.

O que é o algoritmo A*?

O algoritmo A-estrela é um método que busca o caminho mais curto entre dois pontos. Esse método usa os valores de duas funções para estimar o melhor caminho em relação ao custo, cujos valores são o G e o H.

• G: Valor do custo acumulado do caminho percorrido
• H: Valor restante do custo necessário até o destino

A soma dos dois valores acima estimam o caminho mais eficiente de um ponto inicial até o ponto final. O resultado dos valores acima é representado com a letra F e quanto menor for esse valor, menos custoso será o trajeto calculado.

O algoritmo A* é considerado um algoritmo inteligente, uma vez que ele pode encontrar o seu destino automaticamente sem a intervenção humana. A eficiência desse algoritmo é bastante relativo, tendo o seu desempenho diretamente influenciado pelo contexto do programa, com fatores como a qualidade dos dados de entrada e os métodos heurísticos adotados. Alguns métodos heurísticos utilizados com frequência são a distância de Manhattan e a distância euclidiana. Geralmente, o método heurístico é usado para estimar o menor valor possível até o destino do objeto.

Onde o algoritmo A* pode ser usado com efetividade?

O algoritmo A* pode ser usado em exercícios de grafos ou mapas para calcular a menor distância entre dois pontos. Esse algoritmo pode ser usado em jogos, aplicativos de navegação e em robôs.

No exemplo acima, seguindo a ordem das setas, teríamos 3 opções de caminhos até o ponto final (ponto vermelho). Sem nenhum cálculo é possível perceber que o caminho mais curto é o G, H, I. Porém, o método A* pode ser usado em problemas muito mais complexos, contendo muito mais valores complexos a serem considerados do que o exemplos acima.

Um labirinto 2D é um bom candidato para ter um algoritmo A* implementado. Um labirinto, geralmente possui diversos obstáculos e caminhos sem saída até chegar ao seu destino final.

Na imagem acima, temos um labirinto 2D, onde cada cor tem uma representação:

• Quadrados brancos: Paredes (Obstáculo)
• Quadrados azuis: Quadrados calculados para estimar o menor caminho
• Quadrados vermelhos: Menor caminho estimado até o destino
• Quadrado verde: Início
• Quadrado amarelo: Destino

É possível perceber que no exemplo acima, os valores na diagonal também são calculados. O labirinto acima possui ao todo 651 quadrados (31x21). O total de quadrados que tiveram que ser calculados até podermos estimar o menor caminho até o destino foi de 247 quadrados. Isso é apenas 37% do total de quadrados. Sendo que 44% (291 quadrados) do labirinto é composto de paredes e 56% (360 quadrados) do labirinto é composto por quadrados pretos (caminho com possibilidade de locomoção), podemos chegar a conclusão que apenas 68% dos quadrados pretos foram necessários para estimar o melhor caminho até o destino, o que é bastante eficiente para um labirinto com caminhos estreitos. Mas o que aconteceria se não tivéssemos paredes? Veja o resultado abaixo:

O exemplo acima possui um mapa de 651 quadrados (31x21) e não contém paredes. A quantidade total de quadrados que precisaram ser calculados para estimar o menor caminho foi 19 quadrados, ou seja, 2.9% de quadrados em relação ao mapa. Assim, podemos chegar a conclusão que o algoritmo A* é bastante eficiente. Porém, em mapas complexos contendo obstáculos, ele tem uma notação de O(n), onde o “n” é a quantidade de quadrados a serem calculados.

Como aplicar o algoritmo A*?

A aplicação do algoritmo A* pode variar dependendo do contexto do programa. Um dos métodos que mais podem variar é o método de heurística, usado para calcular a distância do ponto atual até o ponto final. A fórmula para calcular o melhor caminho do ponto atual até o destino é:

• f(n) = g(n) + h(n)

Onde o “g” é o caminho total percorrido até o ponto atual e o “h” é a heurística do ponto atual até o destino. O “f” é o custo total estimado do ponto atual até o destino.

Geralmente, o algoritmo A* usa duas variáveis para gerenciar o programa:

• Lista aberta
• Lista fechada

Lista aberta

A lista aberta contém pontos (coordenadas) que ainda não tiveram o seu melhor custo calculado. Dependendo do caminho do início até o ponto atual, ainda podem haver rotas com menores custos até o destino final. Pontos que ainda precisam ser calculados, estarão situados dentro da lista aberta.

Os pontos dentro da lista aberta terão o seu custo calculado através dos seus pontos vizinhos. O algoritmo testa todas as direções possíveis a partir do ponto atual, se locomovendo um intervalo a frente (x + 1 ou y + 1 em espaços 2D) e calculando a heurística para chegar ao ponto final. A direção que apresenta menor heurística será escolhida e adicionada à lista aberta com o ponto atual como parente.

Lista fechada

A lista fechada contém objetos que já tiveram todos os seus vizinhos calculados. Os objetos inseridos na lista fechada são interpretados como concluídos ou custosos e ineficientes. Uma vez que a coordenada é inserida na lista fechada, ela passa a ser ignorada, fazendo com que a lista aberta continue avançando até chegar ao destino final.

Como funciona o algoritmo A*?

O algoritmo A* pode variar dependendo do contexto e das técnicas adotadas. Um dos diversos exemplos de algoritmo A* que existem é o abaixo:

As etapas do algoritmo acima em detalhes são:

1. Início
2. Adiciona o ponto inicial na lista aberta para que o algoritmo comece a operar
3. Ordena a lista aberta pelos itens que apresentaram menos custos até o destino
4. Pega o primeiro item da lista aberta
5. Examina todas as direções vizinhas do ponto atual e calcula o caminho mais curto
6. Checa se o ponto atual chegou ao destino. Se sim, finaliza o programa. Se não, continua.
7. Coloca o ponto atual na lista fechada com antecedência
8. Cria uma repetição (loop) para examinar cada direção (vizinho) disponível do ponto atual
9. Vizinho atual (ponto) já está adicionado na lista aberta? Se sim, continua. Se não, inseri o vizinho na lista com o ponto atual como parente.
10. Vizinho atual já está adicionado a lista, mas apresenta um menor custo até o destino? Se sim, substitui o item existente da lista com o vizinho atual.
11. Volta para a etapa 3 após finalizar a repetição.

Conclusão

O algoritmo A* é uma técnica de busca do menor caminho possível entre o ponto inicial e o destino. Esse método pode ser implementado tanto em simples problemas até em problemas complexos. Esse algoritmo é considerado como parte do campo de inteligência artificial de sistemas de busca inteligente.