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

One map, three algorithms — this time the heuristic is honest, so A* and Branch-and-Bound agree on the optimal path.

The Question

A 1×1-tile grid map. Start S, goal G. MoveGen returns neighbours alphabetically. Heuristic = Manhattan Distance. Tie-breaker: node labels.

#	Question	Official answer
1.1	Path found by Best First Search	`S,C,F,G`
1.2	Path found by A*	`S,B,A,E,G`
1.3	Path found by Branch-and-Bound (acyclic)	`S,B,A,E,G`
1.4	Which algorithm finds the shortest path?	C — both A* and BnB
1.5	Admissibility of the heuristic	A — admissible

All three keep a list of partial paths and repeatedly pick one to expand — they differ only in the sorting key:

Deep-dive: A* Search, Best First Search, Branch and Bound.

Node	$h(n)$	Node	$h(n)$
S	8	D	6
A	9	E	7
B	8	F	4
C	5	G	0

Step	OPEN (node : $h$ )	Pick	Add
1	S : 8	S	B : 8, C : 5
2	C : 5, B : 8	C	F : 4
3	F : 4, B : 8	F	G : 0
4	G : 0, B : 8	G — goal!	—

Path: S → C → F → G. Greedy on $h$ alone — cost $16+8+8 = 32$ (far from optimal, but that's not BFS's job).

Step	OPEN (node : $g$ , $h$ , $f$ )	Pick	Updates
1	S : 0, 8, 8	S	B : 4, 8, 12 · C : 16, 5, 21
2	B : 12, C : 21	B	A : 8, 9, 17 · D : 10, 6, 16 · C via B: 16, 5, 21 (no gain)
3	D : 16, A : 17, C : 21	D	E : 16, 7, 23 · F : 18, 4, 22 · C via D: 28 (keep 21)
4	A : 17, C : 21, E : 23, F : 22	A	E via A: 12, 7, 19 (improves 23!)
5	E : 19, C : 21, F : 22	E	G : 20, 0, 20
6	G : 20, C : 21, F : 22	G — goal!	—

Path: S → B → A → E → G, cost $4+4+4+8 = 20$ .

Pop	OPEN (path : $g$ ) after extending
S : 0	SB : 4 · SC : 16
SB : 4	SBA : $4+4$ = 8 · SBD : $4+6$ = 10 · SBC : $4+12$ = 16
SBA : 8	SBAE : $8+4$ = 12
SBD : 10	SBDA : $10+4$ = 14 · SBDE : $10+6$ = 16 · SBDF : $10+8$ = 18 · SBDC : $10+12$ = 22
SBAE : 12	SBAED : $12+6$ = 18 · SBAEG : $12+8$ = 20 ← goal queued
SBDA : 14	SBDAE : $14+4$ = 18
SBC : 16 (tie with SC — labels)	SBCF : 24 · SBCD : 28
SC : 16	SCF : 24 · SCB : 28 · SCD : 28
SBDE : 16	SBDEA : 20 · SBDEG : 24
SBAED, SBDAE, SBDF : 18	SBAEDC : 30 · SBAEDF : 26 · SBDAEG : 26 · SBDFG : 26 · SBDFC : 26
SBAEG : 20 — cheapest at the 20-tie (S-A before S-B), a complete tour	everything left ≥ 20 → optimal, stop

Path: S → B → A → E → G, cost 20.

Interactive A* trace — watch $f = g + h$ steer the search around to the cheap northern route:

1 / 7

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

expandingin OPEN (f = g+h)expandedreturned path

Enumerate the plausible routes: S-B-A-E-G = 20 · S-B-D-E-G = 24 · S-B-D-F-G = 26 · S-C-F-G = 32. Both A* and BnB returned 20 → option C.

Check $h(n) \le h^*(n)$ everywhere:

Node	$h$	$h^*$ (true best to G)	OK?
S	8	20	✓
B	8	16 (B-A-E-G)	✓
A	9	12 (A-E-G)	✓
D	6	14 (D-E-G)	✓
E	7	8	✓
C	5	16 (C-F-G)	✓
F	4	8	✓

No overestimate anywhere → admissible → option A. (That's exactly why A* succeeded in 1.4.)

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