Algoritmo A*
Origem: Wikipédia, a enciclopédia livre.
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.
[editar] Ligações externas
- ((pt)) A* Pathfinding para Iniciantes
- ((pt)) Projeto de Pesquisa de Algoritmos de Busca
- ((en)) A* Demonstration Uma demonstração visual do algoritmo, usando Applet Java
- ((en)) Amit's A* Pages -- Path finding Texto bastante completo sobre busca de caminhos (Path finding) usando o Algoritmo A*
