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

Best First dives at D, A* settles for 14, and Branch-and-Bound uncovers the cost-12 eastern route through E and C.

The Question

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

#	Question	Official answer
1.1	Best First Search path	`S,D,A,G`
1.2	A* path	`S,F,A,G`
1.3	Branch-and-Bound path	`S,F,E,C,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	9	E	7
F	8	A	3
D	7	B	4
C	2	G	0

Build this before tracing — every subquestion reads from it.

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

Best First picks the open node with the smallest $h$ only — edge costs never matter:

Step	OPEN (node : $h$ )	Pick
1	S : 9	S → F(8), D(7)
2	D : 7, F : 8	D → A(3)
3	A : 3, F : 8	A → B(4), G(0)
4	G : 0, B : 4, F : 8	G — goal!

Path: S → D → A → G. The low $h$ (D) = 7 drags the search east before the cheaper western edge S–F ever gets its turn.

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

Step	OPEN (node : $f$ )	Pick
1	S : 0+9 = 9	S → F : 4+8 = 12, D : 8+7 = 15
2	F : 12, D : 15	F → E : 8+7 = 15, A : 10+3 = 13
3	A : 13, D : 15, E : 15	A → G : 14+0 = 14, B : 14+4 = 18
4	G : 14, D : 15, E : 15, B : 18	G — goal!

Path: S → F → A → G, cost $4+6+4 = 14$ . A*'s tiny $h$ (A) = 3 makes the detour through A look better than grinding east through D and E — so G pops at 14 before D or E are ever expanded.

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

1 / 5

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

expandingin OPEN (f = g+h)expandedreturned path

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

BnB sorts full paths by $g$ and never trusts $h$ :

Pop	OPEN (path : $g$ )	Extend
S : 0	SF : 4, SD : 8
SF : 4	SD : 8, SFE : 8, SFA : 10
SD : 8	SFE : 8, SFA : 10, SDA : 12
SFE : 8	SFA : 10, SFEC : 10, SDA : 12, SFEB : 14
SFA : 10	SFEC : 10, SDA : 12, SFEB : 14, SFAB : 14, SFAG : 14 ← goal on queue
SFEC : 10	SDA : 12, SFECG : 12 ← goal, SFEB : 14, SFAB : 14, SFAG : 14
SDA : 12	SFECG : 12, SFEB : 14, SFAB : 14, SFAG : 14, SDAB : 16, SDAG : 16
SFECG : 12	everything open ≥ 14 → optimal

Path: S → F → E → C → G, cost $4+4+2+2 = 12$ ✓ the true shortest.

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

Algorithm	Path	Cost
Best First	S,D,A,G	$8+4+4 = 16$
A*	S,F,A,G	$4+6+4 = 14$
Branch-and-Bound	S,F,E,C,G	$4+4+2+2 = \mathbf{12}$

A* returned 14, BnB returned 12 → C.

1.5 — Admissibility → B (inadmissible)

$h$ is admissible only if it never overestimates. Check the corner the winning route squeezes through:

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

One counter-example is enough: $h(E) = 7 > h^*(E) = 4$ → not admissible → B ✓ — which is exactly why A* came home with 14 instead of 12.

Tricks & Tips

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