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

A tie between C and D decides Best First Search, A* settles for 5, and only Branch-and-Bound uncovers the hidden cost-4 route.

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,C,G`
1.2	A* path	`S,B,D,G`
1.3	Branch-and-Bound path	`S,A,E,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	5	E	5
B	2	F	3
C	2	G	0

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

Step	OPEN (node : $h$ )	Pick
1	S : 4	S → A(5), B(2)
2	B : 2, A : 5	B → D(2), C(2)
3	C : 2, D : 2, A : 5	C (tie with D → label order!)
4	G : 0, D : 2, A : 5	G — goal!

Path: S → B → C → G. The C-vs-D tie at $h = 2$ is the whole question — labels send the search to C.

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

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

Path: S → B → D → G, cost $2+1+2 = 5$ . (Not optimal — see 1.5.)

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

Pop	OPEN (path : $g$ )	Extend
S : 0	SA : 1, SB : 2
SA : 1	SAE : 2, SAD : 4
SAE : 2 (tie with SB — S-A before S-B)	SAEF : 3
SB : 2	SBD : 3, SBC : 4
SAEF : 3 (tie with SBD — S-A before S-B)	SAEFG : 4 ← goal queued
SBD : 3	SBDA : $3+3$ = 6, SBDF : $3+1$ = 4, SBDG : $3+2$ = 5, SBDC : $3+2$ = 5
SAD : 4 (first of the four-way tie at 4 — labels)	SADF : $4+1$ = 5, SADG : $4+2$ = 6
SAEFG : 4 — next at the tie, a complete tour	everything left ≥ 4 → optimal

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

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

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

1.5 — Admissibility → B (not admissible)

$h(A) = 5$ but the true cheapest cost from A is $A \to E \to F \to G = 3$ — overestimate! → not admissible → B. (Exactly why A* missed the optimal path in 1.4.)

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,C,G · 1.2 S,B,D,G · 1.3 S,A,E,F,G · 1.4 B · 1.5 B