View source for A* search algorithm

{{Infobox algorithm
|name= <!-- Defaults to article name -->
|class= [[Search algorithm]]
|image=
|caption=
|data= Graph
|time= <math>O(|E|\log|V|) = O(b^d)</math>
|best-time=
|average-time=
|space= <math>O(|V|) = O(b^d)</math>
}}

'''A*''' (pronounced "A-star") is a [[Graph traversal|graph traversal]] and [[Pathfinding|pathfinding]] [[Algorithm|algorithm]] that is used in many fields of [[Computer science|computer science]] due to its completeness, optimality, and optimal efficiency.<ref name=":2">{{Cite book|title=Artificial intelligence a modern approach |last1=Russell |first1=Stuart J.|date=2018|last2=Norvig|first2=Peter|author-link2=Peter Norvig|publisher=Pearson|isbn=978-0134610993|edition= 4th|location=Boston|oclc=1021874142}}</ref> Given a weighted graph, a source [[Vertex (graph theory)|node]] and a goal node, the algorithm finds the [[Shortest path problem|shortest path]] (with respect to the given weights) from source to goal.

One major practical drawback is its <math>O(b^d)</math> [[Space complexity|space complexity]] where {{mvar|d}} is the depth of the shallowest solution (the length of the shortest path from the source node to any given goal node)  and {{mvar|b}} is the [[Branching factor|branching factor]] (the maximum number of successors for any given state), as it stores all generated nodes in memory. Thus, in practical travel-routing systems, it is generally outperformed by algorithms that can pre-process the graph to attain better performance,<ref>{{cite book
 | last1 = Delling | first1 = D.
 | last3 = Schultes | first3 = D.
 | doi = 10.1007/978-3-642-02094-0_7
 | pages = 117–139
 | publisher = Springer
 | title= Algorithmics of Large and Complex Networks: Design, Analysis, and Simulation
 | volume = 5515
 | year = 2009| chapter = Engineering Route Planning Algorithms
 | series = Lecture Notes in Computer Science
 | isbn = 978-3-642-02093-3
 }}</ref> as well as by memory-bounded approaches; however, A* is still the best solution in many cases.<ref name="Zeng">{{cite journal
 | first = W.
 | last = Zeng
 |author2= Church, R. L.
 | title = Finding shortest paths on real road networks: the case for A*
 | journal = International Journal of Geographical Information Science
 | issue = 4
 | pages = 531–543
 | year = 2009
 | doi = 10.1080/13658810801949850 | volume = 23
 | bibcode = 2009IJGIS..23..531Z
 | s2cid = 14833639
 | url = https://zenodo.org/record/979689
 }}
</ref>

Peter Hart, Nils Nilsson and [[Biography:Bertram Raphael|Bertram Raphael]] of Stanford Research Institute (now [[Organization:SRI International|SRI International]]) first published the algorithm in 1968.<ref name="nilsson">{{cite journal
 | last1 = Hart
 | last2= Nilsson |first2=N.J.|last3= Raphael |first3=B.
 | title = A Formal Basis for the Heuristic Determination of Minimum Cost Paths
 | journal =  IEEE Transactions on Systems Science and Cybernetics
 | issue = 2
 | pages = 100–7
 | year = 1968
 | doi = 10.1109/TSSC.1968.300136
 | volume = 4
 }}
