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

Best First and A* both get baited right, while Branch-and-Bound assembles the cost-14 northern chain S,A,B,D,G.

The Question

1×1 grid, start S, goal G. MoveGen alphabetical, Manhattan heuristic, ties by label.

#	Question	Official answer
1.1	Best First Search path	`S,F,H,G`
1.2	A* path	`S,F,I,G`
1.3	Branch-and-Bound path	`S,A,B,D,G`
1.4	Who finds the shortest path?	C — Branch-and-Bound
1.5	Admissibility	B — inadmissible

The Topic in 60 Seconds

Algorithm	Sorts OPEN by	Ignores
Best First	$h(n)$	$g(n)$
A*	$f(n) = g(n) + h(n)$	nothing
Branch-and-Bound	$g(n)$	$h(n)$

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

Step 0 — Heuristic table (Manhattan to G, read off the paper's grid)

Node	$h$	Node	$h$
S	6	E	8
A	14	H	4
B	4	I	6
C	8	D	2
F	6	G	0

Build this before tracing — every subquestion reads from it.

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

Sort by $h$ only:

Step	OPEN (node : $h$ )	Pick
1	S : 6	S → F(6), A(14)
2	F : 6, A : 14	F → C(8), H(4), I(6)
3	H : 4, I : 6, C : 8, E : 8, A : 14	H → D(2), E(8), G(0)
4	G : 0, D : 2, …	G — goal!

Path: S → F → H → G. The tiny $h$ (H) = 4 sucks the search into the expensive 10-edge crossing before the cheap north chain is even considered.

1.2 — A* → `S,F,I,G`

Step	OPEN (node : $f$ )	Pick
1	S : 0+6 = 6	S → F : 6+6 = 12, A : 8+14 = 22
2	F : 12, A : 22	F → I : 12+6 = 18, C : 12+8 = 20, H : 16+4 = 20
3	I : 18, C : 20, H : 20, A : 22	I → G : 18+0 = 18
4	G : 18, C : 20, H : 20, A : 22	G — goal!

Path: S → F → I → G, cost $6+6+6 = 18$ . The killer: going north through A would need expanding A, but $h(A) = 14$ inflates $f(A)$ to 22 — A sits at the bottom of OPEN while G pops at 18.

Step through the trace exactly as you would annotate the exam paper:

1 / 5

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

expandingin OPEN (f = g+h)expandedreturned path

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

BnB sorts full paths by $g$ (ties broken by discovery order), never trusting $h$ :

Pop	OPEN (path : $g$ )	Extend
S : 0	SF : 6, SA : 8
SF : 6	SA : 8, SFC : 12, SFI : 12, SFA : 14, SFH : 16
SA : 8	SAB : 10, SFC : 12, SFI : 12, SAC : 14, SAF : 14, SFH : 16
SAB : 10	SFC : 12, SFI : 12, SABD : 12, SAC : 14, SAF : 14, SFH : 16, SABC : 16
SFC : 12	SFI : 12, SABD : 12, SAC : 14, SAF : 14, SFCE : 16, SFH : 16, SABC : 16, SFCA : 18, SFCB : 18
SFI : 12	SABD : 12, SAC : 14, SAF : 14, SFCE : 16, SFH : 16, SABC : 16, SFIG : 18 ← goal, SFCA : 18, SFCB : 18, SFIH : 18
SABD : 12	SAC : 14, SAF : 14, SABDG : 14 ← goal, SFCE : 16, SFH : 16, SABC : 16, SABDE : 16, … , SABDH : 20
SAC : 14	SAF : 14, SABDG : 14, SFCE : 16, … , SACE : 18, SACF : 20, SACB : 22
SAF : 14	SABDG : 14, SFCE : 16, … , SAFC : 20, SAFI : 20, SAFH : 24
SABDG : 14	everything open ≥ 16 → optimal

Path: S → A → B → D → G, cost $8+2+2+2 = 14$ ✓ the true shortest.

1.4 — Shortest path → C (Branch-and-Bound only)

Algorithm	Path	Cost
Best First	S,F,H,G	$6+10+8 = 24$
A*	S,F,I,G	$6+6+6 = 18$
Branch-and-Bound	S,A,B,D,G	$8+2+2+2 = \mathbf{14}$

A* returned 18, BnB returned 14 → C.

1.5 — Admissibility → B (inadmissible)

$h$ is admissible iff it never overestimates. Check the nodes on the true best route:

Node	$h(n)$	True cheapest $h^*(n)$	Verdict
A	14	A→B→D→G = $2+2+2 = 6$	overestimates!
E	8	E→D→G = $4+2 = 6$	overestimates
B	4	B→D→G = $2+2 = 4$	fine

One counter-example suffices: $h(A) = 14 > h^*(A) = 6$ → not admissible → B ✓ — which is precisely why A* came home with 18 instead of 14.

Tricks & Tips

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