Mostrar código-fonte de Algoritmo A*

{{minidesambig|o conto de [[Arthur Charles Clarke]]|A estrela}}
{{Má tradução|1=[[:en:A* search algorithm|A* search algorithm]] (inglês)|data=setembro de 2023}}
'''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 [[Busca em largura|Breadth First Search]] (Busca em Largura) 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 ==
Sejam
 '''Q''' = conjunto de nós a serem pesquisados;
 '''S''' = o estado inicial da busca

Faça:

#Inicialize '''Q''' com o nó de busca '''(S)''' como única entrada;
#Se '''Q''' está vazio, interrompa. Se não, escolha o melhor elemento de '''Q''';
#Se o estado '''(n)''' é um objetivo, retorne '''n''';
#(De outro modo) Remova '''n''' de '''Q''';
#Encontre os descendentes do estado '''(n)''' que não estão em visitados e crie todas as extensões de '''n''' para cada descendente;
#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.

== História ==
[[Ficheiro:SRI_Shakey_with_callouts.jpg|direita|miniaturadaimagem| Trata-se de um algoritmo inventado por pesquisadores que trabalham no ''pathfinding'' do Robô "Shakey the Robot"]]
O A* foi criado como parte do [[Shakey|projeto Shakey]], que tinha como objetivo construir um robô móvel que pudesse planejar suas próprias ações. Nils Nilsson propôs originalmente o uso do algoritmo Graph Traverser<ref>{{Citar periódico |título=Experiments with the Graph Traverser program |data=1966-09-20 |periódico=Proc. R. Soc. Lond. A |número=1437 |ultimo=Doran |primeiro=J. E. |ultimo2=Michie |primeiro2=D. |paginas=235–259 |bibcode=1966RSPSA.294..235D |doi=10.1098/rspa.1966.0205 |volume=294}}</ref> para encontrar caminhos para o Shakey percorrer.<ref name=":0">{{Citar livro|url=https://ai.stanford.edu/~nilsson/QAI/qai.pdf|título=The Quest for Artificial Intelligence|ultimo=Nilsson|primeiro=Nils J.|data=2009-10-30|editora=Cambridge University Press|localização=Cambridge|língua=en|isbn=9780521122931}}</ref> O Graph Traverser é guiado por uma função heurística {{Math|''h''(''n'')}}, a distância estimada do nó {{Mvar|n}} ao nó objetivo: ele ignora totalmente {{Math|''g''(''n'')}}, a distância do nó inicial até {{Mvar|n}} . Bertram Raphael sugeriu usar a soma {{Math|''g''(''n'') + ''h''(''n'')}} .<ref name=":0" /> Peter Hart inventou os conceitos que hoje chamamos de [[Heurística admissível|admissibilidade]] e [[Heurística consistente|consistência]] de funções heurísticas. O A* foi originalmente projetado para encontrar caminhos de menor custo quando o custo de um caminho é a soma de seus custos, mas foi demonstrado que também pode ser usado para encontrar caminhos ótimos para qualquer problema que satisfaça as condições de uma álgebra de custos.<ref>{{Citar periódico |url=http://www.aaai.org/Papers/AAAI/2005/AAAI05-216.pdf |título=Cost-Algebraic Heuristic Search |data=2005 |periódico=Proceedings of the Twentieth National Conference on Artificial Intelligence (AAAI) |ultimo=Edelkamp |primeiro=Stefan |ultimo2=Jabbar |primeiro2=Shahid |paginas=1362–7 |isbn=978-1-57735-236-5 |ultimo3=Lluch-Lafuente |primeiro3=Alberto}}</ref>

O artigo científico original, de 1968,<ref name="nilsson">{{Citar periódico |título=A Formal Basis for the Heuristic Determination of Minimum Cost Paths |periódico=IEEE Transactions on Systems Science and Cybernetics |número=2 |ultimo=Hart |primeiro=P. E. |ultimo2=Nilsson |primeiro2=N.J. |ano=1968 |paginas=100–7 |doi=10.1109/TSSC.1968.300136 |ultimo3=Raphael |primeiro3=B. |volume=4}}
</ref> continha um teorema afirmando que nenhum algoritmo semelhante ao A* {{Nre|“A*-like” means the algorithm searches by extending paths originating at the start node one edge at a time, just as A* does. This excludes, for example, algorithms that search backward from the goal or in both directions simultaneously. In addition, the algorithms covered by this theorem must be admissible, and “not more informed” than A*.}} poderia expandir menos nós do que A* se a função heurística fosse consistente e a regra de desempate de A* fosse escolhida adequadamente. Uma "correção" foi publicada alguns anos depois<ref>{{Citar periódico |url=https://www.ics.uci.edu/~dechter/publications/r0.pdf |título=Correction to 'A Formal Basis for the Heuristic Determination of Minimum Cost Paths' |data=1972-12-01 |periódico=ACM SIGART Bulletin |número=37 |ultimo=Hart |primeiro=Peter E. |ultimo2=Nilsson |primeiro2=Nils J. |paginas=28–29 |doi=10.1145/1056777.1056779 |ultimo3=Raphael |primeiro3=Bertram}}</ref> alegando que a consistência não era necessária, mas esta afirmação foi refutada no estudo definitivo de Dechter e Pearl sobre a otimalidade do A* (agora chamada de eficiência ótima), que deu um exemplo do A* com uma heurística que era admissível, mas não consistente, expandindo arbitrariamente mais nós do que um algoritmo alternativo do tipo A*.<ref name=":1">{{Citar periódico |título=Generalized best-first search strategies and the optimality of A* |periódico=[[Journal of the ACM]] |número=3 |ultimo=Dechter |primeiro=Rina |ultimo2=Judea Pearl |ano=1985 |paginas=505–536 |doi=10.1145/3828.3830 |volume=32}}
</ref>

== Descrição ==
[[Ficheiro:Astarpathfinding.gif|miniaturadaimagem| O algoritmo de localização de caminhos A* navegando em um labirinto gerado aleatoriamente]]
[[Ficheiro:A_Star_Algorithm.webm|miniaturadaimagem| Ilustração da pesquisa A* para encontrar um caminho entre dois pontos de um gráfico. Da esquerda para a direita, uma heurística que prefere pontos mais próximos do objetivo é cada vez mais utilizada]]
O A* é um [[Algoritmo de busca|algoritmo de busca informado]], ou [[Best-first Search|''best-first search'']], o que significa que é formulado em termos de [[Lista de termos técnicos relacionados à teoria dos grafos|grafos ponderados]]: partindo de um [[Vértice (teoria dos grafos)|nó]] inicial específico de um grafo,  visa encontrar um caminho para o nó objetivo determinado com o menor custo (menor distância percorrida, menor tempo, etc.). Ele fá-lo mantendo uma [[Árvore (estrutura de dados)|árvore]] de caminhos originados no nó inicial e estendendo esses caminhos uma aresta de cada vez até que seu critério de término seja satisfeito.

A cada iteração do seu loop principal, o A* precisa determinar quais dos seus caminhos estender. Isso é feito com base no custo do caminho e em uma estimativa do custo necessário para estender o caminho até a meta. Especificamente, o A* seleciona o caminho que minimiza

: <math>f(n) = g(n) + h(n)</math>

onde {{Mvar|n}} é o próximo nó no caminho, {{Math|''g''(''n'')}} é o custo do caminho do nó inicial até {{Mvar|n}}, e {{Math|''h''(''n'')}} é uma função [[heurística]] que estima o custo do caminho mais barato de {{Mvar|n}} até o objetivo. A* termina quando o caminho que ele escolhe estender for um caminho do início ao objetivo ou se não houver caminhos elegíveis para serem estendidos. A função heurística é específica do problema. Se a função heurística for [[Heurística admissível|admissível]] – o que significa que ela nunca superestima o custo real para atingir a meta – é garantido que o A* retornará um caminho de menor custo do início ao objetivo.

Tipicamente, as implementações deste algoritmo usam uma [[fila de prioridade]] para realizar a seleção repetida de nós de custo mínimo (estimado) para expansão. Esta fila de prioridade é conhecida como ''[[Open set (Computer science)|conjunto aberto]]'', ''[[Fringe (Computer science)|franja]]'' ou fronteira. A cada etapa do algoritmo, o nó com o menor valor {{Math|''f''(''x'')}} é removido da fila, os valores de {{Mvar|f}} e {{Mvar|g}} de seus vizinhos são atualizados de acordo e esses vizinhos são adicionados à fila. O algoritmo continua até que um nó removido (portanto, o nó com o valor {{Mvar|f}} mais baixo de todos os nós periféricos) seja um nó de meta. {{Nre|Goal nodes may be passed over multiple times if there remain other nodes with lower {{mvar|f}} values, as they may lead to a shorter path to a goal.}} O valor {{Mvar|f}} dessa meta é então também o custo do caminho mais curto, uma vez que {{Mvar|h}} na meta é zero em uma heurística admissível.

O algoritmo descrito até agora nos dá apenas o comprimento do caminho mais curto. Para encontrar a sequência real de etapas, o algoritmo pode ser facilmente revisado para que cada nó no caminho acompanhe seu antecessor. Depois que esse algoritmo for executado, o nó final apontará para seu antecessor e assim por diante, até que o predecessor de algum nó seja o nó inicial.

Por exemplo, ao procurar a rota mais curta em um mapa, {{Math|''h''(''x'')}} pode representar a [[Distância euclidiana|distância em linha reta]] até o objetivo, uma vez que é fisicamente a menor distância possível entre dois pontos quaisquer. Para um mapa de grade de um jogo de vídeo, usar a [[Geometria do táxi|distância de Manhattan]] ou a [[distância de Chebyshev]] torna-se melhor dependendo do conjunto de movimentos disponíveis (4 ou 8 direções).

Se a [[heurística]] {{Mvar|h}} satisfazer a condição adicional {{Math|''h''(''x'') ≤ ''d''(''x'', ''y'') + ''h''(''y'')}} para cada aresta {{Math|(''x'', ''y'')}} do gráfico (onde {{Mvar|d}} denota o comprimento dessa aresta), então {{Mvar|h}} é chamado [[Consistência|monótono, ou consistente]] . Com uma heurística consistente, o A* tem a garantia de encontrar um caminho ideal sem processar nenhum nó mais de uma vez e o A* é equivalente a executar [[Algoritmo de Dijkstra|o algoritmo de Dijkstra]] com o [[custo reduzido]] {{Math|''d'''(''x'', ''y'') {{=}} ''d''(''x'', ''y'') + ''h''(''y'') − ''h''(''x'')}} {{Carece de fontes|data=setembro de 2023}}.

