A* search is a graph-search algorithm that finds a lowest-cost path from a start point to a goal by combining the cost already incurred with an estimate of the remaining cost. It is widely used for pathfinding in software because a useful estimate helps it inspect fewer possible routes than uninformed search. Its result and efficiency depend heavily on the quality and correctness of its heuristic function.
A* search
What Is A* Search?
A* search is a graph-search algorithm that finds a lowest-cost path from a start point to a goal. It combines the cost traveled with an estimate of the remaining cost to prioritize promising routes.
A graph contains connected nodes, such as game-map squares or planning states. Connections can represent distance, time, or risk. A* searches these structured problems, not text in documents or web pages.
How the A* Search Algorithm Works
A* ranks candidate nodes with f(n) = g(n) + h(n). The g value is the known cost from the start, h estimates the cost to the goal, and f estimates total cost.
- Put the starting node in an open set, usually a min-priority queue.
- Select the node with the lowest f value.
- If it is the goal, reconstruct the path from parent links.
- Check neighbors and calculate each new g cost.
- Update a neighbor when the new route is cheaper.
Choosing a Good Heuristic
A heuristic is admissible if it never overestimates remaining cost. It is consistent if its estimate does not fall by more than one move's cost. These properties help A* find a shortest path. On a grid with horizontal and vertical moves, Manhattan distance counts horizontal plus vertical steps. Euclidean distance better fits straight-line movement. If h(n) is zero, A* becomes Dijkstra's algorithm.
A* Search vs. Dijkstra's Algorithm and Greedy Best-First Search
These algorithms differ mainly in how they choose the next node.
| Algorithm | Decision rule | Shortest-path guarantee | Best use |
|---|---|---|---|
| A* algorithm | g + h | Yes, with a suitable heuristic | Goal-directed pathfinding |
| Dijkstra's algorithm | g only | Yes, for nonnegative costs | Paths to many destinations |
| Greedy best-first search | h only | No | Fast approximate exploration |
Benefits of A* Search
A* is practical and precise when its heuristic fits the problem.
- It explores toward the goal instead of uniformly in all directions.
- It can find optimal paths with admissible heuristics and nonnegative edge costs.
- It supports distance, time, and penalty costs.
- It is used in game navigation, robotics, route planning, and state-space search.
Practical Limits of A* Search
Performance depends on the graph and heuristic.
- Large open sets can require substantial memory.
- A weak heuristic makes A* similar to Dijkstra's algorithm.
- Changing maps or costs may require a new search or incremental method.
- Negative edge costs do not fit standard A* assumptions.
- Inconsistent heuristics may require reopening nodes when a better route appears.
Implementation and Testing Tips
Correct bookkeeping is essential.
- Use a min-priority queue and store each node's best-known g value.
- Keep parent links to reconstruct the route.
- Ignore stale queue entries whose cost is no longer current.
- Test blocked and unreachable goals, equal-cost routes, and known shortest paths.
- For very large graphs, consider bidirectional search, hierarchical routing, or a domain-specific method.
A* Search in AI Application Development
A* is useful when an application must navigate explicit routes or states. It differs from retrieval methods such as semantic search and vector search, which find information by meaning or similarity rather than calculate graph routes. Emergent can help teams build, test, and deploy applications with the appropriate search workflow and interface.
Start Building
on Emergent today
on Emergent today
Start Building
