Algoritmo A*

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Algoritmo A* (Lê-se: A-estrela) é um algoritmo para Busca de Caminho. Ele busca o caminho em um grafo de um vértice inicial até um vértice final. Ele é a combinação de aproximações heurísticas como do algoritmo Best-first Search e da formalidade do Algoritmo de Dijkstra.

O algoritmo foi descrito pela primeira vez em 1968 por Peter Hart, Nils Nilsson, e Bertram Raphael. Na publicação deles, ele foi chamado de algoritmo A; usando este algoritmo com uma heurística apropriada atinge-se um comportamento ótimo, e passou a ser conhecido por A*.

Sua aplicação vai desde aplicativos para encontrar rotas de deslocamento entre localidades a resolução de problemas, como a resolução de um quebra-cabeças. Ele é muito usado em jogos.

Algoritmo[editar | editar código-fonte]

Sejam

Q = conjunto de nós a serem pesquisados;
S = o estado inicial da busca

Faça:

  1. Inicialize Q com o nó de busca (S) como única entrada;
  2. Se Q está vazio, interrompa. Se não, escolha o melhor elemento de Q;
  3. Se o estado (n) é um objetivo, retorne n;
  4. (De outro modo) Remova n de Q;
  5. Encontre os descendentes do estado (n) que não estão em visitados e crie todas as extensões de n para cada descendente;
  6. Adicione os caminhos estendidos a Q e vá ao passo 2;
caminhos expandidos;

Uma estimativa que sempre subestima o comprimento real do caminho ate o objetivo é chamada de admissível. O uso de uma estimativa admissível garante que a busca de custo-uniforme ainda encontrará o menor caminho.

Ligações externas[editar | editar código-fonte]

Commons
O Commons possui imagens e outras mídias sobre Algoritmo A*
Ícone de esboço Este artigo sobre Informática é um esboço. Você pode ajudar a Wikipédia expandindo-o.