=== Pseudo-código ===
O [[pseudocódigo]] a seguir descreve o algoritmo:<syntaxhighlight lang="pascal" start="1">
function reconstruct_path(cameFrom, current)
    total_path := {current}
    while current in cameFrom.Keys:
        current := cameFrom[current]
        total_path.prepend(current)
    return total_path

// A* finds a path from start to goal.
// h is the heuristic function. h(n) estimates the cost to reach goal from node n.
function A_Star(start, goal, h)
    // The set of discovered nodes that may need to be (re-)expanded.
    // Initially, only the start node is known.
    // This is usually implemented as a min-heap or priority queue rather than a hash-set.
    openSet := {start}

    // For node n, cameFrom[n] is the node immediately preceding it on the cheapest path from the start
    // to n currently known.
    cameFrom := an empty map

    // For node n, gScore[n] is the cost of the cheapest path from start to n currently known.
    gScore := map with default value of Infinity
    gScore[start] := 0

    // For node n, fScore[n] := gScore[n] + h(n). fScore[n] represents our current best guess as to
    // how cheap a path could be from start to finish if it goes through n.
    fScore := map with default value of Infinity
    fScore[start] := h(start)

    while openSet is not empty
        // This operation can occur in O(Log(N)) time if openSet is a min-heap or a priority queue
        current := the node in openSet having the lowest fScore[] value
        if current = goal
            return reconstruct_path(cameFrom, current)

        openSet.Remove(current)
        for each neighbor of current
            // d(current,neighbor) is the weight of the edge from current to neighbor
            // tentative_gScore is the distance from start to the neighbor through current
            tentative_gScore := gScore[current] + d(current, neighbor)
            if tentative_gScore < gScore[neighbor]
                // This path to neighbor is better than any previous one. Record it!
                cameFrom[neighbor] := current
                gScore[neighbor] := tentative_gScore
                fScore[neighbor] := tentative_gScore + h(neighbor)
                if neighbor not in openSet
                    openSet.add(neighbor)

    // Open set is empty but goal was never reached
    return failure
