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

Three algorithms, three different paths — Best First finds 14, A* finds 10, and only Branch-and-Bound uncovers the cost-8 northern route.

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,D,E,C,G`
1.2	A* path	`S,D,H,F,G`
1.3	Branch-and-Bound path	`S,A,B,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, from the figure's grid)

Node	$h$	Node	$h$
S	6	E	5
A	7	F	1
B	3	G	0
C	3	H	5
D	5

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

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

Path: S → D → E → C → G, cost $2+4+4+4 = 14$ .

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

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

Path: S → D → H → F → G, cost $2+2+2+4 = 10$ .

1 / 6

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

expandingin OPEN (f = g+h)expandedreturned path

Why A* detours through H

E's low $h$ (5) is a lie — its real cost to G is 8. But at expansion time $f(E) = 11$ sits above $f(H) = 9$ and $f(F) = 7$ , so the goal (10) is reached before E ever comes off the queue. The inadmissible $h(A) = 7 > h^*(A) = 4$ is what breaks optimality overall.

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

Pop the cheapest partial path; ties break by path labels (SDE < SDHF < SAB).

Pop	Extend to	OPEN afterwards (path : g)
S : 0	SA : 4, SD : 2	SD : 2, SA : 4
SD : 2	SDE : 6, SDH : 4	SA : 4, SDH : 4, SDE : 6
SDH : 4	SDHF : 6	SA : 4, SDE : 6, SDHF : 6
SA : 4	SAB : 6, SAE : 12	SDE : 6, SDHF : 6, SAB : 6, SAE : 12
SDE : 6	SDEC : 10, SDEH : 14	SDHF : 6, SAB : 6, SDEC : 10, SAE : 12, SDEH : 14
SDHF : 6	SDHFG : 10 (goal on queue)	SAB : 6, SDHFG : 10, SDEC : 10, SAE : 12, SDEH : 14
SAB : 6	SABC : 10, SABG : 8 (goal on queue)	SABG : 8, SDHFG : 10, SABC : 10, SDEC : 10, SAE : 12, SDEH : 14
SABG : 8	goal popped — cheapest open is 10 ≥ 8	→ optimal

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

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

Routes: S-A-B-G = 8 · S-D-H-F-G = 10 · S-D-E-C-G = 14 · S-A-B-C-G = 14. Only BnB returned 8 → C.

1.5 — Admissibility → B (inadmissible)

$h(A) = 7$ but $h^*(A) = A \to B \to G = 4$ — overestimate → inadmissible → B ✓ (and that's exactly why A* returned 10 instead of 8).

Tricks & Tips

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