A* Search Algorithm: Step-by-Step Worked Example, Heuristics and Exam Traps

You may remember that A* combines path cost with a heuristic, yet lose track of which node leaves OPEN next, when a parent must change, or why the first generated goal is not automatically final. A* ranks a frontier node n by f(n)=g(n)+h(n), balancing cost already paid with estimated cost still remaining. Admissibility prevents h from overestimating; consistency constrains h across every edge; relaxation replaces a parent when a cheaper g appears.

A* search algorithm: what g, h and f mean

An A* problem has a start, goals, directed weighted edges and non-negative costs. g(n) is the cheapest discovered start-to-n cost, h(n) estimates the remaining goal cost, and f(n)=g(n)+h(n) estimates total cost through n. OPEN stores frontier nodes; CLOSED stores expanded nodes.

Put the start in OPEN with g(start)=0. Pop the minimum-f node. If it is a goal, reconstruct through parents. Otherwise relax its outgoing edges: insert an unseen neighbour, or lower its g and update its parent for a cheaper route. Break ties by lower f, lower h, then alphabetical label.

Search Algorithms in AI: BFS, DFS, UCS and A* on One Graph compares five strategies on the same weighted graph. A* adds goal direction through h, while a reliable deep trace must preserve g, f and parent changes as frontier costs improve.

A* heuristics: admissibility, consistency and the greedy boundary

An admissible heuristic satisfies 0 <= h(n) <= h*(n), where h*(n) is the true cheapest remaining cost. A consistent heuristic satisfies h(n) <= c(n,n')+h(n') on every directed edge, with h(goal)=0. Consistency implies admissibility for nodes that can reach a goal and makes f non-decreasing along a path. An admissible but inconsistent heuristic can require reopening a CLOSED node after a better g is found.

Fundamentals of Heuristic Search: A* Worked Example and Exam Traps compares Greedy Best-First and A* on one frontier and explains why their returned costs differ. A deeper A* trace must also retain every relaxation, parent change, OPEN/CLOSED state and expansion-count effect of heuristic strength. Take S->X=1, X->G=100, S->Y=10, Y->G=10, with h(X)=1, h(Y)=5, h(G)=0. Greedy chooses X, then G, and returns cost 101. A* explores X first at f=2, but retains Y at f=15. It expands Y before the expensive goal at f=101, improves G to cost 20, and returns optimal path S-Y-G.

A* worked graph: exact edges and heuristic values

The graph is directed and weighted. Its edges are S->A=1, S->B=4, A->C=2, A->D=5, B->C=2, B->D=1, C->G=5 and D->G=2. The start is S, the only goal is G, and every cost is non-negative.

Keep these values fixed while following OPEN, CLOSED and every parent update.

A* search worked example: OPEN, CLOSED and parent updates

Each (g,h,f) tuple uses the fixed tie-break.

Lower h resolves the f=7 ties as B before C, then D before C. Parents G<-D<-B<-S produce S-B-D-G, cost 4+1+2=7; C stays OPEN.

Every complete route confirms it: S-A-C-G=1+2+5=8, S-A-D-G=1+5+2=8, S-B-C-G=4+2+5=11, and S-B-D-G=4+1+2=7. Thus S-B-D-G is uniquely cheapest.

Why A* is optimal here, and what a stronger heuristic changes

Admissibility follows directly: 6<=7, 5<=7, 3<=3, 4<=5, 2<=2, 0<=0. Consistency also holds on all eight edges: 6<=1+5, 6<=4+3, 5<=2+4, 5<=5+2, 3<=2+4, 3<=1+2, 4<=5+0, and 2<=2+0. Because the heuristic is consistent and we stop only when the goal is popped, CLOSED nodes need not reopen and the returned cost is 7.

Under the same tie rule, setting every h to zero makes uniform-cost search pop S,A,C,B,D,G, six nodes. The heuristic values above make A* pop S,A,B,D,G, five nodes. The perfect heuristic h=h* gives S,B,D,G, four nodes. A more informed admissible heuristic can reduce work, although A* can still require exponential time and memory in difficult state spaces. Tie-breaking may change which equal-f nodes expand without changing the least-cost result under these conditions.

A* search algorithm traps: where a correct formula still goes wrong

The trace shows C at g=3 and D at g=5, but their f=7 tie sends lower-h D first. Update OPEN after every improved g.

If h is admissible but inconsistent, never reopening CLOSED can lose optimality. Require consistency or reopen on a lower g. Any overestimate breaks admissibility, even if the path found is optimal.

A* search exam patterns: calculations and concept checks

Assessments can ask you to calculate g,h,f, choose the next OPEN node under a tie-break, relax a cheaper route, reconstruct parents, test a heuristic, or distinguish A*, uniform-cost and greedy best-first search. UGC NET CS Exam Preparation is a broader study route, not an official syllabus source.

Test the worked graph immediately:

1. After A expands, what is OPEN? B(4,3,7), C(3,4,7), D(6,2,8).

2. Does B->C improve C? No. Candidate g=6 is worse than 3.

3. What changes on B->D? g:6->5, f:8->7, parent A->B.

4. Is h(B)=4 admissible? No, because h*(B)=3.

5. What remains when every h is zero? Uniform-cost search, equivalent to Dijkstra's selection rule for non-negative edges.

Practise until you can rebuild OPEN, CLOSED and every parent pointer for this graph without looking back at the trace table.

A* search algorithm: the short version and next step

Remember: g is paid cost, h is estimated remaining cost, and f=g+h ranks OPEN. Admissibility forbids overestimation. Consistency enforces the edge triangle inequality. Relaxation can change both cost and parent. Under the stated optimality conditions, the goal is final when removed from OPEN.

For mastery, redraw all eight edges and six heuristic labels, reproduce S,A,B,D,G, explain the D update, derive S-B-D-G, and compare cost 7 with the other routes. Then use NTA-UGC-NET Paper - 2 for a curriculum that includes Artificial Intelligence and Search Algorithms, or AI & ML for Placements | Generative AI Placement Course for a broader applied AI route.