A* algoritmo de busca
A* é um conjunto de passos (um algoritmo) que os computadores podem usar para descobrir como chegar rapidamente a algum lugar entre dois lugares. Se você tem uma lista de locais, e como é difícil chegar de um direto ao outro, usando A* pode rapidamente dizer-lhe o caminho mais rápido. Está relacionado ao algoritmo do Dijkstra, mas faz suposições inteligentes para que ele não gaste tanto tempo tentando caminhos lentos. É uma boa série de passos, se você quiser apenas o caminho entre dois lugares. Se você vai pedir muitos caminhos do mesmo mapa, então existem caminhos mais rápidos, que encontram todas as respostas de uma vez, como o algoritmo Floyd-Warshall. A* não funcionará se você quiser visitar vários lugares em uma única viagem (o problema do vendedor ambulante).
As etapas
A* primeiro precisa de uma lista de todos os lugares para onde você pode ir, e depois precisa de uma lista de quão longe está o caminho entre cada um deles. Em seguida, ele lhe dirá a maneira mais rápida de ir do lugar A para o lugar Z.
Por exemplo, diremos que A está conectado aos lugares B e C, e B e C estão ambos conectados a D e E. D e E estão ambos conectados a Z. Há 4 maneiras possíveis de ir de A a Z. Você pode ir A-B-D-Z, A-C-D-Z, A-B-E-Z, ou A-C-E-Z. Um computador usando A* primeiro observa como é difícil passar de A para B, e de A para C. Este é o "custo" para esses lugares. O custo de um lugar significa o quanto é difícil ir de A para aquele lugar. Depois de anotar os dois custos, o computador analisa como é difícil passar de B para D, e acrescenta isto ao custo de B. Ele anota isso como custo de D. Em seguida, o computador observa como é difícil passar de C para D, e acrescenta isto ao custo de C. Este é um custo diferente para D, e se for menor do que o que já tem, substituirá o antigo. O computador só quer saber o melhor caminho, então ele ignora o caminho com o custo mais alto. Ele só se lembrará de um de A-B-D e A-C-D, o que for mais rápido.
O computador continua e encontra a maneira mais rápida de chegar a E. Finalmente, vai de D a Z, e encontra um custo, e de E a Z e encontra um custo. Recebe um custo final para Z, e este é o menor custo que ele pode obter. Agora o computador sabe qual é o caminho mais rápido, e tem a resposta. O computador pode fazer uma série semelhante de passos, mas com muito mais lugares. Cada vez, ele olhará para o lugar mais próximo de A, e somará os custos aos vizinhos daquele lugar.
As pessoas chamam a série de passos acima de algoritmo da Dijkstra. O algoritmo de Dijkstra pode ser lento, porque ele vai olhar para muitos lugares que podem estar indo na direção errada de Z. Se você perguntar ao computador como ir de uma cidade para uma próxima, o algoritmo de Dijkstra pode acabar procurando em outro estado.
A* corrige este problema. A* permite que você diga ao computador um palpite de quão longe ele estará de cada lugar até o final. O computador pode usar o palpite para dizer aproximadamente a distância que levará para chegar de um determinado lugar a Z. Em vez de apenas escolher o lugar mais próximo de A para olhar, ele olhará para aquele que provavelmente terá o total mais baixo. Ele encontra este total somando o custo à distância esperada. Desta forma, ele pode olhar apenas na direção em que as coisas provavelmente vão melhorar. Tudo bem se o palpite não for perfeito, mas mesmo um simples palpite ruim pode fazer o programa andar muito mais rápido. Se você estiver tentando encontrar um caminho entre dois lugares no mundo real, um bom palpite é apenas a distância entre eles em uma linha reta. O caminho real sobre as estradas será mais longo, mas isto permite ao programa adivinhá-lo, e não irá na direção errada.
Na literatura matemática ou informática, este palpite é muitas vezes uma função do lugar, e é chamado de heurístico. Cada lugar é um vértice, e cada caminho entre dois lugares é uma borda. Estas são palavras da teoria dos gráficos.
