A* Search Algorithm
A* (pronounced "A-star") is an informed graph traversal and path-finding algorithm that finds the least-cost path from a start node to a goal node by combining the actual cost to reach a node with a heuristic estimate of the remaining distance to the goal. It is guaranteed to find the optimal path when the heuristic is admissible (never overestimates the true cost) and consistent. A* is widely used in game AI, robotics, GPS navigation, and network packet routing due to its efficiency and optimality guarantees.
Key Formula
f(n) = g(n) + h(n)
LaTeX: f(n) = g(n) + h(n)
| Symbol | Meaning | Unit |
|---|---|---|
| f(n) | Total estimated cost of the cheapest path through node n | cost units |
| g(n) | Actual cost from start node to current node n | cost units |
| h(n) | Heuristic estimate of cost from node n to goal | cost units |
Worked Example
Problem
On a 5×5 grid where each step costs 1, find the shortest path from (0,0) to (4,4) avoiding obstacle at (2,2). Use Manhattan distance as heuristic.
Solution
Step 1: Start at (0,0); f = g(0)+h(0) = 0+8 = 8. Open list: {(0,0)}. Step 2: Expand (0,0); add neighbours (1,0) and (0,1). g(1,0)=1, h=|4-1|+|4-0|=7, f=8; g(0,1)=1, h=|4-0|+|4-1|=7, f=8. Step 3: Expand (1,0); add (2,0) f=2+6=8, (1,1) f=2+6=8. Step 4: Continue expanding lowest-f nodes, skipping (2,2). Step 5: Optimal path found via (0,0)→(1,0)→(2,0)→(3,0)→(3,1)→(3,2)→(3,3)→(4,3)→(4,4) or diagonal-equivalent route of length 8.
Answer
Shortest path length = 8 steps (navigating around the obstacle at (2,2))
A* Algorithm Heuristic Functions and Their Properties
| Heuristic | Formula | Admissible? | Consistent? | Best For |
|---|---|---|---|---|
| Manhattan Distance | |x1-x2| + |y1-y2| | Yes (grid, 4-dir) | Yes | 4-directional grids |
| Euclidean Distance | sqrt((x1-x2)²+(y1-y2)²) | Yes | Yes | 8-directional / continuous space |
| Chebyshev Distance | max(|x1-x2|, |y1-y2|) | Yes (8-dir) | Yes | 8-directional grids |
| Zero Heuristic (Dijkstra) | h(n) = 0 | Yes | Yes | No heuristic info available |
| Inadmissible (Greedy) | h(n) > actual cost | No | No | Fast approximate solutions |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
The name "A*" derives from the notation used by Peter Hart, Nils Nilsson, and Bertram Raphael in their 1968 paper at SRI International. The asterisk (*) conventionally denotes the "best" or "optimal" variant of an algorithm class, distinguishing it from related heuristic search methods A1 and A2 described in the same paper.