A* Search Algorithm
Also known as: A* algorithm, A-star algorithm, A* search
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.
Key highlights
- 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
Intuition
This section is available to Pro members. Upgrade to Pro
How it works
This section is available to Pro members. Upgrade to Pro
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.
Strengths & limitations
- 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
- 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
Common pitfalls
This section is available to Pro members. Upgrade to Pro
Applications
This section is available to Pro members. Upgrade to Pro
Frequently asked
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.
Sources
- 1.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.
- 2.Russell, S. J., & Norvig, P. (2009). Artificial Intelligence: A Modern Approach (3rd ed.). Pearson.ISBN 978-0-13-604259-4
You have read it. What now?
Cite this page
ScholarGate. (2026, June 3). A-star Search Algorithm. ScholarGate. https://scholargate.app/operations-research/a-star-search-algorithm