# A* search algorithm

**A*** (pronounced "A-star") is a best-first graph search algorithm that finds a minimum-cost path by ordering nodes with the evaluation function \( f(n) = g(n) + h(n) \), where \( g(n) \) is the cost of reaching node \( n \) from the start and \( h(n) \) is an estimate of the remaining cost to a goal. It was published in 1968 by Peter E. Hart, Nils J. Nilsson, and Bertram Raphael at the Stanford Research Institute and remains a standard method for pathfinding in robotics, games, and route planning.<sup>[1](https://learngraphtheory.org/articles/a-star-algorithm-in-ai.html)</sup><sup> • </sup><sup>[2](https://www.cs.unh.edu/~ruml/papers/hatem-diss-final.pdf)</sup>

| Key fact | Detail |
|---|---|
| Original publication | Hart, Nilsson, and Raphael, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths", IEEE Transactions on Systems Science and Cybernetics SSC-4(2):100–107, July 1968<sup>[1](https://learngraphtheory.org/articles/a-star-algorithm-in-ai.html)</sup> |
| Evaluation function | \( f(n) = g(n) + h(n) \): cost so far plus estimated cost to the goal; nodes with the lowest \( f \) are expanded first<sup>[2](https://www.cs.unh.edu/~ruml/papers/hatem-diss-final.pdf)</sup> |
| Optimality guarantee | If \( h \) is admissible (never overestimates the true remaining cost \( h^* \)), the first solution found is optimal<sup>[3](https://courses.cs.umbc.edu/471/spring23/02/notes/05_search2/05a.pdf)</sup> |
| Completeness | A* is complete whenever the branching factor is finite and every action has a fixed, positive cost<sup>[3](https://courses.cs.umbc.edu/471/spring23/02/notes/05_search2/05a.pdf)</sup> |
| Optimal efficiency | With a consistent heuristic, Dechter and Pearl (1988) argued that no other algorithm guarantees an optimal solution while exploring fewer nodes than A*, a claim Holte's 2010 paper later showed to be false<sup>[2](https://www.cs.unh.edu/~ruml/papers/hatem-diss-final.pdf)</sup> |
| Main bottleneck | Memory: storing the open and closed lists can require an exponential amount of space, which motivates most variants<sup>[2](https://www.cs.unh.edu/~ruml/papers/hatem-diss-final.pdf)</sup> |
| Special cases | With \( h(n) = 0 \) for all nodes, A* behaves like uniform-cost search, which on graphs with nonnegative weights is Dijkstra's algorithm<sup>[3](https://courses.cs.umbc.edu/471/spring23/02/notes/05_search2/05a.pdf)</sup><sup> • </sup><sup>[1](https://learngraphtheory.org/articles/a-star-algorithm-in-ai.html)</sup> |

## How the algorithm works

A* maintains an open list of generated but unexpanded nodes, typically ordered by \( f \), and a closed list of states already encountered, used to detect duplicates reached by multiple paths. Each iteration removes the node with the lowest \( f \) value, expands it by generating its successors, and adds the successors to the open list with updated path costs. Nodes with lower \( f \) are estimated to lie on cheaper paths to the goal and are therefore explored first.<sup>[2](https://www.cs.unh.edu/~ruml/papers/hatem-diss-final.pdf)</sup>

The heuristic \( h \) carries the problem-specific knowledge. Three reference cases show its role. If \( h(n) = h^*(n) \) for all nodes, the perfect heuristic, A* expands only nodes on an optimal solution path and does no extra work. If \( h(n) = 0 \) for all nodes, the null heuristic, A* acts like uniform-cost search. Between these extremes, if \( h_1(n) < h_2(n) \leq h^*(n) \) for all non-goal nodes, then every node expanded by the search using \( h_2 \) is also expanded by the search using \( h_1 \); \( h_2 \) is said to be better informed, and the closer \( h \) is to \( h^* \), the fewer extra nodes are expanded.<sup>[3](https://courses.cs.umbc.edu/471/spring23/02/notes/05_search2/05a.pdf)</sup>

## Guarantees and their conditions

**Admissibility.** A heuristic is admissible when \( h(n) \leq h^*(n) \) holds for every node, meaning it never overestimates the true cost of the cheapest path from \( n \) to a goal. Using an admissible heuristic guarantees that the first solution A* finds is an optimal one.<sup>[3](https://courses.cs.umbc.edu/471/spring23/02/notes/05_search2/05a.pdf)</sup>

**Consistency.** A heuristic is consistent if it does not decrease between a node and one of its descendants by more than the cheapest path between them, written \( h(n) \geq C^*(n, m) + h(m) \), where \( C^*(n, m) \) is the cheapest path cost between nodes \( n \) and \( m \). With a consistent heuristic, A* explores only the nodes necessary to find an optimal solution, and Dechter and Pearl's 1988 result establishes that no other algorithm guarantees an optimal solution while exploring fewer nodes.<sup>[2](https://www.cs.unh.edu/~ruml/papers/hatem-diss-final.pdf)</sup>

These guarantees have known limits. Robert Holte, a computer scientist at [Carleton University](https://www.edgepedia.org/carleton-university) who studies heuristic search, published a 2010 paper in the Proceedings of the International Symposium on Combinatorial Search showing that several commonly held statements are false, including the claim that A* expands fewer nodes than any other equally informed algorithm that finds optimal solutions, and the claim that any admissible heuristic can be made consistent by the simple pathmax technique.<sup>[4](https://ojs.aaai.org/index.php/SOCS/article/view/18160)</sup>

## History

Hart, Nilsson, and Raphael published the algorithm in July 1968 in IEEE Transactions on Systems Science and [Cybernetics](https://www.edgepedia.org/cybernetics), volume 4, issue 2, pages 100 to 107. What drove the work in practice was Shakey, a mobile robot built at SRI that needed to chart its own path among a set of rooms instead of running along a predetermined course. The paper made two lasting contributions: it separated the search procedure from the heuristic knowledge inside it, so the same loop becomes a different algorithm depending on which \( h \) is supplied, and it proved the optimality guarantee for admissible heuristics.<sup>[1](https://learngraphtheory.org/articles/a-star-algorithm-in-ai.html)</sup> Nilsson spent twenty-three years at the Artificial Intelligence Center of SRI International, where he co-invented A* and the STRIPS planning system and co-directed work on Shakey.<sup>[5](https://ai.stanford.edu/~nilsson/)</sup>

A 1972 note in the SIGART Newsletter, no. 37, pages 28–29, corrected the original optimality argument.<sup>[1](https://learngraphtheory.org/articles/a-star-algorithm-in-ai.html)</sup><sup> • </sup><sup>[6](https://ai.stanford.edu/~nilsson/publications.html)</sup>

## Complexity and heuristic accuracy

[Judea Pearl](https://www.edgepedia.org/judea-pearl), a computer scientist at the [University of California, Los Angeles](https://www.edgepedia.org/university-of-california-los-angeles) known for work on probabilistic reasoning and heuristic search, analyzed the average number of nodes A* expands as a function of heuristic accuracy, modeling the errors \( h^* - h \) as random variables over an \( m \)-ary tree with unit branch costs and a goal at distance \( N \) from the root. If the typical error grows like \( \varphi(h^*) \), the mean complexity grows approximately like \( G(N) \exp[c\varphi(N)] \), where \( c \) is a positive constant and \( G(N) \) is \( O(N^2) \). A necessary and sufficient condition for maintaining polynomial search complexity is that A* be guided by heuristics with logarithmic precision, for example \( \varphi(N) = (\log N)^k \). The same analysis showed A* makes much greater use of its heuristic knowledge than a backtracking procedure would under similar conditions.<sup>[7](https://www.sciencedirect.com/science/article/pii/0004370283900139)</sup>

László Mérõ's 1984 paper in Artificial Intelligence described an improved algorithm, B, that treats the estimate \( \hat{h}(n) \) as a variable rather than a constant, updating it as the search proceeds, and proved it never expands more nodes than A* while expanding far fewer in some cases. The same paper proved that no overall optimal algorithm exists if cost is measured by the total number of node expansions.<sup>[8](https://www.sciencedirect.com/science/article/pii/0004370284900031)</sup>

Later work complicated the intuition that accuracy alone determines performance. A 2013 study by Hang Dinh and Hieu Dinh found an analytical correlation between a heuristic's inconsistency and its accuracy, and experiments on [Knapsack problem](https://www.edgepedia.org/knapsack-problem) domains showed that in many cases the more accurate heuristics also have higher levels of inconsistency and result in fewer node expansions by A*.<sup>[9](https://arxiv.org/abs/1307.2200)</sup>

## Variants

A*'s memory requirement is its main practical limitation: maintaining the open and closed lists can require an exponential amount of memory, making the algorithm impractical for large problems.<sup>[2](https://www.cs.unh.edu/~ruml/papers/hatem-diss-final.pdf)</sup> The main families of variants address this and related limits:

- **Linear-space search.** IDA* (Korf, 1985) performs an [iterative deepening depth-first search](https://www.edgepedia.org/iterative-deepening-depth-first-search) using \( f \) to prune nodes at each iteration; recursive best-first search (Korf, 1993) always expands nodes in best-first order even with a non-monotonic cost function. Because they keep no closed list, they cannot detect duplicate states, which limits them to domains with few duplicates.<sup>[2](https://www.cs.unh.edu/~ruml/papers/hatem-diss-final.pdf)</sup>
- **Bounded-suboptimal and anytime search.** Weighted A* scales the heuristic to find solutions quickly within a proven bound on suboptimality. Anytime variants such as ARA* introduce a weighting value \( \varepsilon \) to find an initial suboptimal path and then reduce it to improve quality over time; Anytime Nonparametric A* (ANA*), proposed by Jur van den Berg and colleagues in 2011, removes the ad-hoc parameters and adaptively reduces \( \varepsilon \), proving that each expanded node provides an upper bound on the suboptimality of the current-best solution.<sup>[10](https://ojs.aaai.org/index.php/AAAI/article/view/7819)</sup>
- **Bidirectional search.** A 2026 study of real-time route optimization in smart cities found that Bidirectional A* consistently outperformed the mean of forward- and backward-only A*, reducing runtime by 23.6–66.2% for shortest-distance queries and 37.0–87.5% for minimum-travel-time queries, with the largest gains for time-weighted fastest-route searches.<sup>[11](https://www.sciencedirect.com/science/article/pii/S2667305326000165)</sup>
- **Incremental and replanning search.** D* and D* Lite reuse search effort for repeated planning in changing environments; a survey of heuristic-based path planning by Ferguson, Likhachev, and Stentz at [Carnegie Mellon University](https://www.edgepedia.org/carnegie-mellon-university) groups static algorithms such as A* with replanning (D*), anytime (ARA*), and anytime replanning (AD*) algorithms used on real robotic systems.<sup>[12](https://www.cs.cmu.edu/~maxim/files/hsplanguide_icaps05ws_abs.html)</sup>

## Applications

A* heuristic search underlies GPS navigation, video game AI, and robotics.<sup>[13](https://sigcsevirtual2026.acm.org/details/sigcse-virtual-2026-papers/55/Ice-Cream-Express-A-Game-Based-Tool-to-Teach-AI-Pathfinding-to-K-12-Learners)</sup> In robotics, heuristic search planners built on A* variants have been deployed on systems including an industrial mobile manipulator used for paint stripping aircraft, a full-size K-MAX helicopter, and a full-size SUV that won the [DARPA Urban Challenge](https://www.edgepedia.org/darpa-urban-challenge) race in 2007.<sup>[14](https://www.cs.cmu.edu/afs/cs/Web/People/maxim/files/research_old.pdf)</sup> Route planning research continues to build on the algorithm: an improved A* with angle-constrained evaluation functions has been applied to oil sample transportation path planning,<sup>[15](https://www.nature.com/articles/s41598-023-49266-z)</sup> and neural networks have been used to learn the cost functions of A* for personalized route recommendation.<sup>[16](https://arxiv.org/abs/1907.08489)</sup>

## References

1. [A* Search Algorithm in AI: The Complete Guide, learngraphtheory.org](https://learngraphtheory.org/articles/a-star-algorithm-in-ai.html)
2. [Heuristic Search with Limited Memory (Hatem, University of New Hampshire dissertation)](https://www.cs.unh.edu/~ruml/papers/hatem-diss-final.pdf)
3. [Algorithm A* lecture notes, University of Maryland Baltimore County, CMSC 471](https://courses.cs.umbc.edu/471/spring23/02/notes/05_search2/05a.pdf)
4. [Holte, R. (2010). Common Misconceptions Concerning Heuristic Search. Proceedings of the International Symposium on Combinatorial Search](https://ojs.aaai.org/index.php/SOCS/article/view/18160)
5. [Nils J. Nilsson Home Page, Stanford University](https://ai.stanford.edu/~nilsson/)
6. [Nils J. Nilsson, Publications, Stanford University](https://ai.stanford.edu/~nilsson/publications.html)
7. [Pearl, J. (1983). Knowledge versus search: A quantitative analysis using A*. Artificial Intelligence 20(1)](https://www.sciencedirect.com/science/article/pii/0004370283900139)
8. [Mérõ, L. (1984). A heuristic search algorithm with modifiable estimate. Artificial Intelligence 23(1):13–27](https://www.sciencedirect.com/science/article/pii/0004370284900031)
9. [Dinh, H. and Dinh, H. (2013). Inconsistency and Accuracy of Heuristics with A* Search. arXiv:1307.2200](https://arxiv.org/abs/1307.2200)
10. [van den Berg, J. et al. (2011). Anytime Nonparametric A*. AAAI 25(1):105–111](https://ojs.aaai.org/index.php/AAAI/article/view/7819)
11. [Real-time route optimization in smart cities via Bidirectional A* algorithm, Expert Systems with Applications, 2026](https://www.sciencedirect.com/science/article/pii/S2667305326000165)
12. [Ferguson, D., Likhachev, M., Stentz, A. A Guide to Heuristic-based Path Planning, Carnegie Mellon University](https://www.cs.cmu.edu/~maxim/files/hsplanguide_icaps05ws_abs.html)
13. [Ice Cream Express: A Game-Based Tool to Teach AI Pathfinding to K-12 Learners, SIGCSE Virtual 2026](https://sigcsevirtual2026.acm.org/details/sigcse-virtual-2026-papers/55/Ice-Cream-Express-A-Game-Based-Tool-to-Teach-AI-Pathfinding-to-K-12-Learners)
14. [Likhachev, M. research statement, Carnegie Mellon University](https://www.cs.cmu.edu/afs/cs/Web/People/maxim/files/research_old.pdf)
15. [A route planning for oil sample transportation based on improved A* algorithm, Scientific Reports, 2023](https://www.nature.com/articles/s41598-023-49266-z)
16. [Empowering A* Search Algorithms with Neural Networks for Personalized Route Recommendation, arXiv:1907.08489](https://arxiv.org/abs/1907.08489)

---
*Topic: Encyclopedia › Technology and the built world › Computing and digital systems › Artificial intelligence and data › Algorithms and computational methods › Graph and network algorithms › Shortest paths*

*Initially written Sep 17, 2026 · Reviewed: Sep 20, 2026; Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license