Entenda o que é o algoritmo A-estrela (A*) em menos de 3 minutos

[Música] a estrela é um algoritmo capaz de encontrar o caminho mais curto entre dois nós esse algoritmo pertence ao campo de Inteligência Artificial e é capaz de encontrar o caminho mais curto de forma autônoma sem ajuda de humanos um de seus pontos fortes é que ele é capaz de encontrar o caminho até o destino mesmo quando a obstáculos no caminho atuando com eficiência em jogos e aplicativos de navegação mesmo quando não a obstáculos esse algoritmo prova que pode chegar ao destino pelo caminho mais curto quando o caminho até o destino está bloqueado o algoritmo consegue

admitir que é impossível chegar ao destino Encerrando o processo a estrela usa dois valores para calcular o caminho mais curto até o destino o valor do custo acumulado até o momento e o valor do custo restante a soma desses dois valores é o que define qual o caminho é o mais curto quanto menor for o resultado da soma desses dois valores menor será o custo do caminho o algoritmo a estrela possui duas listas para gerenciar Cada nó a lista aberta e a lista fechada na lista aberta ficam os nós com potencial para o caminho mais

curto até o destino ali está aberta contém os nós em ordem crescente de custos os nós com menor custo estimado serão calculados com antecedência na lista fechada ficam os nós já calculados que não interessam mais ao algoritmo pois provavelmente não fazem parte do caminho mais eficiente o algoritmo calcula cada passo examinando os vizinhos do nosso atual se um vizinho apresenta um custo menor até o destino ele será colocado no primeiro lugar da lista aberta para que possa ser calculado com prioridade Caso seja descoberto mais tarde que esse caminho era um beco sem saída esses nós

serão adicionados a lista fechada o algoritmo repete esse comportamento até encontrar o destino final caso todos os nós forem adicionados a lista fechada e a lista aberta fique vazia isso quer dizer que o algoritmo não conseguiu encontrar o destino Encerrando o processo