Definitivo
Na fila
Arestas verificadas

  • Atual
  • Na fila
  • Definitivo
  • Caminho
  • Estimativa em linha reta
Um clique num nó define

Mais sobre a pesquisa A*

Pesquisa A*

A pesquisa A* encontra um caminho mais curto de uma origem até um destino, como o algoritmo de Dijkstra, mas sabe mais ou menos onde fica o destino. Cada nó recebe uma estimativa da distância restante, a linha reta até ao destino, e a pesquisa continua sempre a partir do nó com a menor distância até agora mais essa estimativa. Clique num nó para começar a partir dele, escolha um destino e avance passo a passo para ver a pesquisa seguir em direção ao destino e deixar cantos inteiros do grafo intactos. Prima Reproduzir para ver a pesquisa, ou Avançar e Recuar para ir um passo de cada vez. Arraste a barra de passos para saltar para qualquer ponto. Clique num nó para o tornar a origem; mude o clique para Destino e clique noutro nó para o tornar o destino. O número em cada aresta é o seu comprimento, o número em cada nó a sua distância até agora, e a linha tracejada a estimativa em linha reta da distância restante. A linha por baixo do grafo é a fila, com a pontuação mais baixa primeiro, e mostra a pontuação de cada nó: a distância até agora mais a estimativa. Novo grafo cria outro grafo; escolha quantos nós e arestas tem. Com o tabuleiro selecionado, as setas avançam e recuam um passo, a barra de espaço reproduz e pausa, e Home e End saltam para o início e o fim.

Como funciona

  1. Clique num nó para o tornar a origem. Mude o clique para Destino e clique noutro nó para o tornar o destino.
  2. Prima Reproduzir, ou use Avançar e Recuar para ir um passo de cada vez. Arraste a barra de passos para saltar para qualquer ponto da pesquisa.
  3. Observe as pontuações na fila e a estimativa em linha reta tracejada. No fim, compare os nós de que o A* precisou com os do algoritmo de Dijkstra.

Como funciona a pesquisa A*

Dê à origem a distância 0 e coloque-a numa fila. Cada nó na fila tem uma pontuação: a sua distância até agora mais uma estimativa da distância restante. Repita: retire o nó com a pontuação mais baixa e marque a sua distância como definitiva. Se for o destino, pare. Caso contrário, para cada vizinho que não seja definitivo, some o comprimento da aresta à distância do nó; se for menor do que a distância até agora do vizinho, baixe-a, guarde o nó como o caminho até lá e coloque o vizinho na fila com a sua nova pontuação.

Porque é que a estimativa nunca pode ser demasiado longa

O A* encontra um caminho mais curto desde que a estimativa nunca diga que o destino está mais longe do que realmente está: uma estimativa admissível. A linha reta é uma delas, porque nenhuma estrada entre dois lugares é mais curta do que a linha reta. Uma estimativa demasiado longa pode fazer o A* saltar a melhor rota; uma estimativa de 0 em todo o lado transforma o A* no algoritmo de Dijkstra, que é seguro mas procura em todas as direções. Quanto melhor a estimativa, de menos nós o A* precisa. Na app, cada aresta tem o comprimento com que está desenhada, arredondado para cima, por isso a linha reta é uma estimativa segura.

Perguntas frequentes

O que é a pesquisa A*?

Um algoritmo de procura de caminhos que encontra um caminho mais curto de uma origem até um destino. Funciona como o algoritmo de Dijkstra, mas ordena a fila pela distância até agora mais uma estimativa da distância restante, por isso segue em direção ao destino em vez de se espalhar em todas as direções.

O que é uma heurística admissível?

Uma estimativa da distância até ao destino que nunca é maior do que a verdadeira distância mais curta. Com uma estimativa admissível, o A* encontra sempre um caminho mais curto. A distância em linha reta num mapa é o exemplo clássico.

O A* é mais rápido do que o algoritmo de Dijkstra?

Normalmente sim, quando precisa do caminho até um só destino e tem uma boa estimativa: o A* torna definitivos menos nós, porque os nós afastados do destino recebem pontuações altas. Com uma estimativa de 0, faz exatamente o mesmo que o algoritmo de Dijkstra. O algoritmo de Dijkstra é a melhor escolha quando precisa das distâncias até todos os nós.

Onde se usa o A*?

Em videojogos, para mover personagens à volta de obstáculos, em planeadores de rotas, no planeamento de movimentos de robôs e em resolvedores de quebra-cabeças como o 15-puzzle, onde a estimativa conta a que distância as peças estão dos seus lugares.

O meu grafo é enviado para algum lado?

Não. O grafo é criado e percorrido no seu navegador, e as suas últimas definições ficam no armazenamento local deste navegador.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Ir para o editor