AI Glossary / AI and machine learning / Intermediate
A* algorithm
Definition
A* is a search algorithm that finds the lowest-cost path from a starting point to a goal by combining two numbers for each option: the known cost so far and an estimate of the cost still to go.
What it means
Imagine finding the best route across a city. A naive search explores streets in every direction equally. A* explores toward the goal: it always expands the option whose total estimated journey, distance already traveled plus estimated distance remaining, looks shortest.
The estimate, called the heuristic, is the algorithm's compass. A good heuristic, like straight-line distance for road trips, steers the search so it examines far fewer options than a blind search while still finding the best path.
A* carries a famous guarantee: if the heuristic never overestimates the true remaining cost, the first path A* returns is optimal. An optimistic compass cannot mislead it into a worse answer, only make it search a little more.
The algorithm is decades old and still everywhere: route planners, game characters finding their way across maps, network routing, puzzle solvers and robot motion all lean on it or its descendants.
For a business reader, A* is the canonical example of a bigger idea: a sensible estimate of remaining effort turns an impossibly large search into a practical one, and the quality of the estimate decides the speed, not the correctness.
How it works
A* keeps a frontier of partially explored paths. Each is scored as g, the exact cost from the start to the current point, plus h, the heuristic estimate from there to the goal. The frontier entry with the lowest total is expanded next.
Because g is measured, not guessed, the search stays honest about what it has spent. Because h points toward the goal, it avoids wandering. The balance of the two is the whole idea.
The heuristic must be admissible, never overestimating the true cost, for the optimality guarantee to hold. Straight-line distance works for maps because real roads can only be longer.
When the search space is too large for memory, variants bound the frontier or accept slightly suboptimal paths with a weighted heuristic, trading a little path quality for a lot of speed.
Three practical examples
- Delivery routing: find the shortest route through today's stops, using straight-line distance as the estimate of what remains.
- Games: a character finds its way around obstacles to reach the player, replanning when doors close.
- Logistics: sequence warehouse picks to minimize travel, estimating remaining distance to the dispatch point.
Think of it this way
Think of walking toward a visible clock tower in an unfamiliar city. You keep count of how far you have walked, and at each corner you favor the turn that points at the tower. You are running A* with your eyes as the heuristic.
The limit: if the tower is not actually your destination, the compass misleads you efficiently. A heuristic helps only when it genuinely correlates with the true remaining cost.
Worked example
planning one courier route
Suppose a courier must reach an address across a grid of one-way streets. A blind search explores thousands of street segments; the courier wants an answer in seconds.
A* scores each candidate junction by distance driven so far plus straight-line distance to the address. Junctions that lead away from the goal drop down the list automatically, and the search concentrates on promising corridors.
Because straight-line distance never overestimates real driving distance, the route A* returns is provably the shortest on the map used. The scenario is invented; g plus h with an admissible estimate is the exact mechanism.
When a road closure changes the true costs, the search is rerun with the updated map: the guarantee covers the map, not the weather.
Illustrative case study
A fictional game studio finds its characters taking bizarre detours around a new obstacle type. The pathfinding is A*, untouched for years, and the bug hunt starts in the wrong place: the search code.
The real fault is the map data: the new obstacles were never marked as blocked, so the heuristic and the cost function both assumed open ground. Correcting the map fixes every detour at once.
The invented lesson: search algorithms are hostage to their world model, exactly as planning agents are. When paths look stupid, inspect the map before the algorithm.
Common misconceptions and mistakes
- A* is machine learning. It is classic search: no training, no data, just a cost function and an estimate.
- The heuristic must be accurate. It must merely never overestimate for the guarantee; accuracy affects speed, not correctness.
- A* always finds the true best route. It finds the best route on the model it is given; a wrong map yields the best path through a fiction.
Business use
You will rarely implement A*, but you use it constantly in routing, scheduling and planning tools. Knowing its shape tells you what to ask: what is the cost function, what is the estimate, how current is the map?
When a routing or planning tool gives strange answers, check its underlying data and cost settings before blaming the engine. The search is usually doing exactly what the inputs imply.
People also ask
What does the star mean?
It is just the name from the 1968 paper that introduced it, marking an improved version of an earlier algorithm.
Is A* still used?
Yes, widely: maps, games, robotics and network routing, plus many descendants for larger spaces.
What breaks the optimality guarantee?
A heuristic that overestimates the true remaining cost, or a map whose costs are wrong.
Check your understanding
A route planner returns strange detours after new obstacles were added. The search code is unchanged. Where should the investigation start and why?
Answer: In the map data: A* optimizes over the model it is given, so unmarked obstacles make both the costs and the heuristic wrong.
Related terms
Learn next
AI for Business Owners covers how to question planning and routing tools sensibly: https://aiforbusinessandlife.com/academy/ai-for-business-owners. It is an adoption course, not an algorithms course. [C2]
More in AI and machine learning
- (1+ε)-approximate nearest neighbor search - A (1+epsilon)-approximate nearest neighbor search returns a data point whose distance from a query is at most 1+epsilon times the distance of the true...
- Ablation - An ablation is a controlled experiment that removes one part of a model or system and measures what changes, to learn how much that part actually contributes.
- Abstractive Summarization - Abstractive summarization is generating a summary in new words that capture the meaning of the source, rather than selecting and copying the source's own...
- Accumulated local effects - Accumulated local effects, or ALE, describe how a fitted model's predictions change with a feature by averaging local prediction differences and...
- Action - In AI, an action is anything an agent can do that changes its environment or its relationship to it: moving, sending, writing, booking, buying.
- Action model learning - Action model learning is the process of learning descriptions of what actions require and how they change an environment.
Sources
[S9] NetworkX documentation, astar_path. Full URLs are in the source ledger. Verified 11 October 2026.
Previous: 842 (compression algorithm) Next: A/B testing