Editing A* search algorithm (section)

{{short description|Algorithm used for pathfinding and graph traversal}}
{{redirect|A Star|other uses|A* (disambiguation)|and|Astar (disambiguation)}}
{{Infobox algorithm
|name= <!-- Defaults to article name -->
|class= [[Search algorithm]]
|image=
|caption=
|data= [[Graph (data structure)|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]] and [[pathfinding]] [[algorithm]] that is used in many fields of [[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.|author-link1=Stuart J. Russell|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]] 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]] (the maximum number of successors for any given state), as it stores all generated nodes in memory. Thus, in practical [[travel-routing system]]s, it is generally outperformed by algorithms that can pre-process the graph to attain better performance,<ref>{{cite book
 | last1 = Delling | first1 = D.
 | last2 = Sanders | first2 = P. | author2-link = Peter Sanders (computer scientist)
 | last3 = Schultes | first3 = D.
 | last4 = Wagner | first4 = D. | author4-link = Dorothea Wagner
 | 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 E. Hart|Peter Hart]], [[Nils Nilsson (researcher)|Nils Nilsson]] and [[Bertram Raphael]] of Stanford Research Institute (now [[SRI International]]) first published the algorithm in 1968.<ref name="nilsson">{{cite journal
 | first1 = P. E. |author1-link=Peter E. Hart
 | last1 = Hart
 | last2= Nilsson |first2=N.J.|last3= Raphael |first3=B.
 | author2-link=Nils Nilsson (researcher) |author3-link=Bertram Raphael
 | 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]] for using a specific-goal-directed [[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.