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

A* gets baited by B's low h into a cost-5 path while Branch-and-Bound quietly assembles the cost-4 route through C and F.

The Question

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

#	Question	Official answer
1.1	Best First Search path	`S,B,D,G`
1.2	A* path	`S,A,D,G`
1.3	Branch-and-Bound path	`S,A,C,F,G`
1.4	Who finds the shortest path?	B — Branch-and-Bound only
1.5	Admissibility	B — not 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	4	D	2
A	4	E	2
B	2	F	2
C	4	G	0

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

Step	OPEN (node : $h$ )	Pick
1	S : 4	S → A(4), B(2)
2	B : 2, A : 4	B → D(2), E(2)
3	D : 2, E : 2, A : 4	D (tie D/E → labels) → F(2), G(0)
4	G : 0, …	G — goal!

Path: S → B → D → G.

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

Step	OPEN (node : $f$ )	Pick
1	S : 0+4 = 4	S → A : 1+4 = 5, B : 4+2 = 6
2	A : 5, B : 6	A → C : 2+4 = 6, D : 3+2 = 5
3	D : 5, B : 6, C : 6	D → F : 5+2 = 7, G : 5+0 = 5
4	G : 5, B : 6, C : 6, F : 7	G — goal!

Path: S → A → D → G, cost $1+2+2 = 5$ .

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

Pop	OPEN (path : $g$ )	Extend
S : 0	SA : 1, SB : 4
SA : 1	SAC : 2, SAD : 3
SAC : 2	SACF : 3
SACF : 3 (tie with SAD — labels: S-A-C before S-A-D)	SACFG : 4 ← goal queued
SAD : 3	SADF : $3+2$ = 5, SADG : $3+2$ = 5, SADB : $3+1$ = 4
SACFG : 4 — cheapest in OPEN (ties SADB/SB at 4 lose on labels)	a complete tour, everything left ≥ 4 → optimal

Path: S → A → C → F → G, cost $1+1+1+1 = 4$ ✓ the true shortest.

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

Routes: S-A-C-F-G = 4 · S-A-D-G = 5 · S-B-D-G = 7 · S-B-E-G = 7. A* returned 5, BnB returned 4 → B.

1.5 — Admissibility → B (not admissible)

$h(A) = 4$ but the true cheapest cost from A is $A \to C \to F \to G = 3$ — overestimate! → not admissible → B ✓ (which is exactly why A* settled for 5).

Interactive A* trace

1 / 5

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

expandingin OPEN (f = g+h)expandedreturned path

Tricks & Tips

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