</ref> It can be seen as an extension of [[Dijkstra's algorithm]]. A* achieves better performance by using [[Heuristic (computer science)|heuristics]] to guide its search.

Compared to Dijkstra's algorithm, the A* algorithm only finds the shortest path from a specified source to a specified goal, and not the shortest-path tree from a specified source to all possible goals. This is a necessary [[Trade-off|trade-off]] for using a specific-goal-directed [[Heuristic|heuristic]]. For Dijkstra's algorithm, since the entire shortest-path tree is generated, every node is a goal, and there can be no specific-goal-directed heuristic.

==History==
[[File:SRI Shakey with callouts.jpg|thumb|right|A* was invented by researchers working on Shakey the Robot's path planning.]]
A* was created as part of [[Shakey the robot|the Shakey project]], which had the aim of building a mobile robot that could plan its own actions. Nils Nilsson originally proposed using the [[Graph traversal|Graph Traverser]] algorithm<ref>{{Cite journal|last1=Doran|first1=J. E.|last2=Michie|first2=D.|date=1966-09-20|title=Experiments with the Graph Traverser program|journal=Proc. R. Soc. Lond. A |volume=294|issue=1437|pages=235–259|doi=10.1098/rspa.1966.0205 |bibcode=1966RSPSA.294..235D|s2cid=21698093}}</ref> for Shakey's path planning.<ref name=":0">{{Cite book|url=https://ai.stanford.edu/~nilsson/QAI/qai.pdf|title=The Quest for Artificial Intelligence|last=Nilsson|first=Nils J.|date=2009-10-30|publisher=Cambridge University Press|isbn=9780521122931|location=Cambridge|language=en|quote=One of the first problems we considered was how to plan a sequence of 'way points' that Shakey could use in navigating from place to place. […] Shakey's navigation problem is a search problem, similar to ones I have mentioned earlier.}}</ref> Graph Traverser is guided by a heuristic function {{math|''h''(''n'')}}, the estimated distance from node {{mvar|n}} to the goal node: it entirely ignores {{math|''g''(''n'')}}, the distance from the start node to {{mvar|n}}. Bertram Raphael suggested using the sum, {{math|''g''(''n'') + ''h''(''n'')}}.<ref>{{Cite book|url=https://ai.stanford.edu/~nilsson/QAI/qai.pdf|title=The Quest for Artificial Intelligence|last=Nilsson|first=Nils J.|author-link=Nils John Nilsson|date=2009-10-30|publisher=Cambridge University Press|isbn=9780521122931|location=Cambridge|language=en|quote=Bertram Raphael, who was directing work on Shakey at that time, observed that a better value for the score would be the sum of the distance traveled so far from the initial position plus my heuristic estimate of how far the robot had to go.}}</ref> Peter Hart invented the concepts we now call [[Admissible heuristic|admissibility]] and consistency of heuristic functions. A* was originally designed for finding least-cost paths when the cost of a path is the sum of its  costs, but it has been shown that A* can be used to find optimal paths for any problem satisfying the conditions of a cost algebra.<ref>{{Cite conference|last1=Edelkamp|first1=Stefan|last2=Jabbar|first2=Shahid|last3=Lluch-Lafuente|first3=Alberto|date=2005|contribution=Cost-Algebraic Heuristic Search|url=http://www.aaai.org/Papers/AAAI/2005/AAAI05-216.pdf|title=Proceedings of the Twentieth National Conference on Artificial Intelligence (AAAI)|pages=1362–1367 |isbn=978-1-57735-236-5}}</ref>

The original 1968 A* paper<ref name="nilsson" /> contained a theorem stating that no A*-like algorithm{{efn|"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*.}} could expand fewer nodes than A* if the heuristic function is consistent and A*'s tie-breaking rule is suitably chosen. A "correction" was published a few years later<ref>{{Cite journal|last1=Hart|first1=Peter E.|last2=Nilsson|first2=Nils J.|last3=Raphael|first3=Bertram|date=1972-12-01|title=Correction to 'A Formal Basis for the Heuristic Determination of Minimum Cost Paths'|url=https://www.ics.uci.edu/~dechter/publications/r0.pdf|journal=ACM SIGART Bulletin|issue=37|pages=28–29|doi=10.1145/1056777.1056779|s2cid=6386648 }}</ref> claiming that consistency was not required, but this was shown to be false in 1985 in Dechter and Pearl's definitive study of A*'s optimality (now called optimal efficiency), which gave an example of A* with a heuristic that was admissible but not consistent expanding arbitrarily more nodes than an alternative A*-like algorithm.<ref name=":1" />

==Description==

[[File:Astarpathfinding.gif|thumb|A* pathfinding algorithm navigating around a randomly-generated maze]]
[[File:A Star Algorithm.webm|thumb|Illustration of A* search for finding a path between two points on a graph. From left to right, a heuristic that prefers points closer to the goal is used increasingly. ]]

A* is an informed search algorithm, or a [[Best-first search|best-first search]], meaning that it is formulated in terms of weighted graphs: starting from a specific starting node of a graph, it aims to find a path to the given goal node having the smallest cost (least distance travelled, shortest time, etc.).  It does this by maintaining a [[Tree (data structure)|tree]] of paths originating at the start node and extending those paths one edge at a time until the goal node is reached.

At each iteration of its main loop, A* needs to determine which of its paths to extend. It does so based on the cost of the path and an estimate of the cost required to extend the path all the way to the goal. Specifically, A* selects the path that minimizes

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

where {{mvar|n}} is the next node on the path, {{math|''g''(''n'')}} is the cost of the path from the start node to {{mvar|n}}, and {{math|''h''(''n'')}} is a [[Heuristic|heuristic]] function that estimates the cost of the cheapest path from {{mvar|n}} to the goal. The heuristic function is problem-specific. If the heuristic function is [[Admissible heuristic|admissible]] – meaning that it never overestimates the actual cost to get to the goal – A* is guaranteed to return a least-cost path from start to goal.

Typical implementations of A* use a [[Priority queue|priority queue]] to perform the repeated selection of minimum (estimated) cost nodes to expand. This priority queue is known as the ''open set'', ''fringe'' or ''frontier''. At each step of the algorithm, the node with the lowest {{math|''f''(''x'')}} value is removed from the queue, the {{mvar|f}} and {{mvar|g}} values of its neighbors are updated accordingly, and these neighbors are added to the queue. The algorithm continues until a removed node (thus the node with the lowest {{mvar|f}} value out of all fringe nodes) is a goal node.{{efn|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.}} The {{mvar|f}} value of that goal is then also the cost of the shortest path, since {{mvar|h}} at the goal is zero in an admissible heuristic.

The algorithm described so far only gives the length of the shortest path. To find the actual sequence of steps, the algorithm can be easily revised so that each node on the path keeps track of its predecessor. After this algorithm is run, the ending node will point to its predecessor, and so on, until some node's predecessor is the start node.

As an example, when searching for the shortest route on a map, {{math|''h''(''x'')}} might represent the [[Euclidean distance|straight-line distance]] to the goal, since that is physically the smallest possible distance between any two points. For a grid map from a video game, using the Taxicab distance or the [[Chebyshev distance]] becomes better depending on the set of movements available (4-way or 8-way).

If the heuristic {{mvar|h}} satisfies the additional condition {{math|''h''(''x'') ≤ ''d''(''x'', ''y'') + ''h''(''y'')}} for every edge {{math|(''x'', ''y'')}} of the graph (where {{mvar|d}} denotes the length of that edge), then {{mvar|h}} is called monotone, or consistent. With a consistent heuristic, A* is guaranteed to find an optimal path without processing any node more than once and A* is equivalent to running [[Dijkstra's algorithm]] with the [[Reduced cost|reduced cost]] {{math|''d'''(''x'', ''y'') {{=}} ''d''(''x'', ''y'') + ''h''(''y'') − ''h''(''x'')}}.<ref>{{cite journal
 | last1 = Nannicini | first1 = Giacomo
 | last2 = Delling | first2 = Daniel
 | last3 = Schultes | first3 = Dominik
 | last4 = Liberti | first4 = Leo
 | doi = 10.1002/NET.20438
 | issue = 2
 | journal = Networks
 | pages = 240–251
 | title = Bidirectional A* search on time-dependent road networks
 | url = https://www.lix.polytechnique.fr/~liberti/bidirtimedepj.pdf
 | volume = 59
 | year = 2012}}</ref>

===Pseudocode===
The following [[Pseudocode|pseudocode]] describes the algorithm:

<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 currently known cost of the cheapest path from start to n.
    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>

'''Remark:''' In this pseudocode, if a node is reached by one path, removed from openSet, and subsequently reached by a cheaper path, it will be added to openSet again. This is essential to guarantee that the path returned is optimal if the heuristic function is [[Admissible heuristic|admissible]] but not  consistent.   If the heuristic is consistent, when a node is removed from openSet the path to it is guaranteed to be optimal so the test ‘<code>tentative_gScore < gScore[neighbor]</code>’ will always fail if the node is reached again. The pseudocode implemented here is sometimes called the ''graph-search'' version of A*.<ref>{{Cite book|title=Artificial intelligence: A modern approach |last1=Russell |first1=Stuart J.|date=2009|last2=Norvig|first2=Peter|author-link2=Peter Norvig|publisher=Pearson|isbn=978-0136042594|edition= 3rd|location=Boston|page=95}}</ref> This is in contrast with the version without the ‘<code>tentative_gScore < gScore[neighbor]</code>’ test to add nodes back to openSet, which is sometimes called the ''tree-search'' version of A* and require a consistent heuristic to guarantee optimality.

[[Image:Astar progress animation.gif|thumb|Illustration of A* search for finding path from a start node to a goal node in a [[robotics|robot]] [[Motion planning|motion planning]] problem. The empty circles represent the nodes in the ''open set'', i.e., those that remain to be explored, and the filled ones are in the closed set. Color on each closed node indicates the distance from the goal: the greener, the closer. One can first see the A* moving in a straight line in the direction of the goal, then when hitting the obstacle, it explores alternative routes through the nodes from the open set. {{see also|Dijkstra's algorithm}}]]

===Example===
An example of an A* algorithm in action where nodes are cities connected with roads and h(x) is the     straight-line distance to the target point:

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

'''Key:''' green: start; blue: goal; orange: visited

The A* algorithm has real-world applications. In this example, edges are railroads and h(x) is the [[Great-circle distance|great-circle distance]] (the shortest possible distance on a sphere) to the target. The algorithm is searching for a path between Washington, D.C., and Los Angeles.

The A* algorithm finding a path of railroads between Washington, D.C. and Los Angeles.

===Implementation details===
There are a number of simple optimizations or implementation details that can significantly affect the performance of an A* implementation.  The first detail to note is that the way the priority queue handles ties can have a significant effect on performance in some situations.  If ties are broken so the queue behaves in a LIFO manner, A* will behave like [[Depth-first search|depth-first search]] among equal cost paths (avoiding exploring more than one equally optimal solution).

When a path is required at the end of the search, it is common to keep with each node a reference to that node's parent.  At the end of the search, these references can be used to recover the optimal path.  If these references are being kept then it can be important that the same node doesn't appear in the priority queue more than once (each entry corresponding to a different path to the node, and each with a different cost).  A standard approach here is to check if a node about to be added already appears in the priority queue.  If it does, then the priority and parent pointers are changed to correspond to the lower-cost path. A standard [[Binary heap|binary heap]] based priority queue does not directly support the operation of searching for one of its elements, but it can be augmented with a [[Hash table|hash table]] that maps elements to their position in the heap, allowing this decrease-priority operation to be performed in logarithmic time. Alternatively, a [[Fibonacci heap]] can perform the same decrease-priority operations in constant amortized time.

===Special cases===
[[Dijkstra's algorithm]], as another example of a uniform-cost search algorithm, can be viewed as a special case of A* where {{tmath|1=h(x) = 0}} for all ''x''.<ref name="geospatial">{{citation|title=Geospatial Analysis: A Comprehensive Guide to Principles, Techniques and Software Tools|first1=Michael John|last1=De Smith|first2=Michael F.|last2=Goodchild|first3=Paul|last3=Longley|publisher=Troubadour Publishing Ltd|year=2007|isbn=9781905886609|page=344|url=https://books.google.com/books?id=SULMdT8qPwEC&pg=PA344}}.</ref><ref name="pythalgs">{{citation |last=Hetland |first=Magnus Lie |title=Python Algorithms: Mastering Basic Algorithms in the Python Language |page=214 |year=2010 |url=https://books.google.com/books?id=9_AXCmGDiz8C&pg=PA214 |archive-url=https://web.archive.org/web/20220215222823/https://books.google.com/books?id=9_AXCmGDiz8C&pg=PA214 |archive-date=15 February 2022 |publisher=Apress |isbn=9781430232377}}.</ref> General [[Depth-first search|depth-first search]] can be implemented using A* by considering that there is a global counter ''C'' initialized with a very large value. Every time we process a node we assign ''C'' to all of its newly discovered neighbors. After every single assignment, we decrease the counter ''C'' by one. Thus the earlier a node is discovered, the higher its {{tmath|h(x)}} value. Both Dijkstra's algorithm and depth-first search can be implemented more efficiently without including an {{tmath|h(x)}} value at each node.

==Properties==

===Termination and completeness===
On finite graphs with non-negative edge weights A* is guaranteed to terminate and is ''complete'', i.e. it will always find a solution (a path from start to goal) if one exists. On infinite graphs with a finite branching factor and edge costs that are bounded away from zero (<math display="inline">d(x,y)>\varepsilon>0</math> for some fixed <math>\varepsilon</math>), A* is guaranteed to terminate only if there exists a solution.<ref name=":2" />

===Admissibility===
A search algorithm is said to be ''admissible'' if it is guaranteed to return an optimal solution. If the heuristic function used by A* is [[Admissible heuristic|admissible]], then A* is admissible. An intuitive "proof" of this  is as follows:

Call a node ''closed'' if it has been visited and is not in the open set.  We ''close'' a node when we remove it from the open set.  A basic property of the A* algorithm, which we'll sketch a proof of below, is that when {{tmath|n}} is closed, {{tmath|f(n)}} is an optimistic estimate (lower bound) of the true distance from the start to the goal.  So when the goal node, {{tmath|g}}, is closed, {{tmath|f(g)}} is no more than the true distance.  On the other hand, it is no less than the true distance, since it is the length of a path to the goal plus a heuristic term.

Now we'll see that whenever a node {{tmath|n}} is closed, {{tmath|f(n)}} is an optimistic estimate.  It is enough to see that whenever the open set is not empty, it has at least one node {{tmath|n}} on an optimal path to the goal for which {{tmath|g(n)}} is the true distance from start, since in that case {{tmath|g(n)}} + {{tmath|h(n)}} underestimates the distance to goal, and therefore so does the smaller value chosen for the closed vertex. Let {{tmath|P}} be an optimal path from the start to the goal.  Let {{tmath|p}} be the last closed node on {{tmath|P}} for which {{tmath|g(p)}} is the true distance from the start to the goal (the start is one such vertex).  The next node in {{tmath|P}} has the correct {{tmath|g}} value, since it was updated when {{tmath|p}} was closed, and it is open since it is not closed.

===Optimality and consistency===

Algorithm A is optimally efficient with respect to a set of alternative algorithms '''Alts''' on a set of problems '''P''' if for every problem P in '''P''' and every algorithm A′ in '''Alts''', the set of nodes expanded by A in solving P is a subset (possibly equal) of the set of nodes expanded by A′ in solving P. The definitive study of the optimal efficiency of A* is due to Rina Dechter and Judea Pearl.<ref name=":1">{{cite journal
 | first = Rina
 | last = Dechter
 |author2= Judea Pearl
 | title = Generalized best-first search strategies and the optimality of A*
 | journal = [[Journal of the ACM]]
 | volume = 32
 | issue = 3
 | pages = 505–536
 | year = 1985
 | doi = 10.1145/3828.3830
 | s2cid = 2092415
 | doi-access = free
 }}
</ref>
They considered a variety of  definitions of '''Alts''' and '''P'''  in combination with A*'s heuristic being merely admissible or being both consistent and admissible.  The most interesting positive result they proved is that A*, with a consistent heuristic, is optimally efficient with respect to all admissible A*-like search algorithms on all "non-pathological" search problems.  Roughly speaking, their notion of the non-pathological problem is what we now mean by "up to tie-breaking".  This result does not hold if A*'s heuristic is admissible but not consistent. In that case, Dechter and Pearl showed there exist admissible A*-like algorithms that can expand arbitrarily fewer nodes than A* on some non-pathological problems.

Optimal efficiency is about the ''set'' of nodes expanded, not the ''number'' of node expansions (the number of iterations of A*'s main loop).  When the heuristic being used is admissible but not consistent, it is possible for a node to be expanded by A* many times, an exponential number of times in the worst case.<ref name="Martelli">{{cite journal
 | first = Alberto
 | last = Martelli
 | title = On the Complexity of Admissible Search Algorithms
 | journal = Artificial Intelligence
 | volume = 8
 | issue = 1
 | pages = 1–13
 | year = 1977
 | doi = 10.1016/0004-3702(77)90002-9
 }}
</ref>
In such circumstances, Dijkstra's algorithm could outperform A* by a large margin. However, more recent research found that this pathological case only occurs in certain contrived situations where the edge weight of the search graph is exponential in the size of the graph and that certain inconsistent (but admissible) heuristics can lead to a reduced number of node expansions in A* searches.<ref name="Felner2011">{{cite journal | first = Ariel | last = Felner | author2 = Uzi Zahavi | title = Inconsistent heuristics in theory and practice | journal = Artificial Intelligence | volume = 175 | issue = 9–10 | pages = 1570–1603 | year = 2011 | doi = 10.1016/j.artint.2011.02.001| doi-access = free }}</ref><ref name="Zhang2009">{{cite conference | first1 = Zhifu | last1 = Zhang | author2 = N. R. Sturtevant | date = 2009 | title = Using Inconsistent Heuristics on A* Search | conference = Twenty-First International Joint Conference on Artificial Intelligence |url=https://www.aaai.org/ocs/index.php/IJCAI/IJCAI-09/paper/viewPDFInterstitial/413/726 |pages=634–639}}</ref>

==Bounded relaxation==
[[Image:Weighted A star with eps 5.gif|thumb|A* search that uses a heuristic that is 5.0(=ε) times a [[consistent heuristic]], and obtains a suboptimal path]]
While the admissibility criterion guarantees an optimal solution path, it also means that A* must examine all equally meritorious paths to find the optimal path. To compute approximate shortest paths, it is possible to speed up the search at the expense of optimality by relaxing the admissibility criterion. Oftentimes we want to bound this relaxation, so that we can guarantee that the solution path is no worse than (1 + ''ε'') times the optimal solution path. This new guarantee is referred to as ''ε''-admissible.

There are a number of ''ε''-admissible algorithms:

*Weighted A*/Static Weighting's.<ref>{{cite journal
 | first = Ira
 | last = Pohl
 | title = First results on the effect of error in heuristic search
 | journal = Machine Intelligence 5
 | pages = 219–236 |isbn=978-0-85224-176-9 |oclc=1067280266
 | year = 1970 |publisher=Edinburgh University Press
}}</ref> If ''h<sub>a</sub>''(''n'') is an admissible heuristic function, in the weighted version of the A* search one uses {{math|1=''h<sub>w</sub>''(''n'') = ''ε h<sub>a</sub>''(''n'')}}, {{math|1=''ε'' > 1}} as the heuristic function, and perform the A* search as usual (which eventually happens faster than using ''h<sub>a</sub>'' since fewer nodes are expanded). The path hence found by the search algorithm can have a cost of at most ''ε'' times that of the least cost path in the graph.<ref name="pearl84">{{cite book
 | first = Judea
 | last = Pearl
 | title = Heuristics: Intelligent Search Strategies for Computer Problem Solving
 | publisher = Addison-Wesley
 | year = 1984
 | isbn = 978-0-201-05594-8
 | url = https://archive.org/details/heuristicsintell00pear
 }}</ref>
*Convex Upward/Downward Parabola (XUP/XDP).<ref>{{Cite journal |last=Chen |first=Jingwei |last2=Sturtevant |first2=Nathan R. |date=2019 |title=Conditions for Avoiding Node Re-expansions in Bounded Suboptimal Search |url=https://www.ijcai.org/proceedings/2019/170 |journal=Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence |publisher=International Joint Conferences on Artificial Intelligence Organization |pages=1220–1226}}</ref> Modification to the cost function in weighted A* to push optimality toward the start or goal.  XDP gives paths which are near optimal close to the start, and XUP paths are near-optimal close to the goal. Both yield <math>\epsilon</math>-optimal paths overall.
*:<math>f_{\text{XDP}}(n) = \frac{1}{2\epsilon} \left[ \ g(n) + (2\epsilon - 1) + \sqrt{(g(n)-h(n))^2 + 4\epsilon g(n)h(n) } \ \right]</math>.
*:<math>f_{\text{XUP}}(n) = \frac{1}{2\epsilon} \left[ \ g(n)+h(n) + \sqrt{(g(n)+h(n))^2+4\epsilon (\epsilon-1)h(n)^2} \ \right]</math>.
*Piecewise Upward/Downward Curve (pwXU/pwXD).<ref>{{Cite journal |last=Chen |first=Jingwei |last2=Sturtevant |first2=Nathan R. |date=2021-05-18 |title=Necessary and Sufficient Conditions for Avoiding Reopenings in Best First Suboptimal Search with General Bounding Functions |url=https://ojs.aaai.org/index.php/AAAI/article/view/16485 |journal=Proceedings of the AAAI Conference on Artificial Intelligence |language=en |volume=35 |issue=5 |pages=3688–3696 |doi=10.1609/aaai.v35i5.16485 |issn=2374-3468|doi-access=free }}</ref> Similar to XUP/XDP but with piecewise functions instead of parabola. Solution paths are also <math>\epsilon</math>-optimal.                                                                              
*:<math>f_{\text{pwXD}}(n) = \begin{cases} g(n)+h(n), & \text{if } h(n) > g(n) \\ 
g(n) + (2\epsilon-1)h(n)/\epsilon, & \text{if } h(n) \le g(n) \end{cases}</math>
*:<math>f_{\text{pwXU}}(n) = \begin{cases} g(n)/(2\epsilon-1)+h(n), & \text{if } g(n) < (2\epsilon-1)h(n)
\\ (g(n) + h(n))/\epsilon, & \text{if } g(n) \ge (2\epsilon-1)h(n) \end{cases}</math>
* Dynamic Weighting<ref>{{cite conference
 | first = Ira
 | last = Pohl
 | title = The avoidance of (relative) catastrophe, heuristic competence, genuine dynamic weighting and computational issues in heuristic problem solving
 | book-title = Proceedings of the Third International Joint Conference on Artificial Intelligence (IJCAI-73)
 | volume = 3
 | pages = 11–17
 | place = California, USA
 | date = August 1973
 | url = https://www.cs.auckland.ac.nz/courses/compsci709s2c/resources/Mike.d/Pohl1973WeightedAStar.pdf
}}</ref> uses the cost function {{tmath|1=f(n) = g(n) + (1 + \varepsilon w(n))h(n)}}, where <math>w(n) = \begin{cases} 1 - \frac{d(n)}{N} & d(n) \le N \\ 0 & \text{otherwise} \end{cases}</math>, and where {{tmath|d(n)}} is the depth of the search and ''N'' is the anticipated length of the solution path.
* Sampled Dynamic Weighting<ref>{{cite conference
 | first = Andreas
 | last = Köll
 |author2= Hermann Kaindl
 | title = A new approach to dynamic weighting
 | book-title = Proceedings of the Tenth European Conference on Artificial Intelligence (ECAI-92)
 | pages = 16–17 |url=https://dl.acm.org/doi/abs/10.5555/145448.145484
 | place = Vienna, Austria
 | date = August 1992 |isbn=978-0-471-93608-4 |publisher=Wiley
}}</ref> uses sampling of nodes to better estimate and debias the heuristic error.
* <math>A^*_\varepsilon</math>.<ref>{{cite journal
 | first = Judea
 | last = Pearl
 |author2= Jin H. Kim
 | title = Studies in semi-admissible heuristics
 | journal =  IEEE Transactions on Pattern Analysis and Machine Intelligence
 | volume = 4
 | issue = 4
 | pages = 392–399
 | year = 1982
| doi = 10.1109/TPAMI.1982.4767270
 | pmid = 21869053
 | s2cid = 3176931
 }}</ref> uses two heuristic functions. The first is the FOCAL list, which is used to select candidate nodes, and the second ''h<sub>F</sub>'' is used to select the most promising node from the FOCAL list.
* ''A<sub>ε</sub>''<ref>{{cite conference
 |first=Malik 
 |last=Ghallab 
 |author2=Dennis Allard 
 |title=''A<sub>ε</sub>'' – an efficient near admissible heuristic search algorithm 
 |book-title=Proceedings of the Eighth International Joint Conference on Artificial Intelligence (IJCAI-83) 
 |volume=2 
 |pages=789–791 
 |place=Karlsruhe, Germany 
 |date=August 1983 
 |url=http://ijcai.org/Past%20Proceedings/IJCAI-83-VOL-2/PDF/048.pdf 
 |url-status=dead 
 |archive-url=https://web.archive.org/web/20140806200328/http://ijcai.org/Past%20Proceedings/IJCAI-83-VOL-2/PDF/048.pdf 
 |archive-date=2014-08-06 
}}</ref> selects nodes with the function {{tmath|A f(n) + B h_F(n)}}, where ''A'' and ''B'' are constants. If no nodes can be selected, the algorithm will backtrack with the function {{tmath|C f(n) + D h_F(n)}}, where ''C'' and ''D'' are constants.
* AlphA*<ref>{{cite report |first=Bjørn |last=Reese |title=AlphA*: An ''ε''-admissible heuristic search algorithm |year=1999 |publisher=Institute for Production Technology, University of Southern Denmark |url=http://home1.stofanet.dk/breese/astaralpha-submitted.pdf.gz |access-date=2014-11-05 |archive-url=https://web.archive.org/web/20160131214618/http://home1.stofanet.dk/breese/astaralpha-submitted.pdf.gz |archive-date=2016-01-31 |url-status=dead }}</ref> attempts to promote depth-first exploitation by preferring recently expanded nodes. AlphA* uses the cost function <math>f_\alpha(n) = (1 + w_\alpha(n)) f(n)</math>, where <math>w_\alpha(n) = \begin{cases} \lambda & g(\pi(n)) \le g(\tilde{n}) \\ \Lambda & \text{otherwise} \end{cases}</math>, where ''λ'' and ''Λ'' are constants with <math>\lambda \le \Lambda</math>, ''π''(''n'') is the parent of ''n'', and ''ñ'' is the most recently expanded node.

==Complexity==

As a heuristic search algorithm, the performance of A* is heavily influenced by the quality of the heuristic function <math display="inline">h(n)</math>. If the heuristic closely approximates the true cost to the goal, A* can significantly reduce the number of node expansions. On the other hand, a poor heuristic can lead to many unnecessary expansions.

===Worst case===
In the worst case, A* expands all nodes <math display="inline">n</math> for which <math display="inline">f(n)=g(n)+h(n) \leq C^{*}</math>, where <math display="inline">C^{*}</math> is the cost of the optimal goal node.

==== Why it cannot be worse ====
Suppose there is a node <math display="inline">N'</math> in the open list with <math display="inline">f(N') > C^{*}</math>, and it's the next node to be expanded. Since the goal node has <math display="inline">f(goal)=g(goal)+h(goal)=g(goal)=C^{*}</math>, and <math display="inline"> f(N') > C^{*} </math>, the goal node will have a lower f-value and will be expanded before <math display="inline">N'</math>. Therefore, A* never expands nodes with <math display="inline"> f(n) > C^{*} </math>.

==== Why it cannot be better ====
Assume there exists an optimal algorithm that expands fewer nodes than <math display="inline"> C^{*} </math> in the worst case using the same heuristic. That means there must be some node <math display="inline"> N' </math> such that <math display="inline"> f(N') < C^{*} </math>, yet the algorithm chooses not to expand it.

Now consider a modified graph where a new edge of cost <math display="inline"> \varepsilon </math> (with <math display="inline"> \varepsilon > 0 </math>) is added from <math display="inline"> N' </math> to the goal. If <math display="inline"> f(N')+\varepsilon<C^{*} </math>, then the new optimal path goes through <math display="inline"> N' </math>. However, since the algorithm still avoids expanding <math display="inline"> N' </math>, it will miss the new optimal path, violating its optimality.

Therefore, no optimal algorithm including A* could expand fewer nodes than <math display="inline"> C^{*} </math> in the worst case.

==== Mathematical notation ====
The worst-case complexity of A* is often described as <math display="inline">O(b^d)</math>, where <math>b</math> is the branching factor and <math display="inline">d</math> is the depth of the shallowest goal. While this gives a rough intuition, it does not precisely capture the actual behavior of A*.

A more accurate bound considers the number of nodes with <math display="inline">f(n) \leq C^{*}</math>. If <math>\varepsilon</math> is the smallest possible difference in <math display="inline">f</math>-cost between distinct nodes, then A* may expand up to:
{{center|<math>O\left(\frac{C^{*}}{\varepsilon}\right)</math>}}

This represents both the time and space complexity in the worst case.

===Space complexity===

The [[Space complexity|space complexity]] of A* is roughly the same as that of all other graph search algorithms, as it keeps all generated nodes in memory.<ref name=":2" /> In practice, this turns out to be the biggest drawback of the A* search, leading to the development of memory-bounded heuristic searches, such as [[Iterative deepening A*]], memory-bounded A*, and [[SMA*]].

==Applications==
A* is often used for the common [[Pathfinding|pathfinding]] problem in applications such as video games, but was originally designed as a general graph traversal algorithm.<ref name="nilsson"/>
It finds applications in diverse problems, including the problem of [[Parsing|parsing]] using stochastic grammars in [[Natural language processing|NLP]].<ref>{{cite conference
|url= https://people.eecs.berkeley.edu/~klein/papers/pcfg-astar.pdf
|last1=Klein
|first1=Dan
|last2=Manning
|first2=Christopher D.
|title=A* parsing: fast exact Viterbi parse selection
|book-title=Proceedings of the 2003 Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics
|pages=119–126
|doi=10.3115/1073445.1073461
|year=2003
}}</ref>
Other cases include an Informational search with online learning.<ref name="WPCleanerAuto1">{{cite journal
 |url          = http://www.eng.tau.ac.il/~bengal/GTA.pdf
 |title        = A Group-Testing Algorithm with Online Informational Learning
 |author       = Kagan E.
 |author2      = Ben-Gal I.
 |journal      = IIE Transactions
 |volume       = 46
 |issue        = 2
 |pages        = 164–184
 |year         = 2014
 |doi          = 10.1080/0740817X.2013.803639
 |s2cid        = 18588494
 |access-date  = 2016-02-12
 |archive-date = 2016-11-05
 |archive-url  = https://web.archive.org/web/20161105103321/http://www.eng.tau.ac.il/~bengal/GTA.pdf
 |url-status   = dead
}}</ref>

==Relations to other algorithms==
What sets A* apart from a [[Greedy algorithm|greedy]] best-first search algorithm is that it takes the cost/distance already traveled, {{math|''g''(''n'')}}, into account.

Some common variants of [[Dijkstra's algorithm]] can be viewed as a special case of A* where the heuristic <math>h(n) = 0</math> for all nodes;<ref name="geospatial"/><ref name="pythalgs"/> in turn, both Dijkstra and A* are special cases of [[Dynamic programming|dynamic programming]].<ref>{{cite conference |first1=Dave |last1=Ferguson |first2=Maxim |last2=Likhachev |first3=Anthony |last3=Stentz |title=A Guide to Heuristic-based Path Planning |year=2005 |url=https://www.cs.cmu.edu/afs/cs.cmu.edu/Web/People/maxim/files/hsplanguide_icaps05ws.pdf |archive-url=https://web.archive.org/web/20160629214339/https://www.cs.cmu.edu/afs/cs.cmu.edu/Web/People/maxim/files/hsplanguide_icaps05ws.pdf |archive-date=2016-06-29 |url-status=live |book-title=Proceedings of the international workshop on planning under uncertainty for autonomous systems, international conference on automated planning and scheduling (ICAPS) |pages=9–18}}</ref>
A* itself is a special case of a generalization of [[Branch and bound|branch and bound]].<ref>{{cite journal |last1=Nau |first1=Dana S. |first2=Vipin |last2=Kumar |first3=Laveen |last3=Kanal |title=General branch and bound, and its relation to A∗ and AO∗ |journal=Artificial Intelligence |volume=23 |issue=1 |year=1984 |pages=29–58 |url=https://www.cs.umd.edu/~nau/papers/nau1984general.pdf |archive-url=https://web.archive.org/web/20121004051632/http://www.cs.umd.edu/~nau/papers/nau1984general.pdf |archive-date=2012-10-04 |url-status=live |doi=10.1016/0004-3702(84)90004-3}}</ref>

A* is similar to [[Beam search|beam search]] except that beam search maintains a limit on the numbers of paths that it has to explore.<ref>{{Cite web |title=Variants of A* |url=http://theory.stanford.edu/~amitp/GameProgramming/Variations.html |access-date=2023-06-09 |website=theory.stanford.edu}}</ref>

==Variants==
*[[Anytime A*]]<ref>{{cite journal |last1=Hansen |first1=Eric A. |first2=Rong |last2=Zhou |title=Anytime Heuristic Search |journal= Journal of Artificial Intelligence Research|volume=28 |issue= |pages=267–297 |date=2007 |doi= 10.1613/jair.2096|s2cid=9832874 |url=https://www.jair.org/index.php/jair/article/view/10489 |doi-access=free |arxiv=1110.2737 }}</ref>
*[[Any-angle path planning#A*-based|Block A*]]
*[[D*]]
*[[Any-angle path planning|Field D*]]
*[[Fringe search|Fringe]]
*[[Incremental heuristic search|Fringe Saving A* (FSA*)]]
*[[Incremental heuristic search|Generalized Adaptive A* (GAA*)]]
*[[Incremental heuristic search]]
*Reduced A*<ref> {{Cite journal|last1=Fareh|first1=Raouf|last2=Baziyad|first2=Mohammed|last3=Rahman|first3=Mohammad H.|last4=Rabie|first4=Tamer|last5=Bettayeb|first5=Maamar|date=2019-05-14|title=Investigating Reduced Path Planning Strategy for Differential Wheeled Mobile Robot|url=https://www.cambridge.org/core/journals/robotica/article/abs/investigating-reduced-path-planning-strategy-for-differential-wheeled-mobile-robot/6EDFFC11CEF00D0E010C0D149FE9C811|journal=Robotica|language=en|volume=38|issue=2|pages=235–255|doi=10.1017/S0263574719000572|s2cid=181849209|issn=0263-5747|url-access=subscription}}</ref>
*[[Iterative deepening A*|Iterative deepening A* (IDA*)]]
*[[Jump point search]]
*[[Lifelong Planning A*|Lifelong Planning A* (LPA*)]]
*New Bidirectional A* (NBA*)<ref>{{cite tech report |last1=Pijls |first1=Wim |last2=Post |first2=Henk |url=https://repub.eur.nl/pub/16100/ei2009-10.pdf |archive-url=https://web.archive.org/web/20140611141858/http://repub.eur.nl/pub/16100/ei2009-10.pdf |archive-date=2014-06-11 |url-status=live |title=Yet another bidirectional algorithm for shortest paths |id=EI 2009-10 |publisher=Econometric Institute, Erasmus University Rotterdam}}</ref>
*[[SMA*|Simplified Memory bounded A* (SMA*)]]
*[[Theta*]]

A* can also be adapted to a [[Bidirectional search|bidirectional search]] algorithm, but special care needs to be taken for the stopping criterion.<ref>{{cite web |last1=Goldberg |first1=Andrew V. |last2=Harrelson |first2=Chris |last3=Kaplan |first3=Haim |last4=Werneck |first4= Renato F. |title=Efficient Point-to-Point Shortest Path Algorithms |url=http://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/EPP%20shortest%20path%20algorithms.pdf |publisher=[[Organization:Princeton University|Princeton University]] |archive-url=https://web.archive.org/web/20220518121847/https://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/EPP%20shortest%20path%20algorithms.pdf |archive-date=18 May 2022 |url-status=live }}</ref>

==See also==
* [[Any-angle path planning]] – Search for paths that are not limited to moving along graph edges but rather can take on any angle
* {{Annotated link|Breadth-first search}}
* {{Annotated link|Depth-first search}}
* {{Annotated link|Dijkstra's algorithm}}

==Notes==
{{notelist}}

==References==
{{Reflist|30em}}

==Further reading==
* {{cite book
 | first = N. J.
 | last = Nilsson
 | title = Principles of Artificial Intelligence
 | publisher = Tioga Publishing Company
 | location = Palo Alto, California
 | year = 1980
 | isbn = 978-0-935382-01-3
 | url = https://archive.org/details/principlesofarti00nils
 }}

==External links==
* Variation on A* called [https://web.archive.org/web/20090917155722/http://www.cs.ualberta.ca/~mmueller/ps/hpastar.pdf Hierarchical Path-Finding A* (HPA*)]
* {{cite web |author1=Brian Grinstead |title=A* Search Algorithm in JavaScript (Updated) |url=https://briangrinstead.com/blog/astar-search-algorithm-in-javascript-updated/ |access-date=8 February 2021 |archive-url=https://web.archive.org/web/20200215174913/https://briangrinstead.com/blog/astar-search-algorithm-in-javascript-updated/ |archive-date=15 February 2020 |url-status=live}}

{{Graph traversal algorithms}}

{{DEFAULTSORT:A Search Algorithm}}
[[Category:Graph algorithms]]
[[Category:Routing algorithms]]
[[Category:Search algorithms]]
[[Category:Combinatorial optimization]]
[[Category:Game artificial intelligence]]

{{Sourceattribution|A* search algorithm}}