A* Search Algorithm
- Definition
- A* is a pathfinding algorithm that finds the least-cost path between nodes by combining the cost so far with a heuristic estimate of remaining cost. It is efficient and optimal when the heuristic is admissible (never overestimates). S, visualize expanding nodes in a grid while using a guess for distance-to-go; A* prioritizes nodes that look promising. It differs from uninformed searches (like Dijkstra) by using heuristics to guide the search and from local optimizers that don't guarantee shortest overall paths.
How does it work?
A* expands nodes from a priority queue ordered by cost-so-far plus heuristic estimate. Implement it by maintaining open and closed sets, updating costs when better paths are found, and ensuring the heuristic is admissible for optimality. Efficient implementations use appropriate data structures for the frontier.
Examples
- Game AI pathfinding — Find shortest paths for NPCs on grid maps using admissible heuristics like Manhattan distance.
- Robot motion planning — Compute collision-free routes in discretized maps with heuristics to focus search.
- Route planning in maps — Combine road network costs and heuristic estimates for efficient navigation on graphs.
Problems
- Memory blow-up storing the open/closed sets on large graphs
- Poor performance if the heuristic isn't admissible or well-designed
- Ties and near-equal costs causing unnecessary node expansion
- Difficulty adapting to dynamic graphs where edge weights change
- Heuristic computation itself becoming a bottleneck