</syntaxhighlight>'''Observação:''' Neste pseudocódigo, se um nó for alcançado por um caminho, removido do openSet e posteriormente alcançado por um caminho mais barato, ele será adicionado ao openSet novamente. Isto é essencial para garantir que o caminho retornado seja ótimo se a função heurística for [[Heurística admissível|admissível]], mas não [[Consistência|consistente]] . Se a heurística for consistente, quando um nó é removido do openSet, o caminho para ele é garantido como ideal, portanto o teste ' <code>tentative_gScore < gScore[neighbor]</code> ' sempre falhará se o nó for alcançado novamente.
[[Ficheiro:Astar_progress_animation.gif|miniaturadaimagem| Ilustração da busca A* para encontrar o caminho de um nó inicial até um nó final em um problema de planeamento de movimento [[Robótica|de robô]] . Os círculos vazios representam os nós do ''conjunto aberto'', ou seja, aqueles que restam para serem explorados, e os preenchidos estão no conjunto fechado. A cor em cada nó fechado indica a distância do objetivo: quanto mais verde, mais próximo. Pode-se ver primeiro o A* se movendo em linha reta na direção do objetivo, depois ao atingir o obstáculo, ele explora rotas alternativas através dos nós do conjunto aberto.]]

=== Exemplo ===
Um exemplo de algoritmo A* em ação onde os nós são cidades conectadas a estradas e h(x) é a distância em linha reta até o ponto alvo:

[[Ficheiro:AstarExampleEn.gif|alt=An example of A* algorithm in action (nodes are cities connected with roads, h(x) is the straight-line distance to the target point) Green: Start, Blue: Target, Orange: Visited|Um exemplo do algoritmo A* em ação (nós são cidades conectadas a estradas, h(x) é a distância em linha reta até o ponto alvo) Verde: Início, Azul: Alvo, Laranja: Visitado]]

'''Legenda:''' verde: início; azul: meta; laranja: visitado

O algoritmo A* também tem aplicações no mundo real. Neste exemplo, as arestas são ferrovias e h(x) é a [[Ortodromia|distância do grande círculo]] (a distância mais curta possível em uma esfera) até o alvo. O algoritmo está procurando um caminho entre Washington, DC e Los Angeles.

[[Ficheiro:A*_Search_Example_on_North_American_Freight_Train_Network.gif|alt=The A* algorithm finding a path of railroads between Washington, D.C. and Los Angeles.|O algoritmo A* encontra um caminho de ferrovia entre Washington, DC e Los Angeles]]

=== Detalhes de implementação ===
Há uma série de otimizações simples ou detalhes de implementação que podem afetar significativamente o desempenho de uma implementação A*. O primeiro detalhe a ser observado é que a forma como a fila de prioridade trata os empates pode ter um efeito significativo no desempenho em algumas situações. Se os empates forem quebrados e a fila se comportar de maneira [[Pilha (informática)|LIFO]], A* se comportará como [[Busca em profundidade|uma busca em profundidade]] entre caminhos de custos iguais (evitando explorar mais de uma solução igualmente ótima).

