Q1 — Best First Search, A* and Branch-and-Bound on a Grid Map

Three algorithms, one map — why each returns a different path, and why only Branch-and-Bound finds the shortest one.

The Question

A map on a uniform grid (each tile 10×10). Start S, goal G. MoveGen returns neighbours in alphabetical order. Heuristic = Manhattan Distance. Tie-breaker: node labels.

Subquestions

#	Question	Official answer
1.1	Path found by Best First Search	`S,D,F,G`
1.2	Path found by A*	`S,B,E,G`
1.3	Path found by Branch-and-Bound (acyclic)	`S,A,C,G`
1.4	Which algorithm finds the shortest path?	B — Branch-and-Bound
1.5	Is the heuristic admissible?	B — Not admissible

The Topic in 60 Seconds

All three algorithms keep a list of partial paths and repeatedly pick one, expand it — they differ only in how they pick:

Algorithm	Picks the node with smallest	Ignores
Best First Search (greedy)	$h(n)$ — estimated distance to goal	cost already paid
A*	$f(n) = g(n) + h(n)$	nothing — balances both
Branch-and-Bound	$g(n)$ — exact cost so far	the heuristic entirely

$g(n)$ = exact cost of the path from S to $n$
$h(n)$ = heuristic estimate from $n$ to G

Deep-dive: A* Search, Best First Search, Branch and Bound.

Step 0 — Precompute the heuristic table

Manhattan distance on the grid: $h(n) = 10 \times (|x_n - x_G| + |y_n - y_G|)$ with G at (90, 60).

Node	Coordinates	$h(n)$
S	(0, 30)	$90 + 30 = 120$
A	(30, 0)	$60 + 60 = 120$
B	(30, 30)	$60 + 30 = 90$
D	(20, 50)	$70 + 10 = 80$
E	(50, 60)	$40 + 0 = 40$
F	(50, 90)	$40 + 30 = 70$
C	(70, 0)	$20 + 60 = 80$
G	(90, 60)	$0$

Build this table before tracing anything — every subquestion reads from it.

1.1 — Best First Search → `S,D,F,G`

Best First picks the open node with the smallest $h$ only.

Step	Open list (node : $h$ )	Pick	Expand → add
1	S : 120	S	D : 80, B : 90, A : 120
2	D : 80, B : 90, A : 120	D	F : 70 (B, S already seen)
3	F : 70, B : 90, A : 120	F	E : 40, G : 0
4	G : 0, E : 40, B : 90, A : 120	G — goal!	—

Path: S → D → F → G. Notice BFS never looked at edge costs — it just slid downhill on $h$ . Step through the trace exactly as you would write it in the exam:

1 / 5

OPEN = { S(h=120) }

picking nowin OPENexpandedfinal path

1.2 — A* → `S,B,E,G`

A* picks the open node with the smallest $f(n) = g(n) + h(n)$ .

Step	Open list (node : $g$ , $h$ , $f$ )	Pick	Updates
1	S : 0, 120, 120	S	B : 40, 90, 130 · A : 50, 120, 170 · D : 60, 80, 140
2	B : 130, D : 140, A : 170	B	A via B: $g=70$ → 190 (worse than 170, keep 50/170) · E : 90, 40, 130 · D via B: $g=80$ → 160 (worse than 140, keep)
3	E : 130, D : 140, A : 170	E	G : 130, 0, 130 · C : 150, 80, 230
4	G : 130, D : 140, A : 170, C : 230	G — goal!	—

Path: S → B → E → G, cost $40 + 50 + 40 = 130$ .

1 / 5

OPEN = { S(g=0, h=120, f=120) }

expandingin OPEN (f = g+h)expanded / rejectedreturned path

Wait — is that really optimal?

A* returned cost 130, but 1.4 says the shortest path costs 100 (via A and C). A* can only be trusted to be optimal when $h$ is admissible — and 1.5 shows it is not. A single inadmissible node poisoned the search: the inflated $h(C) = 80$ scared A* away from the genuinely cheap S–A–C–G route.

1.3 — Branch-and-Bound → `S,A,C,G`

BnB picks the open path with the smallest $g$ and never extends a path that revisits a node (the "avoids cyclic expansions" note).

Step	Open paths (path : $g$ )	Pick	Extend with
1	S : 0	S	SB : 40, SA : 50, SD : 60
2	SB : 40, SA : 50, SD : 60	SB	SBA : 70, SBE : 90, SBD : 80
3	SA : 50, SD : 60, SBA : 70, SBD : 80, SBE : 90	SA	SAC : 70
4	SD : 60, SBA : 70, SAC : 70, SBD : 80, SBE : 90	SD	SDF : 120, SDB : 100
5	SBA : 70, SAC : 70, SBD : 80, SBE : 90, SDB : 100, SDF : 120	SBA	SBAC : 90
6	SAC : 70, SBD : 80, SBE : 90, SBAC : 90, SDB : 100, SDF : 120	SAC	SACG : 100 ← goal on the queue
7	SBE : 90, SBAC : 90, SACG : 100, SDB : 100, SDF : 120	SBD	SBDF : 140
8	SBE : 90, SBAC : 90, SACG : 100, SDB : 100, SDF : 120, SBDF : 140	SBE	SBEG : 130, SBEC : 150
9	SBAC : 90, SACG : 100, SDB : 100, SDF : 120, SBEG : 130, SBDF : 140, SBEC : 150	SBAC	SBACG : 120
10	SACG : 100, everything else ≥ 100	SACG — cheapest, done	—

Path: S → A → C → G, cost $50 + 20 + 30 = 100$ .

Why BnB can stop

Every remaining open path already costs $\geq 100$ , so none of them can ever beat SACG. That is the whole trick of Branch-and-Bound: the first goal node pulled from the queue while all alternatives are no cheaper is provably optimal.

1 / 9

OPEN = [ S:0 ]

path being extendedin OPEN (sorted by g)not reachable nowoptimal path (cost 100)

1.4 — Which algorithm finds the shortest path? → B

Compare the three answers:

Algorithm	Path	Cost
Best First	S,D,F,G	$60+60+60 = 180$
A*	S,B,E,G	$40+50+40 = 130$
Branch-and-Bound	S,A,C,G	$50+20+30 = \mathbf{100}$

Only B (Branch-and-Bound) found the shortest path — because it optimizes on exact costs $g$ alone and never trusts the heuristic.

1.5 — Admissibility → B (not admissible)

$h$ is admissible iff it never overestimates the true remaining cost: $0 \le h(n) \le h^*(n)$ . Compute the true cheapest cost-to-go for each node and compare:

Node	$h(n)$	True cost $h^*(n)$	Verdict
C	80	C→G = 30	overestimates!
F	70	F→G = 60	overestimates
A	120	A→C→G = 50	overestimates

One counter-example is enough: $h(C) = 80 > h^*(C) = 30$ , so the heuristic is not admissible → option B.

Tricks & Tips for This Question Family

QuizIn this map, why did A* miss the shortest path S,A,C,G?

Answers: 1.1 S,D,F,G · 1.2 S,B,E,G · 1.3 S,A,C,G · 1.4 B · 1.5 B