DataTerminology.comNEW
Also known as: A-star algorithm
Best-first graph search algorithm using heuristics to find optimal paths when the heuristic is admissible and consistent.
DESCRIPTION
A* search finds least-cost paths by combining actual cost from the start (g) with a heuristic estimate to the goal (h) to prioritize nodes by f=g+h. With an admissible, consistent heuristic, A* guarantees optimality and expands fewer nodes than uninformed searches. It underpins routing, robotics, and game pathfinding. Variants like weighted A* trade optimality for speed; IDA* reduces memory at the cost of repeated work. Performance depends on heuristic quality: tighter estimates cut expansions. Implementations require careful data structures (priority queues) and closed-set handling to avoid re-expanding states.
ALTERNATIVE DEFINITIONS
Wikipedia
A* is a graph traversal and path search algorithm that finds the least-cost path from a given initial node to a goal node, as long as the heuristic is admissible.
Connects optimality to heuristic admissibility in pathfinding.
Stanford University
A* search orders node expansion by f(n) = g(n) + h(n), where g is the path cost so far and h is a heuristic estimate to the goal.
Formalizes the evaluation function and its components.
MIT OpenCourseWare
A* uses a best-first strategy guided by the sum of path cost and heuristic to efficiently find optimal solutions with good heuristics.
Emphasizes efficiency gains with informative heuristics.
RELATED TERMS
Heuristic Admissible Heuristic Consistent Heuristic Best-First Search Pathfinding Graph Traversal IDA-star Weighted A-star Manhattan Distance
COMPETING TERMS
Dijkstra’s Algorithm Greedy Best-First Search
RELATIONS
- Broader: Best-First Search Graph Traversal Search
KNOWLEDGE AREAS
AI Mathematics Data Science Software Engineering
TARGET AUDIENCE
AI Engineer Software Developer Data Scientist
EXTERNAL SOURCES
- Wikipedia - A* search algorithm
- Red Blob Games - Visual A* tutorial
- Stanford University - Heuristics and A* comparison
TOP QUESTIONS
When is A* Search optimal?
When the heuristic is admissible (never overestimates) and consistent, A* returns an optimal path.
Category: Requirements
How does A* compare to Dijkstra’s Algorithm?
A* uses heuristics to focus search and typically expands fewer nodes; Dijkstra’s is heuristic-free and explores uniformly by distance.
Category: Distinction
What is a common mistake implementing A* Search?
Failing to maintain a closed set or not updating priorities when better paths are found leads to suboptimal or inefficient search.
Category: Mistakes
How do heuristics affect A* performance?
More informed (closer to true cost) heuristics reduce expansions. Overestimation breaks optimality.
Category: Performance
What are practical applications of A* Search?
Navigation, robotics, network routing, and game AI commonly use A* for pathfinding.
Category: Application
What is IDA* and when to use it?
Iterative Deepening A* reduces memory by iterative cost thresholds, useful on memory-constrained problems.
Category: Alternatives
How does Weighted A* differ?
It scales h(n) by a factor >1 to speed up at the cost of optimality guarantees.
Category: Distinction
What data structures are essential for A*?
A priority queue (min-heap) for the open set and a hash set for the closed set are typical.
Category: Requirements
How do you choose a heuristic for grids?
Use Manhattan distance for 4-directional moves or diagonal/Euclidean for 8-way movement, consistent with cost model.
Category: Best practices