A* Search
A* finds a least-cost route to one goal by ordering candidates with f(n)=g(n)+h(n): known cost so far plus a defensible estimate of the remaining cost.
From Dijkstra to informed search
Dijkstra expands the smallest known path cost g and therefore explores equally cheap directions even when most lead away from the goal. A* adds h, a domain estimate of cost from a state to the goal, and expands the smallest f=g+h. The g term preserves evidence already paid for; h supplies direction.
A* targets one goal rather than computing every source distance. With h=0 its order is exactly uniform-cost search. Using only h produces greedy best-first search, which may rush toward a visually close but expensive route because it ignores the cost already accumulated.
- g is exact past cost
- h estimates future cost
- f balances evidence and direction
Admissibility and consistency
An admissible heuristic never exceeds the true remaining optimum. Consistency is the edge-wise triangle inequality h(u)≤w(u,v)+h(v), with h(goal)=0. Consistency implies admissibility and makes f nondecreasing along a path, so graph-search A* may safely finalize a vertex when its fresh heap entry is removed.
With an admissible but inconsistent heuristic, an implementation that permanently closes vertices can be wrong; it must reopen a closed state when a cheaper g appears. Manhattan distance is consistent for four-direction unit grids. Euclidean distance fits unrestricted straight-line movement when edge costs dominate geometric length.
- Admissible means optimistic
- Consistent means every edge respects the estimate
- Reopen states if consistency is not guaranteed
Terms, operations, and practical uses
Search scores
- g-scoreg-score is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- Heuristic hHeuristic h is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- f-scoref-score is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Correctness
- AdmissibilityAdmissibility is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- ConsistencyConsistency is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- State reopeningState reopening is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Implementation
- Open setOpen set is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- Stale heap entryStale heap entry is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- Parent mapParent map is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
A* orders the frontier by g+h
import heapq
g={"S":[("A",2),("B",4)],"A":[("C",2)],"B":[("C",1)],"C":[("G",2)],"G":[]}
h={"S":5,"A":4,"B":2,"C":2,"G":0}
dist={v:10**9 for v in g};dist["S"]=0
q=[(h["S"],0,"S")]
while q:
f,d,u=heapq.heappop(q)
if d!=dist[u]: continue
if u=="G": break
for v,w in g[u]:
nd=d+w
if nd<dist[v]:
dist[v]=nd;heapq.heappush(q,(nd+h[v],nd,v))
print("Path cost:",dist["G"])#include <algorithm>
#include <array>
#include <cstring>
#include <functional>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
int main() {
vector<vector<pair<int,int>>> g={{{1,2},{2,4}},{{3,2}},{{3,1}},{{4,2}}, {}};
vector<int> h={5,4,2,2,0}, d(5,1e9);
priority_queue<array<int,3>,vector<array<int,3>>,greater<array<int,3>>> q;
d[0]=0;
q.push({h[0],0,0});
while(!q.empty()) {
auto [f,du,u]=q.top();
q.pop();
if(du!=d[u]) continue;
if(u==4) break;
for(auto [v,w]:g[u]) if(du+w<d[v]) {
d[v]=du+w;
q.push({d[v]+h[v],d[v],v});
}
}
cout << "Path cost: " << d[4] << '\n';
}import java.util.*;
class Main {
record Edge(int to,int w) {
}
record State(int f,int g,int u) {
}
public static void main(String[] args) {
List<Edge>[] graph=new List[5];
for(int i=0;i<5;i++) graph[i]=new ArrayList<>();
graph[0].add(new Edge(1,2));
graph[0].add(new Edge(2,4));
graph[1].add(new Edge(3,2));
graph[2].add(new Edge(3,1));
graph[3].add(new Edge(4,2));
int[] h={5,4,2,2,0}, dist={0,1_000_000_000,1_000_000_000,1_000_000_000,1_000_000_000};
PriorityQueue<State> open=new PriorityQueue<>(Comparator.comparingInt(State::f));
open.add(new State(h[0],0,0));
while(!open.isEmpty()) {
State s=open.remove();
if(s.g()!=dist[s.u()]) continue;
if(s.u()==4) break;
for(Edge e:graph[s.u()]) if(s.g()+e.w()<dist[e.to()]) {
dist[e.to()]=s.g()+e.w();
open.add(new State(dist[e.to()]+h[e.to()],dist[e.to()],e.to()));
}
}
System.out.println("Path cost: "+dist[4]);
}
}Step through it
Running on weighted map S to G
The open set and relaxation
Store (f,g,node) entries in a min-heap, the best g per state, and a parent map. Pop the smallest f, discard stale entries whose g differs from the table, and relax each outgoing edge. A better tentative g updates the table, parent, and a new heap entry with tentative+h(neighbor).
Stop only when the goal is popped with its current g. Discovering or inserting the goal is not enough: another frontier state may still lead to it more cheaply. Parent pointers recover the route backward. If the heap empties first, the goal is unreachable from the start.
- Lazy deletion handles decreased priorities
- Relax using tentative g
- Terminate on a fresh goal pop
Designing a useful heuristic
A heuristic should be cheap, informative, and a lower bound. Solve a relaxed problem obtained by removing constraints: its optimum cannot exceed the constrained optimum. The maximum of several admissible heuristics remains admissible and dominates each one, often reducing expansions without weakening correctness.
Scale must match edge costs. Raw Manhattan distance overestimates if a grid step can cost less than one; multiply by the minimum possible step cost. Obstacles may make a geometric lower bound weak but not invalid. Weighted A* multiplies h to trade optimality for speed and must be described as approximate.
- Relax constraints to obtain lower bounds
- Larger safe estimates usually expand fewer states
- Units and minimum edge cost must agree
Complexity and failure cases
Worst-case A* still explores the reachable state space: O((V+E)log V) with adjacency lists and a binary heap, plus O(V) tables. Its practical advantage is fewer expansions, not a better universal asymptotic bound. Memory can dominate because the open and closed sets retain many frontier states.
Test start equal to goal, unreachable goals, equal-cost alternatives, stale heap entries, a heuristic of zero, and a deliberately inconsistent heuristic that requires reopening. Negative edges invalidate the Dijkstra-style finalization foundation; use Bellman–Ford-family methods or reformulate the costs instead.
- Worst case matches heap-based graph search
- Memory grows with the frontier
- Negative edges require different machinery
Operational checklist
Keep separate best-g and parent maps; f is only a queue priority and must not replace the proven path cost. A heap may contain several entries for one state, so compare the popped g with the table before expansion. Tie-breaking toward larger g can reduce plateaus without changing optimality under the same heuristic assumptions.
Measure both path cost and expanded-state count when evaluating a heuristic. A heuristic can be correct yet too expensive to compute, erasing its savings. Cache deterministic heuristic values, validate h(goal)=0, and sample every edge to check consistency before relying on a permanent closed set.
- Store g independently from f
- Discard stale queue entries
- Validate heuristic cost and consistency