Skip to content
Voltar aos resultados

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

Tamanho da fonte

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

1

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.

2

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.

3

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

  1. 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 DOI
    Copiado.
  2. Russell, S. J., & Norvig, P. (2009). Artificial Intelligence: A Modern Approach (3rd ed.). Pearson.

    ISBN: 978-0-13-604259-4
    Copiado.