A* Search Algorithm Theory Guide
Try the A* Search Algorithm Solver →A* Algorithm, A star search, Pathfinding Calculator, Heuristic Search, g(n) + h(n) solver, Open List Closed List, Shortest Path
The A* (pronounced 'A-star') algorithm calculator and step-by-step solver is the gold standard for pathfinding and graph traversal in Artificial Intelligence. It acts like a smart GPS. Instead of blindly exploring every possible road (like Dijkstra's Algorithm) or greedily driving toward the destination regardless of traffic (like Greedy Best-First Search), A* perfectly balances the distance you have already traveled with an educated guess of the distance remaining. By using an Open List to track possibilities and a Closed List to remember dead ends, it guarantees the shortest possible path to your goal without wasting time.
The A* Evaluation Function
What do these variables mean?
- The total estimated cost of the cheapest path passing through node . A* always expands the node with the lowest first.
- The exact, known cost to reach node from the starting point (e.g., the actual distance traveled so far).
- The heuristic. This is an estimated cost to get from node to the goal. For A* to be perfectly optimal, must be 'admissible'—meaning it must never overestimate the true cost to reach the goal.
How Does it Work?
Initialize Lists: Create an empty 'Closed List' (for evaluated nodes) and an 'Open List' (for discovered but unevaluated nodes). Add the starting node to the Open List.
Pick the Best Node: Find the node in the Open List with the lowest total cost: . Pop it off the Open List.
Check for Goal: If this popped node is your target destination, the search is complete!
Close the Node: If it is not the goal, add this node to the Closed List so you never evaluate it again.
Expand Neighbors: Look at all directly connected neighbors of the popped node. Calculate their (parent's + edge cost) and their .
Update Lists: If a neighbor is not in the Open or Closed list, add it to the Open List. If it is already in the Open List but you just found a cheaper path to it, update its score. Repeat from Step 2.
Solved Example: Tracing the Open and Closed Lists
Finding the shortest path from Start (S) to Goal (G). Heuristics [h]: S=7, A=10, B=9, C=5, G=0. Edge costs [g]: S→A=1, S→B=1, A→B=9, B→C=6, B→G=12, C→G=5.
Step 1 (Start): We begin at S. The exact cost to S is 0. The heuristic is 7. Open List: [ S(0+7) = 7 ]. Closed List: [ Empty ].
Step 2 (Pop S): S has the lowest f(n). We pop it and check neighbors A and B. Path SA is 1+10=11. Path SB is 1+9=10. Open List: [ SB(10), SA(11) ]. Closed List: [ S(7) ].
Step 3 (Pop SB): SB (10) is the lowest. Neighbors of B are C and G. Path SBC is 1+6=7, plus h(5) = 12. Path SBG is 1+12=13, plus h(0) = 13. Open List: [ SA(11), SBC(12), SBG(13) ]. Closed List: [ S, SB ].
Step 4 (Pop SA): SA (11) is now the lowest in the list! Neighbor of A is B. Cost via A is 1+9=10. But we already found a cheaper way to B (cost 1). We ignore it. Open List: [ SBC(12), SBG(13) ]. Closed List: [ S, SB, SA ].
Step 5 (Pop SBC & Goal): SBC (12) is the lowest. Its neighbor is G. Path SBCG is 1+6+5=12, plus h(0) = 12. We pop SBCG(12). Since it's our Goal, we are done! Final Path: S → B → C → G. Total Cost: 12.
Student Tip: You can verify these exact manual calculations using our interactive A* Search Algorithm step-by-step solver. Simply plug in the values from the table above to see the logic in action.
Implementation Pseudocode
function AStar(start, goal):
open_list = [start]
closed_list = []
while open_list is not empty:
// Find node with lowest f(n) = g(n) + h(n)
current_node = node in open_list with lowest f(n)
if current_node == goal:
return reconstruct_path(current_node)
remove current_node from open_list
add current_node to closed_list
for each neighbor of current_node:
if neighbor in closed_list:
continue
tentative_g_score = current_node.g + distance(current_node, neighbor)
if neighbor not in open_list or tentative_g_score < neighbor.g:
neighbor.g = tentative_g_score
neighbor.f = neighbor.g + heuristic(neighbor, goal)
neighbor.parent = current_node
if neighbor not in open_list:
add neighbor to open_list
return "No Path Found"Rules & Common Mistakes
Exam Trap: Always pop the lowest f(n) from the ENTIRE Open List, not just from the children of the node you just expanded. A* jumps around the tree based purely on the lowest score.
If two nodes in the Open List have the exact same f(n) score, break the tie by picking the node with the lowest h(n). It is closer to the goal!
A heuristic is 'admissible' if it assumes straight-line distance (like a bird flying). It is 'inadmissible' if it accounts for traffic or detours that might not exist.
Advantages
- ✓ Guaranteed Optimality: As long as the heuristic does not overestimate, A* will absolutely find the shortest, most efficient path.
- ✓ Highly Efficient: It explores significantly fewer nodes than uninformed algorithms like Dijkstra's or Breadth-First Search.
Disadvantages
- × Memory Intensive: A* stores every single generated node in RAM (Open and Closed lists). On massive maps, it can easily run out of memory.
- × Heuristic Dependent: If you provide a bad heuristic, A* loses its speed and can perform worse than basic algorithms.
Algorithm Complexity
| Scenario | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Worst Case Time | Where 'b' is the branching factor and 'd' is the depth of the shortest path. This occurs if the heuristic is useless (e.g., h(n) = 0), turning A* into standard Breadth-First Search. | ||
| Best Case Time | Occurs when the heuristic is perfect. A* walks directly to the goal without exploring a single incorrect branch. | ||
| Space Complexity Concern | A* must keep all generated nodes in memory (in the Open and Closed lists). For massive maps, algorithms like IDA* (Iterative Deepening A*) are used to save RAM. |
A* Algorithm vs. Greedy Best-First Search
A* and Greedy Best-First Search both use heuristics to guess how far away the goal is, but they make radically different decisions about how to travel there.
- •The Formula: Greedy Best-First Search only cares about the heuristic (). A* cares about both the distance traveled and the heuristic ().
- •The Mindset: Greedy search is 'myopic'. It will blindly take a path that looks closer to the goal, even if it requires driving through a mountain with a massive edge cost. A* acts as a calculated planner, perfectly balancing the cost of the road with the direction of the destination.
- •The Guarantee: A* is mathematically guaranteed to find the shortest possible path (Optimal) and will never get stuck in infinite loops (Complete). Greedy Search is not optimal and can easily get trapped in dead-end loops on complex graphs.
Summary
The A* Algorithm represents the perfect harmony between brute-force calculation and educated guessing. By tracking the exact cost of the path taken so far and combining it with a conservative estimate of the journey ahead, A* efficiently narrows down its search area. It ignores routes that are clearly too expensive while guaranteeing it will never miss the absolute optimal path. Whether you are navigating a video game character through a maze or routing packets across the internet, A* remains the undisputed king of pathfinding.
Common Exam Questions & FAQ
+ What happens if my heuristic overestimates the distance?
If the heuristic is 'inadmissible' (meaning it guesses the goal is further away than it actually is), A* breaks its golden rule. It might settle for a sub-optimal path because it incorrectly calculates that the true optimal path is too expensive to explore. Always ensure your heuristic is optimistic!
+ Why do we need a Closed List in A* Search?
The Closed List acts as the algorithm's memory. In a graph with circular paths (e.g., A connects to B, and B connects back to A), A* would bounce back and forth infinitely. By placing a node in the Closed List after evaluating it, A* knows it has already found the absolute best path to that specific point and ignores it if it encounters it again.
+ How does A* handle ties in the Open List?
If two paths have the exact same f(n) score, the standard industry practice is to break the tie by choosing the node with the lowest h(n). Because its h(n) is lower, it is theoretically physically closer to the goal, making it a better immediate bet.
🎓 Core University Curriculum
This algorithm and its manual calculation methods are foundational requirements in leading Computer Science and Software Engineering programs worldwide. You will find this topic heavily featured in the syllabi of these standard AI courses:
Explore Related Algorithms
Try the Greedy Best-First Search Calculator
Run Greedy Best-First Search on custom graphs step-by-step and see exactly where omitting the path-cost term g(n) makes it faster but suboptimal compared to A*.
Greedy Best-First Search Theory
Compare the heuristic evaluation functions of A* and Greedy BFS: understand why A*'s admissible heuristic h(n) ≤ h*(n) guarantees the optimal path while Greedy's pure h(n) approach trades correctness for speed.