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 maintains a priority queue of candidate paths and evaluates 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 depend 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 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 in robotics navigation, video game pathfinding, natural language processing, and network routing. Its adaptability, which lets developers 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 widely the algorithm's core insight, combining cost-so-far with informed estimation, has shaped computational problem-solving.