A* Search

A* Search is a best-first graph traversal and pathfinding algorithm that finds the least-cost path between a start node and a goal node. It works by maintaining a priority queue of candidate paths and evaluating each node using the function f(n) = g(n) + h(n), where g(n) represents the known cost from the start to the current node, and h(n) is a heuristic estimate of the remaining cost to the goal. By combining these two components, A* balances the thoroughness of Dijkstra's algorithm with the directional efficiency of greedy best-first search, avoiding unnecessary exploration while still guaranteeing an optimal solution.

The algorithm's correctness and efficiency hinge on the properties of its heuristic. When h(n) is admissible — meaning it never overestimates the true cost to the goal — A* is guaranteed to find the optimal path. When h(n) is also consistent (satisfying a triangle inequality across nodes), A* avoids redundant re-evaluation of nodes, improving runtime performance. The choice of heuristic is therefore domain-specific: Manhattan distance works well for grid-based maps, while Euclidean distance suits continuous spaces. A poorly chosen heuristic can degrade A* to the performance of an exhaustive search.

A* has become a foundational tool in AI planning and search, with applications spanning robotics navigation, video game pathfinding, natural language processing, and network routing. Its adaptability — allowing developers to tune the heuristic for speed versus optimality trade-offs — makes it broadly applicable across problem domains. Variants such as weighted A*, IDA* (iterative deepening A*), and bidirectional A* extend the core algorithm to handle memory constraints, real-time requirements, and large-scale graphs.

In machine learning and AI pipelines, A* frequently appears in structured prediction, symbolic planning, and model-based reinforcement learning, where agents must reason over discrete state spaces. Its influence on modern search-based methods, including beam search in sequence modeling and Monte Carlo Tree Search in game-playing systems, reflects how deeply the algorithm's core insight — combining cost-so-far with informed estimation — has shaped computational problem-solving.