Quando um caminho é requerido no final da busca, é comum manter com cada nó uma referência ao pai daquele nó. Ao final da busca, essas referências podem ser utilizadas para recuperar o caminho ótimo. Se estas referências forem mantidas então pode ser importante que o mesmo nó não apareça na fila de prioridade mais de uma vez (cada entrada corresponde a um caminho diferente para o nó, e cada uma com um custo diferente). Uma abordagem padrão aqui é verificar se um nó prestes a ser adicionado já aparece na fila de prioridade. Se isso acontecer, então a prioridade e os ponteiros pai serão alterados para corresponder ao caminho de custo mais baixo. Uma fila de prioridade baseada em heap binário padrão não suporta diretamente a operação de busca por um de seus elementos, mas pode ser aumentada com uma [[Tabela de dispersão|tabela hash]] que mapeia os elementos para sua posição no heap, permitindo que esta operação de diminuição de prioridade seja executada em tempo logarítmico. Alternativamente, um heap de Fibonacci pode realizar as mesmas operações de prioridade decrescente em [[Análise amortizada|tempo amortizado]] constante.

=== Casos especiais ===
O [[algoritmo de Dijkstra]], como outro exemplo de algoritmo de busca de custo uniforme, pode ser visto como um caso especial de A* onde&lt;math xmlns="http://www.w3.org/1998/Math/MathML"&gt;<semantics><mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> {{Tmath|1=h(x) = 0}}</mi><mo stretchy="false"> {{Tmath|1=h(x) = 0}}</mo><mi> {{Tmath|1=h(x) = 0}}</mi><mo stretchy="false"> {{Tmath|1=h(x) = 0}}</mo><mo> {{Tmath|1=h(x) = 0}}</mo><mn> {{Tmath|1=h(x) = 0}}</mn></mstyle></mrow><annotation encoding="application/x-tex"> </annotation></semantics>&lt;/math&gt;{{Tmath|1=h(x) = 0}} para todo ''x'' .<ref name="geospatial">{{Citation|título=Geospatial Analysis: A Comprehensive Guide to Principles, Techniques and Software Tools|primeiro1=Michael John|último=De Smith|primeiro2=Michael F.|último2=Goodchild|primeiro3=Paul|último3=Longley|publicado=Troubadour Publishing Ltd|ano=2007|isbn=9781905886609|página=344|url=https://books.google.com/books?id=SULMdT8qPwEC&pg=PA344}}.</ref><ref name="pythalgs">{{Citation|título=Python Algorithms: Mastering Basic Algorithms in the Python Language|primeiro1=Magnus Lie|último=Hetland|publicado=Apress|ano=2010|isbn=9781430232377|página=214|url=https://books.google.com/books?id=9_AXCmGDiz8C&pg=PA214}}.</ref> [[Busca em profundidade|A busca geral em profundidade]] pode ser implementada usando A* considerando que existe um contador global ''C'' inicializado com um valor muito grande. Cada vez que processamos um nó, atribuímos ''C'' a todos os seus vizinhos recém-descobertos. Após cada atribuição, diminuímos o contador ''C'' em um. Assim, quanto mais cedo um nó for descoberto, maior será seu valor {{Tmath|h(x)}}. Tanto o algoritmo de Dijkstra quanto a busca em profundidade podem ser implementados de forma mais eficiente sem incluir um valor {{Tmath|h(x)}} em cada nó.

== Propriedades ==

=== Término e integralidade ===
Em grafos finitos com pesos de aresta não negativos, é garantido que o A* termine e seja ''completo'', ou seja, que encontre sempre uma solução (um caminho do início à meta), se existir. Em gráficos infinitos com um fator de ramificação finito e custos de borda limitados a zero (<math display="inline">d(x,y)>\varepsilon>0</math> para alguns <math>\varepsilon</math> fixos), é garantido que A* terminará apenas se existir uma solução.<ref name=":2">{{Citar livro|título=Artificial intelligence a modern approach|ultimo=Russell|primeiro=Stuart J.|data=2018|editora=Pearson|localização=Boston|isbn=978-0134610993|oclc=1021874142|edição=4th}}</ref>

=== Admissibilidade ===
Um algoritmo de busca é considerado ''admissível'' se for garantido que ele retornará uma solução ótima. Se a função heurística usada por A* for admissível, então A* é admissível. Uma “prova” intuitiva disso é a seguinte:

Quando A* termina sua busca, ele encontrou um caminho do início ao objetivo cujo custo real é menor que o custo estimado de qualquer caminho do início ao objetivo através de qualquer nó aberto (o valor {{Tmath|f}} do nó). Quando a heurística é admissível, essas estimativas são otimistas (não exatamente – veja o próximo parágrafo), então o A* pode ignorar com segurança esses nós porque eles não podem levar a uma solução mais barata do que aquela que já possui. Em outras palavras, A* nunca ignorará a possibilidade de um caminho de custo mais baixo do início ao objetivo e, portanto, continuará a procurar até que tais possibilidades não existam.

A prova real é um pouco mais complicada porque os valores&lt;math xmlns="http://www.w3.org/1998/Math/MathML"&gt;<semantics><mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> {{Tmath|f}}</mi></mstyle></mrow><annotation encoding="application/x-tex"> </annotation></semantics>&lt;/math&gt;{{Tmath|f}} não são garantidos que sejam os valores dos nós abertos sejam otimistas, mesmo que a heurística seja admissível. Isso ocorre porque os valores &lt;math xmlns="http://www.w3.org/1998/Math/MathML"&gt;<semantics><mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> {{Tmath|g}}</mi></mstyle></mrow><annotation encoding="application/x-tex"> </annotation></semantics>&lt;/math&gt;{{Tmath|g}} de nós abertos não são garantidos como óptimos, então a soma&lt;math xmlns="http://www.w3.org/1998/Math/MathML"&gt;<semantics><mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><mi> {{Tmath|g+h}}</mi><mo> {{Tmath|g+h}}</mo><mi> {{Tmath|g+h}}</mi></mstyle></mrow><annotation encoding="application/x-tex"> </annotation></semantics>&lt;/math&gt;{{Tmath|g+h}}não é garantido que seja otimista.

=== Otimização e consistência ===
O algoritmo A é otimamente eficiente em relação a um conjunto de algoritmos alternativos '''Alts''' em um conjunto de problemas '''P''' se para cada problema P em '''P''' e cada algoritmo A′ em '''Alts''', o conjunto de nós expandidos por A na resolução de P é um subconjunto (possivelmente igual) do conjunto de nós expandidos por A′ na resolução de P. O estudo definitivo da eficiência ótima de A* deve-se a Rina Dechter e Judea Pearl.<ref name=":1" /> Elas consideraram uma variedade de definições de '''Alts''' e '''P''' em combinação com a heurística de A* sendo meramente admissível ou sendo [[Consistência|consistente]] e admissível. O resultado positivo mais interessante que eles provaram é que A*, com uma heurística consistente, é otimamente eficiente em relação a todos os algoritmos de busca admissíveis do tipo A* em todos os problemas de busca "não patológicos". De grosso modo, a sua noção de problema não patológico é o que hoje entendemos por “até ao desempate”. Este resultado não é válido se a heurística de A* for admissível, mas não consistente. Nesse caso, Dechter e Pearl mostraram que existem algoritmos admissíveis do tipo A* que podem expandir arbitrariamente menos nós do que A* em alguns problemas não patológicos.

A eficiência óptima diz respeito ao ''conjunto'' de nós expandidos, não ao ''número'' de expansões de nós (o número de iterações do loop principal de A*). Quando a heurística utilizada é admissível, mas não consistente, é possível que um nó seja expandido por A* muitas vezes, um número exponencial de vezes no pior caso.<ref name="Martelli">{{Citar periódico |título=On the Complexity of Admissible Search Algorithms |periódico=[[Artificial Intelligence]] |número=1 |ultimo=Martelli |primeiro=Alberto |ano=1977 |paginas=1–13 |doi=10.1016/0004-3702(77)90002-9 |volume=8}}
</ref> Nessas circunstâncias, o algoritmo de Dijkstra poderia superar A* por uma grande margem. No entanto, pesquisas mais recentes descobriram que este caso patológico só ocorre em certas situações inventadas onde o peso da aresta do grafo de busca é exponencial no tamanho do grafo e que certas heurísticas inconsistentes (mas admissíveis) podem levar a um número reduzido de expansões de nós em pesquisas A*.<ref name="Felner2011">{{Citar periódico |título=Inconsistent heuristics in theory and practice |periódico=[[Artificial Intelligence]] |número=9–10 |ultimo=Felner |primeiro=Ariel |ultimo2=Uzi Zahavi |ano=2011 |paginas=1570–1603 |doi=10.1016/j.artint.2011.02.001 |volume=175 |doi-access=free}}</ref><ref name="Zhang2009">{{Citar conferência |ultimo=Zhang |primeiro=Zhifu |ultimo2=N. R. Sturtevant |url=https://www.aaai.org/ocs/index.php/IJCAI/IJCAI-09/paper/viewPDFInterstitial/413/726 |titulo=Using Inconsistent Heuristics on A* Search |data=2009 |paginas=634–639 |conferencia=Twenty-First International Joint Conference on Artificial Intelligence}}</ref>

== Relaxamento limitado ==
[[Ficheiro:Weighted_A_star_with_eps_5.gif|miniaturadaimagem| Uma pesquisa A* que usa uma heurística que é 5,0(=ε) vezes uma heurística consistente e obtém um caminho abaixo do ideal]]
Embora o critério de admissibilidade garanta um caminho de solução óptimo, também significa que A* deve examinar todos os caminhos igualmente meritórios para encontrar o caminho óptimo. Para calcular caminhos mais curtos aproximados, é possível acelerar a busca em detrimento da otimalidade, relaxando o critério de admissibilidade. Muitas vezes queremos limitar esta relaxação, para que possamos garantir que o caminho da solução não é pior que (1 + ''ε'' ) vezes o caminho da solução ideal. Esta nova garantia é referida como ''ε-''admissível.

Existem vários algoritmos ''ε-''admissíveis:

* Ponderação A*/Ponderação Estática.<ref>{{Citar periódico |título=First results on the effect of error in heuristic search |periódico=Machine Intelligence 5 |publicado=Edinburgh University Press |ultimo=Pohl |primeiro=Ira |ano=1970 |paginas=219–236 |isbn=978-0-85224-176-9 |oclc=1067280266}}</ref> Se ''<sub>ha</sub>'' ( ''n'' ) é uma função heurística admissível, na versão ponderada da busca A* utiliza-se {{Math|1=''h<sub>w</sub>''(''n'') = ''ε h<sub>a</sub>''(''n'')}}, {{Math|''ε'' > 1}} como função heurística, e realiza-se a busca A* como de costume (o que eventualmente acontece mais rápido do que usar ''h<sub>a,</sub>'' pois menos nós são expandidos). O caminho, portanto, encontrado pelo algoritmo de busca pode ter um custo no máximo ''ε'' vezes maior que o caminho de menor custo no gráfico.<ref name="pearl84">{{Citar livro|url=https://archive.org/details/heuristicsintell00pear|título=Heuristics: Intelligent Search Strategies for Computer Problem Solving|ultimo=Pearl|primeiro=Judea|editora=Addison-Wesley|ano=1984|isbn=978-0-201-05594-8}}</ref>
* A Ponderação Dinâmica<ref>{{Citar conferência |ultimo=Pohl |primeiro=Ira |url=https://www.cs.auckland.ac.nz/courses/compsci709s2c/resources/Mike.d/Pohl1973WeightedAStar.pdf |titulo=The avoidance of (relative) catastrophe, heuristic competence, genuine dynamic weighting and computational issues in heuristic problem solving |data=agosto de 1973 |paginas=11–17 |volume=3}}</ref> usa a função de custo {{tmath|1=f(n) = g(n) + (1 + \varepsilon w(n))h(n)}}, onde <math>w(n) = \begin{cases} 1 - \frac{d(n)}{N} & d(n) \le N \\ 0 & \text{em caso contrário} \end{cases}</math>, e onde {{Tmath|d(n)}} é a profundidade da pesquisa e ''N'' é o comprimento previsto do caminho da solução.
* A ponderação dinâmica amostrada<ref>{{Citar conferência |ultimo=Köll |primeiro=Andreas |ultimo2=Hermann Kaindl |url=https://dl.acm.org/doi/abs/10.5555/145448.145484 |titulo=A new approach to dynamic weighting |data=agosto de 1992 |publicado=Wiley |paginas=16–17 |isbn=978-0-471-93608-4}}</ref> usa amostragem de nós para melhor estimar e reduzir o erro heurístico.
* <math>A^*_\varepsilon</math> .<ref>{{Citar periódico |título=Studies in semi-admissible heuristics |periódico=IEEE Transactions on Pattern Analysis and Machine Intelligence |número=4 |ultimo=Pearl |primeiro=Judea |ultimo2=Jin H. Kim |ano=1982 |paginas=392–399 |doi=10.1109/TPAMI.1982.4767270 |pmid=21869053 |volume=4}}</ref> usa duas funções heurísticas. A primeira é a lista FOCAL, que é usada para selecionar os nós candidatos, e a segunda ''h <sub>F</sub>'' é usada para selecionar o nó mais promissor da lista FOCAL.
* ''A<sub>ε</sub>''<ref>{{Citar conferência |ultimo=Ghallab |primeiro=Malik |ultimo2=Dennis Allard |url=http://ijcai.org/Past%20Proceedings/IJCAI-83-VOL-2/PDF/048.pdf |titulo=''A<sub>ε</sub>'' – an efficient near admissible heuristic search algorithm |data=agosto de 1983 |paginas=789–791 |arquivourl=https://web.archive.org/web/20140806200328/http://ijcai.org/Past%20Proceedings/IJCAI-83-VOL-2/PDF/048.pdf |arquivodata=2014-08-06 |volume=2}}</ref> seleciona nós com a função {{Tmath|A f(n) + B h_F(n)}}, onde ''A'' e ''B'' são constantes. Se nenhum nó puder ser selecionado, o algoritmo retrocederá com a função {{Tmath|C f(n) + D h_F(n)}}, onde ''C'' e ''D'' são constantes.
* AlphA* <ref>{{Citar relatório|primeiro=Bjørn|ultimo=Reese|titulo=AlphA*: An ''ε''-admissible heuristic search algorithm|ano=1999|publicado=Institute for Production Technology, University of Southern Denmark|url=http://home1.stofanet.dk/breese/astaralpha-submitted.pdf.gz|arquivourl=https://web.archive.org/web/20160131214618/http://home1.stofanet.dk/breese/astaralpha-submitted.pdf.gz|arquivodata=2016-01-31|urlmorta=dead}}</ref> tenta promover a exploração em profundidade, preferindo nós recentemente expandidos. AlphA* usa a função de custo <math>f_\alpha(n) = (1 + w_\alpha(n)) f(n)</math>, onde <math>w_\alpha(n) = \begin{cases} \lambda & g(\pi(n)) \le g(\tilde{n}) \\ \Lambda & \text{em caso contrário} \end{cases}</math>, onde ''λ'' e ''Λ'' são constantes com <math>\lambda \le \Lambda</math>, ''π'' ( ''n'' ) é o pai de ''n'' e ''ñ'' é o nó expandido mais recentemente.

== Complexidade ==
A [[Complexidade computacional|complexidade]] de A* depende da heurística. No pior caso de um espaço de busca ilimitado, o número de nós expandidos é [[Complexidade de Tempo|exponencial]] na profundidade da solução (o caminho mais curto) {{Mvar|d}} : {{Math|''O''(''b<sup>d</sup>'')}}, onde {{Mvar|b}} é o fator de ramificação (o número médio de sucessores por estado ).  Isso pressupõe que existe um estado objetivo e é [[Atingibilidade (teoria dos grafos)|alcançável]] a partir do estado inicial; se não for, e o espaço de estados for infinito, o algoritmo não terminará.

A função heurística tem um efeito importante no desempenho prático da busca A*, uma vez que uma boa heurística permite que A* remova muitos dos nós {{Mvar|b<sup>d</sup>}} que uma busca desinformada expandiria. Sua qualidade pode ser expressa em termos do fator de ramificação ''efetivo'' {{Math|''b''*}}, que pode ser determinado empiricamente para uma instância do problema medindo o número de nós gerados pela expansão, {{Mvar|N}}, e a profundidade da solução, resolvendo então

: <math>N + 1 = 1 + b^* + (b^*)^2 + \dots + (b^*)^d.</math>

Boas heurísticas são aquelas com baixo fator de ramificação efetivo (sendo o ideal {{Math|''b''* {{=}} 1}} ).

A complexidade do tempo é [[Complexidade de Tempo|polinomial]] quando o espaço de busca é uma árvore, existe um único estado objetivo e a função heurística ''h'' atende à seguinte condição:

: <math>|h(x) - h^*(x)| = O(\log h^*(x))</math>

onde {{Math|''h''<sup>*</sup>}} é a heurística ótima, o custo exato para ir de {{Mvar|x}} até a meta. Em outras palavras, o erro de {{Mvar|h}} não crescerá mais rápido que o [[logaritmo]] da “heurística perfeita” {{Math|''h''<sup>*</sup>}} que retorna a distância real de {{Mvar|x}} até o objetivo.<ref name="pearl84" />

A [[complexidade espacial]] de A* é aproximadamente a mesma de todos os outros algoritmos de busca de grafos, pois mantém todos os nós gerados na memória.<ref name=":2">{{Citar livro|título=Artificial intelligence a modern approach|ultimo=Russell|primeiro=Stuart J.|data=2018|editora=Pearson|localização=Boston|isbn=978-0134610993|oclc=1021874142|edição=4th}}</ref> Na prática, esta acaba sendo a maior desvantagem da pesquisa A*, levando ao desenvolvimento de pesquisas heurísticas limitadas por memória, como A* por aprofundamento interativo, A* limitado por memória e SMA* .

== Aplicações ==
A* é frequentemente usado para o problema comum de localização de caminhos em aplicações como jogos de vídeo, mas foi originalmente projetado como um algoritmo geral de travessia de gráfico.<ref name="nilsson">{{Citar periódico |título=A Formal Basis for the Heuristic Determination of Minimum Cost Paths |periódico=IEEE Transactions on Systems Science and Cybernetics |número=2 |ultimo=Hart |primeiro=P. E. |ultimo2=Nilsson |primeiro2=N.J. |ano=1968 |paginas=100–7 |doi=10.1109/TSSC.1968.300136 |ultimo3=Raphael |primeiro3=B. |volume=4}}
</ref> Encontra aplicações em diversos problemas, incluindo o problema de [[Análise sintática (computação)|análise sintática]] usando [[Gramática livre de contexto estocástica|gramáticas estocásticas]] em [[Processamento de linguagem natural|PNL]] .<ref>{{Citar conferência |ultimo=Klein |primeiro=Dan |ultimo2=Manning |primeiro2=Christopher D. |url=https://people.eecs.berkeley.edu/~klein/papers/pcfg-astar.pdf |titulo=A* parsing: fast exact Viterbi parse selection |ano=2003 |paginas=119–126 |doi=10.3115/1073445.1073461}}</ref> Outros casos incluem uma busca informativa com aprendizagem online.<ref name="WPCleanerAuto1">{{Citar periódico |url=http://www.eng.tau.ac.il/~bengal/GTA.pdf |título=A Group-Testing Algorithm with Online Informational Learning |acessodata=2016-02-12 |periódico=IIE Transactions |número=2 |ultimo=Kagan E. |ultimo2=Ben-Gal I. |ano=2014 |paginas=164–184 |doi=10.1080/0740817X.2013.803639 |arquivourl=https://web.archive.org/web/20161105103321/http://www.eng.tau.ac.il/~bengal/GTA.pdf |arquivodata=2016-11-05 |volume=46}}</ref>

== Relações com outros algoritmos ==
O que diferencia A* de um algoritmo [[Algoritmo guloso|ganancioso]] de busca do melhor primeiro é que ele leva em consideração o custo/distância já percorrida, {{Math|''g''(''n'')}} .

Algumas variantes comuns do [[algoritmo de Dijkstra]] podem ser vistas como um caso especial de A* onde a heurística <math>h(n) = 0</math> para todos os nós;<ref name="geospatial" /><ref name="pythalgs" /> por sua vez, tanto Dijkstra quanto A* são casos especiais de [[programação dinâmica]] .<ref>{{Citar conferência |ultimo=Ferguson |primeiro=Dave |ultimo2=Likhachev |primeiro2=Maxim |url=https://www.cs.cmu.edu/afs/cs.cmu.edu/Web/People/maxim/files/hsplanguide_icaps05ws.pdf |titulo=A Guide to Heuristic-based Path Planning |ano=2005 |paginas=9–18 |ultimo3=Stentz |primeiro3=Anthony}}</ref> O próprio A* é um caso especial de generalização do [[Ramificar e limitar|''branch and bound'']].<ref>{{Citar periódico |url=https://www.cs.umd.edu/~nau/papers/nau1984general.pdf |título=General branch and bound, and its relation to A∗ and AO∗ |periódico=Artificial Intelligence |número=1 |ultimo=Nau |primeiro=Dana S. |ultimo2=Kumar |primeiro2=Vipin |ano=1984 |paginas=29–58 |doi=10.1016/0004-3702(84)90004-3 |ultimo3=Kanal |primeiro3=Laveen |volume=23}}</ref>

O A* é semelhante à busca por feixe, exceto que a busca por feixe mantém um limite no número de caminhos que deve explorar.<ref>{{Citar web|url=http://theory.stanford.edu/~amitp/GameProgramming/Variations.html|titulo=Variants of A*|acessodata=2023-06-09|website=theory.stanford.edu}}</ref>

== Variantes ==

* Anytime A*<ref>{{Citar periódico |url=https://www.jair.org/index.php/jair/article/view/10489 |título=Anytime Heuristic Search |data=2007 |periódico=Journal of Artificial Intelligence Research |número= |ultimo=Hansen |primeiro=Eric A. |ultimo2=Zhou |primeiro2=Rong |paginas=267–297 |doi=10.1613/jair.2096 |volume=28 |doi-access=free}}</ref>
* Block A*
* D*
* Field D*
* Fringe
* Fringe Saving A* (FSA*)
* Generalized Adaptive A* (GAA*)
* Incremental heuristic search
* Reduced A*<ref> {{Citar periódico |url=https://www.cambridge.org/core/journals/robotica/article/abs/investigating-reduced-path-planning-strategy-for-differential-wheeled-mobile-robot/6EDFFC11CEF00D0E010C0D149FE9C811 |título=Investigating Reduced Path Planning Strategy for Differential Wheeled Mobile Robot |data=2019-05-14 |periódico=Robotica |número=2 |ultimo=Fareh |primeiro=Raouf |ultimo2=Baziyad |primeiro2=Mohammed |paginas=235–255 |lingua=en |doi=10.1017/S0263574719000572 |issn=0263-5747 |ultimo3=Rahman |primeiro3=Mohammad H. |ultimo4=Rabie |primeiro4=Tamer |ultimo5=Bettayeb |primeiro5=Maamar |volume=38}}</ref>
* Iterative deepening A* (IDA*)
* Jump point search
* Lifelong Planning A* (LPA*)
* New Bidirectional A* (NBA*)<ref>{{Citar relatório técnico|ultimo2=Post|primeiro2=Henk|url=https://repub.eur.nl/pub/16100/ei2009-10.pdf|titulo=Yet another bidirectional algorithm for shortest paths|publicado=Econometric Institute, Erasmus University Rotterdam|id=EI 2009-10}}</ref>
* Simplified Memory bounded A* (SMA*)
* Theta*

O A* também pode ser adaptado a um algoritmo de busca bidirecional . Cuidados especiais devem ser tomados com o critério de parada.<ref>{{Citar web|ultimo=Goldberg|primeiro=Andrew V.|ultimo2=Harrelson|primeiro2=Chris|url=http://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/EPP%20shortest%20path%20algorithms.pdf|titulo=Efficient Point-to-Point Shortest Path Algorithms|publicado=[[Princeton University]]|arquivourl=https://web.archive.org/web/20220518121847/https://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/EPP%20shortest%20path%20algorithms.pdf|arquivodata=18 de maio de 2022|urlmorta=não|ultimo3=Kaplan|primeiro3=Haim|ultimo4=Werneck|primeiro4=Renato F.}}</ref>

{{Notas e referências}}

== Ligações externas ==
{{Commons|A* Algorithm}}

* {{((pt))}} [https://web.archive.org/web/20061222182121/http://policyalmanac.org/games/aStarTutorial_port.htm A* Pathfinding para Iniciantes]
* {{((pt))}} [https://web.archive.org/web/20090327141634/http://www2.dc.uel.br/~rarosa/pixel/path.html Projeto de Pesquisa de Algoritmos de Busca]
* {{((en))}} [http://theory.stanford.edu/~amitp/GameProgramming/ Amit's A* Pages -- Path finding] Texto bastante completo sobre busca de caminhos (Path finding) usando o Algoritmo A*

{{Portal3|Matemática}}

[[Categoria:Algoritmos de busca|A*]]
[[Categoria:Algoritmos de grafos|A*]]