A* Search is an informed search algorithm that combines the strengths of Dijkstra's algorithm and greedy best-first search. It uses both the cost to reach a node (g-score) and a heuristic estimate of the remaining cost to the goal (h-score) to guide its search, making it both complete and optimal when using an admissible heuristic.
Key Components:
- f(n) = g(n) + h(n) - Evaluation function that determines node exploration order
- g(n) - Cost to reach node n from the start node
- h(n) - Heuristic estimate of cost from node n to the goal
- Open Set - Nodes discovered but not yet evaluated (frontier)
- Closed Set - Nodes already evaluated
The A* Algorithm:
- Initialize open set with start node
- Loop until goal is found or open set is empty:
- Select node with lowest f-score from open set
- If this node is the goal, reconstruct and return path
- Move node from open set to closed set
- For each neighbor of the current node:
- If neighbor is in closed set, skip it
- Calculate tentative g-score via current node
- If neighbor is not in open set or has better g-score:
- Update neighbor's g-score and parent
- Calculate f-score = g-score + h-score
- Add neighbor to open set if not already present
- If open set is empty, no path exists
Common Heuristics:
-
Manhattan Distance: |x1 - x2| + |y1 - y2|
Optimal for 4-directional movement (no diagonals)
-
Euclidean Distance: √[(x1 - x2)² + (y1 - y2)²]
Works well with unrestricted movement
-
Chebyshev Distance: max(|x1 - x2|, |y1 - y2|)
Optimal for 8-directional movement with same cost in all directions
-
Octile Distance: |x1 - x2| + |y1 - y2| + (√2 - 2) × min(|x1 - x2|, |y1 - y2|)
Optimal for 8-directional movement where diagonal cost is √2
Properties of A* Search:
- Complete: Always finds a path if one exists (assuming positive edge weights)
- Optimal: Finds the optimal path when using an admissible heuristic
- Admissible Heuristic: Never overestimates the true cost to the goal
- Consistent Heuristic: For any nodes n and m, h(n) ≤ d(n,m) + h(m), where d(n,m) is the cost from n to m
- Efficiency: More efficient than Dijkstra's algorithm by using heuristic guidance
Variations and Applications:
- Weighted A*: Uses w × h(n) with w > 1 to find solutions faster (might not be optimal)
- IDA*: Iterative deepening version that uses less memory
- Applications: Robotics, video games, GPS navigation, puzzle solving, network routing