A* Search Algorithm - Complete AI Guide

Introduction

A* (pronounced "A-star") is the most widely used pathfinding algorithm in artificial intelligence. Developed by Peter Hart, Nils Nilsson, and Bertram Raphael in 1968, it finds the shortest path between nodes in a weighted graph by intelligently combining two pieces of information: the actual cost paid to reach a node and an estimate of the remaining cost to the goal.

What makes A* special is its guarantee: with a proper heuristic, it finds the optimal solution while expanding the minimum number of nodes necessary. No other algorithm using the same heuristic can do better—A* is optimally efficient.

The Evaluation Function

A* uses the evaluation function:

f(n) = g(n) + h(n)

Where:

• g(n) = actual cost from start to node n (known exactly)
• h(n) = heuristic estimate from node n to goal (approximation)
• f(n) = estimated total cost of cheapest solution through n

The algorithm maintains a priority queue (open list) ordered by f(n), always expanding the node with the lowest estimated total cost.

Algorithm Pseudocode

Complete Worked Example

Consider this weighted graph for route planning:

Step-by-Step Trace

Notice how A* never expanded B or C—the heuristic guided it directly to the optimal path. BFS would have expanded all nodes at each level.

Admissibility and Optimality

Admissible Heuristic

A heuristic h(n) is admissible if it never overestimates the true cost:

**h(n) ≤ h*(n) for all nodes n**

where h*(n) is the actual cheapest cost from n to the goal.

Theorem: If h is admissible, A* with tree-search is optimal.

Consistent (Monotone) Heuristic

A heuristic is consistent if for every node n and successor n':

h(n) ≤ cost(n, n') + h(n')

This is the triangle inequality. Consistency implies admissibility, and with graph-search (closed list), consistency guarantees optimality and that no node is ever re-expanded.

Proof Sketch of Optimality

Suppose A* expands a suboptimal goal G₂ (cost C₂ > C*). There must be a node n on the optimal path still in the open list. Since h is admissible:

• f(n) = g(n) + h(n) ≤ g(n) + h*(n) = C*
• f(G₂) = g(G₂) + 0 = C₂ > C*
• Therefore f(n) < f(G₂), so A* would expand n before G₂. Contradiction.

Common Heuristics by Domain

Grid Navigation (4-directional movement)

Grid Navigation (8-directional movement)

Road Networks

8-Puzzle

A* Properties

Memory-Efficient Variants

A*'s main weakness is memory—it stores all generated nodes.

IDA* (Iterative Deepening A*)

Uses f-cost threshold instead of depth limit. Memory: O(bd). Re-expands nodes but practical for puzzles.

SMA* (Simplified Memory-Bounded A*)

Uses all available memory, drops highest-f nodes when full. Maintains optimality if memory suffices for the solution path.

RBFS (Recursive Best-First Search)

Linear space like IDA* but smarter about re-expansion. Backs up f-values to remember the best alternative path.

Implementation Considerations

Priority Queue Choice

• Binary heap: O(log n) insert/extract
• Fibonacci heap: O(1) amortized decrease-key
• In practice, binary heap wins due to cache efficiency

Tie-Breaking

When f-values are equal, prefer nodes with higher g (closer to goal). This reduces unnecessary exploration of equal-f nodes.

Handling Re-expansion

With consistent heuristics, nodes are never re-expanded (closed list is safe). With only admissible heuristics, you may need to re-open closed nodes if a cheaper path is found—more complex but still correct.

A* vs. Dijkstra's Algorithm

Dijkstra's algorithm is A* with h(n) = 0 everywhere. Without heuristic guidance, Dijkstra expands all nodes with cost ≤ C* before finding the goal. A* uses the heuristic to focus expansion toward the goal, potentially exploring far fewer nodes.

Common Interview Questions

**Q: Can A* be used with inadmissible heuristics?** A: Yes, but optimality is lost. Weighted A* uses f(n) = g(n) + w·h(n) where w > 1 to trade optimality for speed. The solution cost is at most w times optimal.

Q: What happens when h(n) = 0 for all n? A: A* degenerates to Uniform Cost Search (Dijkstra's). Still optimal but explores more nodes.

**Q: What happens when h(n) = h*(n) (perfect heuristic)?** A: A* goes directly to the goal without expanding any unnecessary nodes. Zero wasted expansion—but computing h* is usually as hard as solving the problem.