Best-First Search Explained: Greedy Heuristics, a Worked Graph and Exam Traps

Best-first search expands the "most promising" state. Questions get harder when its priority is unnamed, OPEN changes, or the first goal is mistaken for the cheapest path. Greedy best-first search can find a goal before finding the cheapest path, unlike uniform-cost search and A*.

Best-First Search: the family name and the greedy variant

Best-first search is a family that selects the next frontier node through an evaluation function. Let g(n) be the discovered cost from start S to n, and h(n) the estimated cost from n to goal G. The function supplies the priority.

Best-first search describes a family, but many AI questions mean its greedy variant, f(n)=h(n). The greedy variant uses f(n)=h(n); uniform-cost search uses f(n)=g(n), and A* uses f(n)=g(n)+h(n). Never switch formulas midway through a trace.

For wider preparation, see GATE CS Exam Preparation Courses & Test Series.

Greedy best-first mechanics: OPEN, CLOSED, parents and ties

OPEN is a minimum-priority queue ordered by h. Add S, then repeatedly pop the smallest-h node. If it is G, reconstruct through parent pointers. Otherwise close it, generate outgoing neighbours, and add each unseen state with its h, accumulated g, and parent. Skip stale entries for closed states.

push S into OPEN
while OPEN is not empty:
    n = pop minimum h
    if n is closed: skip it
    if n is G: reconstruct the path using parents
    close n
    generate each unseen successor x
    set parent[x] = n, record g(x), and push x

Greedy records g to price the route, not for selection. A trace is determinate only when its duplicate and reopening policies are stated. This graph has no repeated state. Equal h values are broken alphabetically, though no tie changes the trace. CLOSED prevents cycling. Search terminates here, but greedy is not generally complete in an infinite space or optimal.

Best-First Search worked graph: edges, heuristics and route costs

Use the directed graph with nodes S, A, B, C, D, E, G. Its only edges are S->A:2, S->B:3, A->C:2, A->G:9, B->D:2, B->E:4, C->G:2, D->G:5, and E->G:1.

Before running any algorithm, enumerate every complete route:

• S-A-C-G: 2+2+2=6

• S-B-E-G: 3+4+1=8

• S-B-D-G: 3+2+5=10

• S-A-G: 2+9=11

Therefore S-A-C-G is the unique cheapest route, with cost 6.

Greedy best-first trace: every OPEN update

Start with OPEN=[S(g=0,h=5)] and CLOSED={}. Entries below are ordered by increasing h.

On popping G, follow G<-E<-B<-S and reverse the pointers. The returned path is S-B-E-G, and its cost is 3+4+1=8. The expansion order is S,B,E,G. Neither A nor C is expanded before termination.

Why a good heuristic does not make greedy search optimal

The returned cost is 8, while independent route enumeration gave an optimum of 6. The gap is 8-6=2. Greedy sees h(B)=2<h(A)=4, then h(E)=1<h(A)=4, but never adds the already-paid g(B)=3 or g(E)=7 to its choices.

The heuristic is admissible because h(n)<=h*(n) at every node: 5<=6, 4<=4, 2<=5, 2<=2, 5<=5, 1<=1, and 0<=0.

It is also consistent on every edge: 5<=2+4, 5<=3+2, 4<=2+2, 4<=9+0, 2<=2+5, 2<=4+1, 2<=2+0, 5<=5+0, and 1<=1+0.

Admissibility and consistency support A* guarantees under the relevant graph-search assumptions. They do not make greedy best-first optimal because greedy uses only h. This implementation tests the goal when popped, not when generated. It still returns cost 8 because G immediately has the minimum heuristic, 0.

Greedy best-first vs A*, uniform-cost search and BFS

For A*, expanding A creates C with g=2+2=4, h=2, f=6, and direct G with g=2+9=11, f=11. C then creates G with g=4+2=6, h=0, f=6. The pop order is S,B,A,C,G, returning the optimum cost 6.

A* with h=0 becomes uniform-cost search. Greedy with every h=0 creates ties because it ignores g. Review Graph Algorithms: BFS, DFS and Dijkstra Traced Step by Step for traversal and Greedy Algorithms: Huffman, Knapsack, Activity Selection for the greedy idea. BFS minimises edges in an unweighted graph. Here, two-edge S-A-G costs 11, so minimum depth is not minimum weighted cost.

Best-First Search exam traps to calculate

Check these answers directly from the trace:

1. After S, B is next because h(B)=2<h(A)=4.

2. After B, OPEN is [E(h=1,g=7), A(h=4,g=2), D(h=5,g=5)].

3. The greedy expansion order is S,B,E,G.

4. Greedy returns S-B-E-G at cost 8; the optimum is S-A-C-G at cost 6.

5. The heuristic is admissible and consistent, yet greedy is non-optimal.

Wrong rules have predictable results. Using g+h produces A*. Selecting smallest g produces uniform-cost search. Treating h as an edge cost corrupts priority and path arithmetic. Testing the goal on generation changes the algorithm. Without a tie rule, equal-priority orders are ambiguous. BFS is not a cheapest-path method on weighted edges.

Change only h(A) from 4 to 1. Greedy pops A after S, generates C(h=2,g=2+2=4) and direct G(h=0,g=2+9=11), then pops G. It returns S-A-G at cost 11, worse than the earlier 8 and optimum 6. A smaller local heuristic can change the route without making it cheaper. KnowledgeGate has 5+ live practice questions on Best First Search, a focused practice set rather than evidence of official recurrence.

Best-First Search: the short version and next step

Recall six steps: identify the evaluation function; place S in OPEN; pop minimum priority; move it to CLOSED; generate successors and record parents; when G is popped, reconstruct and separately total the edge costs. Here, priority h expands S,B,E,G, returns S-B-E-G, and pays 8; the cheapest route costs 6.

Self-check one: replace greedy priority with g+h. You should get S,B,A,C,G and cost 6. Self-check two: why does setting every h to 0 make A* uniform-cost search but leave greedy tie-dependent? A* orders by g+0=g; greedy compares identical zeroes and never consults g.

For heuristic search and broader AI concepts, use AI & ML for Placements | Generative AI Placement Course. For structured core GATE CS preparation, use GATE Guidance by Sanchit Sir. Before moving on, recreate the OPEN table without looking at the trace.