Q1 — Search: BFS/A*/BnB

Search algorithms on a grid map

The Question

The figure shows a map on a uniform grid where each tile is 10x10 in size.

The start node is S and the goal node is G. The MoveGen function returns nodes in alphabetical order. Use Manhattan Distance as the heuristic function.

Tie-breaker: If several nodes have the same cost, use node labels to break the tie.

Node coordinates on the 10x10 grid (relative to origin):

S: (0, 20)
A: (20, 0)
B: (20, 20)
C: (40, 0)
D: (10, 40)
E: (30, 40)
F: (30, 60)
G: (50, 40)

#	Question	Official answer
1.1	What is the path found by the Depth First Search algorithm? Enter the path as a	`S,A,C,G`
1.2	What is the path found by the Best First Search algorithm? Enter the path as a c	`S,D,F,G`
1.3	What is the path found by A* search algorithm? Enter the path as a comma separat	`S,B,E,G`
1.4	What is the path found by Branch-and-Bound search algorithm? Enter the path as a	`S,A,C,G`
1.5	For the given map, which algorithm finds the shortest path from S to G?	`B`

The Topic in 60 Seconds

Algorithm	Sorts frontier by	Ignores
DFS	deepest node (dive alphabetically)	all costs
Best First	$h(n)$	$g(n)$
A*	$f(n) = g(n) + h(n)$	nothing
Branch-and-Bound	$g(n)$ on whole paths	$h(n)$

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

Step 0 — Heuristic table

Manhattan units to G at (50, 40), scaled ×2 to match the edge-cost scale:

Node	$\Delta x + \Delta y$	$h$	Node	$\Delta x + \Delta y$	$h$
S	50 + 20 = 70	140	D	40 + 0 = 40	80
A	30 + 40 = 70	140	E	20 + 0 = 20	40
B	30 + 20 = 50	100	F	20 + 20 = 40	80
C	10 + 40 = 50	100	G	0	0

Any common positive scaling of these $h$ values produces the same picks below.

1.1 — Depth First Search → `S,A,C,G`

DFS dives into the alphabetically-first fresh neighbour and never re-enters a node already generated; the goal test fires the moment G is generated.

Step	Action
1	Expand S → MoveGen gives A, B, D (all new). OPEN = {A, B, D}. Dive into A
2	At A: S closed, B already generated from S → skip. Fresh branch = C. Dive into C
3	At C: A closed, E new, G new → generate G → goal test fires

Path: S → A → C → G. Note B and D sit unexpanded in OPEN forever — DFS never looks at them.

1.2 — Best First Search → `S,D,F,G`

Sort OPEN by $h$ only:

Step	OPEN (node : $h$ )	Pick
1	S : 140	S → A(140), B(100), D(80)
2	D : 80, B : 100, A : 140	D → F(80)
3	F : 80, B : 100, A : 140	F → E(40), G(0)
4	G : 0, E : 40, B : 100, A : 140	G — goal!

Path: S → D → F → G, cost $60+60+30+40 = 190$ . Greedy on $h$ walks straight "towards" G geometrically — and straight into the expensive eastern route.

1.3 — A* Search → `S,B,E,G`

Sort OPEN by $f = g + h$ :

Step	OPEN (node : $f$ )	Pick
1	S : 0+140 = 140	S → A : 50+140 = 190, B : 40+100 = 140, D : 60+80 = 140
2	B : 140, D : 140, A : 190	B (tie B=D at 140 → labels) → A stays 190 (via B costs 210), D : 80+80 = 160, E : 90+40 = 130
3	E : 130, D : 160, A : 190	E → F : 120+80 = 200, G : 130+0 = 130, C : 150+100 = 250
4	G : 130, D : 160, A : 190, F : 200, C : 250	G — goal!

Path: S → B → E → G, cost $40+50+40 = 130$ .

Interactive trace (labels show the current best $f$ ):

1 / 5

h: S=140, A=140, B=100, C=100, D=80, E=40, F=80, G=0 OPEN = { S(g=0, f=0+140=140) }

expandingin OPEN (f = g+h)expandedreturned path

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

Pop whole paths by $g$ ; discard any path reaching a node already cheaper reached:

Pop	New paths (path : $g$ )
S : 0	SB : 40, SA : 50, SD : 60
SB : 40	SBA : 70, SBD : 80, SBE : 90
SA : 50	SAC : 70 (SAB : 80 discarded — B already at 40)
SD : 60	SDF : 120 (B via D = 100 discarded)
SAC : 70 (tie with SBA at 70 → labels: S-A-C first)	SACG : 100 ← goal queued
SBA : 70	nothing survives (A@70 > 50, D@110 > 80)
SBD : 80	SBDF : 140
SAB : 80	nothing
SBE : 90	SBEF : 120, SBEG : 130, SBEC : 150
SACG : 100 — cheapest left in OPEN is 120	complete → optimal, stop

Path: S → A → C → G, cost $50+20+30 = 100$ ✓ the true shortest.

Answers, decoded

1.5 → B (Branch-and-Bound). Enumerate every route: S-A-C-G = 100, S-B-E-G = 130, S-B-D-E-G = 160, S-B-E-C-G = 230, S-D-F-G = 190, S-D-B-E-G = 210… The shortest is 100. Best First returns 190 and A* returns 130 — both miss it because $h(C) = 100$ grossly overestimates the true remaining cost $h^*(C) = 30$ (inadmissible heuristic ⇒ no optimality guarantee). Only Branch-and-Bound sorts by real accumulated cost $g$ , so its first complete path is provably cheapest → keyed answer B.
Why DFS also lands on S,A,C,G here: pure alphabetical luck — the western letters come first, so the dive happens to ride the cheap route. No cost bookkeeping backs it up, which is why the key credits BnB alone.
Why A fails despite using costs:* one poisoned $h$ value is enough. With $h(C) = 100 \gg 30$ , every $f$ through C looks terrible ( $f(C) = 250$ ), so G pops at 130 before the C-route can win.

Tricks & Tips

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

The Question

The Topic in 60 Seconds

Step 0 — Heuristic table

1.1 — Depth First Search → S,A,C,G

1.2 — Best First Search → S,D,F,G