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

A tie at f=20 makes A* work hard for the win — full traces for all three algorithms on an admissible map.

The Question

1×1-tile grid. Start S, goal G. MoveGen alphabetical. Heuristic = Manhattan Distance. Tie-breaker: node labels.

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

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)

Node	$h$	Node	$h$
S	8	B	6
F	9	A	4
D	7	E	4
C	2	G	0

1.1 — Best First Search → `S,E,C,G`

Step	OPEN (node : $h$ )	Pick	Add
1	S : 8	S	D : 7, F : 9, E : 4
2	E : 4, D : 7, F : 9	E	C : 2
3	C : 2, D : 7, F : 9	C	G : 0
4	G : 0, …	G — goal!	—

Path: S → E → C → G, cost $16+8+4 = 28$ .

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

Step	OPEN (node : $f$ )	Pick	Updates
1	S : 0+8 = 8	S	F : 6+9 = 15 · D : 8+7 = 15 · E : 16+4 = 20
2	F : 15, D : 15, E : 20	F (tie F before D)	B : 12+6 = 18 · D via F: 14+7 = 21 (keep 15)
3	D : 15, B : 18, E : 20	D	B via D: 16+6 = 22 (keep 18) · E via D: 18+4 = 22 (keep 20)
4	B : 18, E : 20	B	A : 16+4 = 20 · C : 20+2 = 22
5	A : 20, E : 20, C : 22	A (tie A before E)	G : 20+0 = 20
6	E : 20, G : 20, C : 22	E (tie E before G)	C via E: 26 (keep)
7	G : 20, C : 22	G — goal!	—

Path: S → F → B → A → G, cost $6+6+4+4 = 20$ . (The step-6 tie E vs G is why this trace is worth practising — labels keep E first, but G pops next anyway.)

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

Pop	OPEN (path : $g$ ) after extending
S : 0	SF : $0+6$ = 6 · SD : $0+8$ = 8 · SE : $0+16$ = 16
SF : 6	SFB : $6+6$ = 12 · SFD : $6+8$ = 14
SD : 8	SDF : $8+8$ = 16 · SDB : $8+8$ = 16 · SDE : $8+10$ = 18
SFB : 12	SFBA : $12+4$ = 16 · SFBC : $12+8$ = 20 · SFBD : $12+8$ = 20
SFD : 14	SFDB : $14+8$ = 22 · SFDE : $14+10$ = 24
SDB : 16 (first of the 16-tie — labels)	SDBA : $16+4$ = 20 · SDBF : $16+6$ = 22 · SDBC : $16+8$ = 24
SDF : 16	SDFB : $16+6$ = 22
SE : 16	SEC : $16+8$ = 24 · SED : $16+10$ = 26
SFBA : 16	SFBAG : $16+4$ = 20 ← goal queued
SDE : 18	SDEC : $18+8$ = 28
SDBA : 20 (tie at 20: S-D before S-F)	SDBAG : $20+4$ = 24
SFBAG : 20 — next at the tie, a complete tour	everything left ≥ 20 → optimal

Path: S → F → B → A → G, cost 20 ✓

1.4 — Shortest path → C (both)

Routes: S-F-B-A-G = 20 · S-D-B-A-G = 24 · S-F-D-B-A-G = $6+8+8+4+4$ = 30 · S-E-C-G = 28. Both algorithms returned 20 → C.

1.5 — Admissibility → A

$h(A) = 4 = h^*(A)$ (exact), $h(C) = 2 \le 4$ , $h(B) = 6 \le 8$ , $h(F) = 9 \le 14$ , $h(D) = 7 \le 16$ , $h(E) = 4 \le 12$ , $h(S) = 8 \le 20$ — no overestimate anywhere → admissible ✓ (and that's why A* hit the optimum).

Interactive A* trace

1 / 7

OPEN = { S(0+8=8) }

expandingin OPEN (f = g+h)expandedreturned path

Tricks & Tips

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