Algoritmo de Busca A*
- Proposto por
- Peter E. Hart, Nils J. Nilsson, and Bertram Raphael
- Ano
- 1968
- Tipo
- algorithm
- Família
- Graph Algorithms
Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês
O que ele faz?
O Algoritmo de Busca A*, desenvolvido por Peter E. Hart, Nils J. Nilsson e Bertram Raphael em 1968, é um algoritmo de busca de caminho ótimo que combina os benefícios do algoritmo de Dijkstra com orientação heurística.
Ele encontra eficientemente o caminho mais curto, equilibrando a distância real do início com a distância estimada até o objetivo.
A intuição por trás do método
A* utiliza uma função de avaliação f(n) = g(n) + h(n), onde g(n) é o custo real do início até o nó n, e h(n) é uma estimativa heurística do custo restante até o objetivo. Ao explorar nós com o menor valor de f(n), o algoritmo restringe eficientemente o espaço de busca em direção ao objetivo, mantendo a otimalidade quando a heurística é admissível (nunca superestima). Isso torna o A* significativamente mais rápido do que os métodos de busca não informada, ao mesmo tempo em que garante encontrar o caminho ótimo.
História
Hart, Nilsson e Raphael publicaram A* em 1968, demonstrando que adicionar informações heurísticas ao algoritmo de Dijkstra poderia melhorar drasticamente a eficiência da busca, mantendo a otimalidade. O algoritmo tornou-se fundamental em inteligência artificial e pesquisa operacional. Desenvolvimentos subsequentes incluem A* bidirecional, IDA* (aprofundamento iterativo) e várias melhorias heurísticas. A* continua sendo a escolha padrão para busca de caminhos em motores de jogos modernos e sistemas de robótica.
Quando usar
Aplique A* quando precisar encontrar caminhos ótimos em grafos onde uma boa função heurística esteja disponível. É particularmente eficaz para busca de caminhos em jogos, robótica e planejamento de rotas, onde a busca informada pode reduzir substancialmente a computação. Use-o quando a velocidade for importante, mas a otimalidade for necessária. Para casos sem uma heurística confiável, use o algoritmo de Dijkstra.
Limitações e considerações
- A otimalidade depende da admissibilidade da função heurística
- O desempenho degrada significativamente com heurísticas ruins ou inadmissíveis
- O uso de memória pode ser substancial em grandes espaços de busca (mantém conjuntos abertos e fechados)
- Requer conhecimento de domínio explícito para projetar boas funções heurísticas
As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.
Pontos fortes
- Busca de caminho ótimo quando a heurística é admissível
- Muito mais rápido que Dijkstra ou busca em largura quando boas heurísticas estão disponíveis
- Flexível: funciona com qualquer função heurística admissível
- Bem adequado para problemas de busca de caminho com um único objetivo
- Extensa validação no mundo real em jogos, robótica e sistemas de navegação
Aplicações
- Busca de caminho em videogames: navegação de NPCs em tempo real em ambientes de jogo dinâmicos
- Planejamento de movimento de robôs: planejamento de caminho ótimo para robôs autônomos evitando obstáculos
- Navegação GPS: cálculo de rotas eficientes considerando redes rodoviárias e tráfego
- Resolução de quebra-cabeças: encontrar soluções ótimas em problemas combinatórios como o quebra-cabeça de 15 peças
- Roteamento de rede: determinação de rotas de pacotes eficientes com heurísticas de qualidade de link
- Bioinformática: alinhamento de sequências e buscas de previsão de estrutura de proteínas
Como funciona
Como funciona
Crie um conjunto aberto com o nó inicial, defina seu valor g (custo do início) como zero e calcule seu valor h usando a função heurística.
Selecione o nó com o menor valor f do conjunto aberto, calcule os valores f para seus vizinhos não visitados e adicione vizinhos promissores ao conjunto aberto.
Continue expandindo os nós até que o objetivo seja alcançado com o menor valor f, o que garante o caminho ótimo; reconstrua o caminho rastreando os ponteiros dos pais.
Erros comuns
- Usar uma heurística inadmissível que superestima os custos, levando a caminhos subótimos
- Escolher uma heurística muito simples ou não relacionada ao problema, reduzindo a eficiência da busca
- Implementação ineficiente do conjunto aberto (deve usar fila de prioridade), causando seleção lenta de nós
Perguntas frequentes
O que é uma heurística admissível e por que ela é importante?
Uma heurística admissível nunca superestima o custo verdadeiro até o objetivo. Essa propriedade garante que A* encontre o caminho ótimo. Se uma heurística superestimar, A* pode perder caminhos mais curtos e retornar soluções subótimas.
Como projetar uma boa heurística para um problema?
Boas heurísticas são baseadas no conhecimento do domínio e na estrutura do problema. Para busca de caminho baseada em grade, a distância de Manhattan ou Euclidiana funciona bem. Para problemas mais complexos, considere relaxar restrições ou usar bancos de dados de padrões para calcular heurísticas admissíveis.
Qual a diferença entre o algoritmo A* e o algoritmo de Dijkstra?
Ambos encontram caminhos ótimos, mas A* usa uma heurística para priorizar a exploração em direção ao objetivo, tornando-o muito mais rápido quando uma boa heurística está disponível. Dijkstra explora uniformemente em todas as direções e é mais seguro quando as heurísticas não são confiáveis.
A* pode garantir encontrar o caminho mais curto?
Sim, A* garante o caminho mais curto quando a heurística é admissível (nunca superestima o custo verdadeiro). Com heurísticas inadmissíveis, a otimalidade não é garantida.
Métodos relacionados
Fontes
Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107.
Abrir referência DOICopiado.Russell, S. J., & Norvig, P. (2009). Artificial Intelligence: A Modern Approach (3rd ed.). Pearson.
ISBN: 978-0-13-604259-4Copiado.