A* Search Algorithm
- Introduced by
- Peter E. Hart, Nils J. Nilsson, and Bertram Raphael
- Year
- 1968
- Type
- algorithm
- Family
- Graph Algorithms
What does it do?
The A* Search Algorithm, developed by Peter E. Hart, Nils J. Nilsson, and Bertram Raphael in 1968, is an optimal path-finding algorithm that combines the benefits of Dijkstra's algorithm with heuristic guidance.
It efficiently finds the shortest path by balancing actual distance from the start with estimated distance to the goal.
The intuition behind the method
A* uses an evaluation function f(n) = g(n) + h(n), where g(n) is the actual cost from the start to node n, and h(n) is a heuristic estimate of the remaining cost to the goal. By exploring nodes with the lowest f(n) value, the algorithm efficiently narrows the search space toward the goal while maintaining optimality when the heuristic is admissible (never overestimates). This makes A* significantly faster than uninformed search methods while remaining guaranteed to find the optimal path.
History
Hart, Nilsson, and Raphael published A* in 1968, demonstrating that adding heuristic information to Dijkstra's algorithm could dramatically improve search efficiency while maintaining optimality. The algorithm became foundational in artificial intelligence and operations research. Subsequent developments include bidirectional A*, IDA* (iterative deepening), and various heuristic improvements. A* remains the standard choice for pathfinding in modern game engines and robotics systems.
When to use it
Apply A* when you need to find optimal paths in graphs where a good heuristic function is available. It is particularly effective for pathfinding in games, robotics, and route planning where informed search can substantially reduce computation. Use it when speed matters but optimality is required. For cases without a reliable heuristic, use Dijkstra's algorithm instead.
Limitations and considerations
- Optimality depends on the admissibility of the heuristic function
- Performance degrades significantly with poor or inadmissible heuristics
- Memory usage can be substantial in large search spaces (maintains open and closed sets)
- Requires explicit domain knowledge to design good heuristic functions
Source conditions do not replace independent scientific review or validation by an analysis engine.
Strengths
- Optimal pathfinding when the heuristic is admissible
- Much faster than Dijkstra or breadth-first search when good heuristics are available
- Flexible: works with any admissible heuristic function
- Well-suited for single-goal pathfinding problems
- Extensive real-world validation in games, robotics, and navigation systems
Applications
- Video game pathfinding: real-time NPC navigation in dynamic game environments
- Robot motion planning: optimal path planning for autonomous robots avoiding obstacles
- GPS navigation: computing efficient routes considering road networks and traffic
- Puzzle solving: finding optimal solutions in combinatorial problems like the 15-puzzle
- Network routing: determining efficient packet routes with link quality heuristics
- Bioinformatics: sequence alignment and protein structure prediction searches
How it works
How it works
Create an open set with the start node, set its g-value (cost from start) to zero, and calculate its h-value using the heuristic function.
Select the node with the lowest f-value from the open set, compute f-values for its unvisited neighbors, and add promising neighbors to the open set.
Continue expanding nodes until the goal is reached with the lowest f-value, which guarantees the optimal path; reconstruct the path by tracing parent pointers.
Common pitfalls
- Using an inadmissible heuristic that overestimates costs, leading to suboptimal paths
- Choosing a heuristic that is too simple or unrelated to the problem, reducing search efficiency
- Inefficient implementation of the open set (should use priority queue), causing slow node selection
Frequently asked questions
What is an admissible heuristic and why does it matter?
An admissible heuristic never overestimates the true cost to the goal. This property guarantees that A* finds the optimal path. If a heuristic overestimates, A* may miss shorter paths and return suboptimal solutions.
How do you design a good heuristic for a problem?
Good heuristics are based on domain knowledge and problem structure. For grid-based pathfinding, Manhattan or Euclidean distance works well. For more complex problems, consider relaxing constraints or using pattern databases to compute admissible heuristics.
What is the difference between A* and Dijkstra's algorithm?
Both find optimal paths, but A* uses a heuristic to prioritize exploration toward the goal, making it much faster when a good heuristic is available. Dijkstra explores uniformly in all directions and is safer when heuristics are unreliable.
Can A* guarantee finding the shortest path?
Yes, A* guarantees the shortest path when the heuristic is admissible (never overestimates true cost). With inadmissible heuristics, optimality is not guaranteed.
Related methods
Sources
Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107.
Open DOI referenceCopied.Russell, S. J., & Norvig, P. (2009). Artificial Intelligence: A Modern Approach (3rd ed.). Pearson.
ISBN: 978-0-13-604259-4Copied.