Fundamentals of Heuristic Search: A* Worked Example and Exam Traps

The labels h(n), g(n) and f(n) can look interchangeable until two search algorithms choose different nodes from the same frontier. That is where memorised definitions stop helping, especially under a short exam time limit. Greedy Best-First Search uses h(n), whereas A* uses g(n)+h(n); exact admissibility and consistency checks prevent common exam mistakes.

What a heuristic search problem actually contains

A search problem has a state space, a start state, a goal test, and successors reached through edges or actions. Each edge can have a step cost. The accumulated cost from the start to node n is g(n), while h(n) estimates the cheapest remaining cost from n to a goal. An evaluation function f(n) decides how the frontier is ranked.

Keep the units consistent. If edge costs measure distance, g and h must both measure distance. An estimate in minutes cannot be added to a distance in kilometres.

Uninformed search ranks nodes without a goal-directed estimate. Informed search uses h(n) to guide the choice. A useful boundary case is h(n) = 0 for every node. A* then ranks only by g(n) and behaves like Uniform Cost Search when edge costs are non-negative. If graph representation and frontier handling need revision, start with Graph Algorithms: BFS, DFS and Shortest Paths.

Greedy Best-First Search and A* use the heuristic differently

Consider a frontier containing P(g=1,h=5,f=6), Q(g=5,h=2,f=7) and R(g=4,h=3,f=7). Greedy chooses Q because its h is 2. A* chooses P because its f is 6. For every tie below, use lower h first, then alphabetical node label.

Greedy's choice resembles a local-choice strategy, but that does not make it the same as a greedy optimisation algorithm or make its returned path optimal.

Worked example: run both algorithms on one weighted graph

Use only these directed edges: S→A=2, S→B=1, A→C=2, C→G=2, B→D=2, D→G=2. The heuristic values are h(S)=4, h(A)=3, h(B)=4, h(C)=1, h(D)=2, h(G)=0.

There are two complete routes. The upper route S→A→C→G costs 2+2+2=6. The lower route S→B→D→G costs 1+2+2=5. Therefore, the true optimum is the lower route with cost 5.

Greedy expands S, then sees A(h=3) and B(h=4), so it chooses A. Its next frontier contains C(h=1) and B(h=4), so it chooses C, followed by G(h=0). It returns S→A→C→G with cost 6. The apparently closest nodes hid the cheaper lower route because Greedy ignored the cost already paid.

A* produces a different result:

At step 2, A wins the f=5 tie because it has lower h. Crucially, G is not accepted when first generated with g=6. After D is expanded, its entry improves to g=5, and A* returns S→B→D→G.

Admissibility, consistency and heuristic quality

An admissible heuristic never overestimates: 0 ≤ h(n) ≤ h*(n), where h*(n) is the true cheapest remaining cost. Here the true values are h*(S)=5, h*(A)=4, h*(B)=4, h*(C)=2, h*(D)=2, h*(G)=0. Comparing them with h={4,3,4,1,2,0} shows that every estimate is admissible.

Consistency checks every edge using h(n) ≤ c(n,n') + h(n'):

• S→A: 4 ≤ 2+3 = 5

• S→B: 4 ≤ 1+4 = 5

• A→C: 3 ≤ 2+1 = 3

• C→G: 1 ≤ 2+0 = 2

• B→D: 4 ≤ 2+2 = 4

• D→G: 2 ≤ 2+0 = 2

All six pass. Consistency makes f non-decreasing along a path and supports clean handling of closed nodes in graph search. The zero heuristic gives no goal-directed guidance, while a closer admissible estimate usually focuses the frontier more strongly. It does not guarantee one universal runtime, because representation, tie-breaking and data structures still matter. Use Time Complexity and Asymptotic Notation when analysing those costs.

Common traps and the exact correction for each

Three theory corrections also matter. Admissible means “never overestimates”, not “exact”. Greedy Best-First Search is not made optimal merely by an admissible heuristic. Consistency implies admissibility when h(G)=0 in the usual goal-reaching setup, but an admissible heuristic need not be consistent.

For optimal A* graph search here, keep non-negative edge costs, the stated tie rule and the best_g duplicate policy visible. Completeness claims additionally need their assumptions, commonly finite branching and step costs bounded away from zero.

The implementation skeleton is only seven operations:

push S into a min-priority queue
set best_g[S] = 0
pop the entry with the smallest evaluation score
skip it if its g exceeds best_g for that state
test for the goal after the pop
relax outgoing edges, updating best_g and parent
reconstruct the path through parent pointers

How exams test heuristic search

Questions usually ask you to compute an expansion order or returned path, test admissibility or consistency, or select a correct completeness or optimality statement under explicit assumptions. For a quick selection check, Greedy picks Q from P(1,5,6), Q(5,2,7), R(4,3,7), while A* picks P. For consistency, substitute values edge by edge, as in 4≤1+4 and 3≤2+1.

The official GATE 2026 Data Science and Artificial Intelligence syllabus includes informed, uninformed and adversarial search under AI. That line establishes scope for the DA paper, not how frequently a question appears.

Practise by solving the worked graph with separate g, h, f columns. Then change only h(A) from 3 to 5 and predict the new order before checking it. Use the GATE Test Series as the next exam-practice route.

The short version and the next step

• Heuristic search ranks a frontier using estimated remaining cost.

• Greedy Best-First Search uses h.

• A* uses g+h.

• Admissibility compares estimates with true remaining cost.

• Consistency checks the estimate across every edge.

In the worked graph, Greedy returns cost 6, while A* corrects the first goal entry and returns cost 5.

Redraw the graph from memory, reproduce the six A* rows, and explain why G:6 cannot end the run. For the wider preparation map, use the GATE category. If you want a structured study route, continue with GATE Guidance by Sanchit Sir.