Q3 — A* Optimal Solution

A* on a 10x10-tile grid with edge cost 15 — Manhattan overestimates and A* returns S,C,F,K,G at cost 60.

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 and the cost of each edge is 15 units. The MoveGen function returns nodes in alphabetical order. Use Manhattan Distance as the heuristic function. Where necessary, use node labels to break ties.

#	Question	Official answer
3.1	What is the path found by A*?	`S,C,F,K,G`
3.2	What is the cost of the path found by A*?	`60`
3.3	Is the Manhattan Distance admissible for the given problem?	`B` — No

The Topic in 60 Seconds

A* orders OPEN by $f(n) = g(n) + h(n)$ . With every edge costing 15, $g$ = 15 × edges so far. Admissibility demands $h(n) \le h^*(n)$ for every node — one counterexample is enough to answer "No".

Deep-dive: A* Search.

Step 0 — Grid coordinates and the h-table

Reading tile positions off the figure ( $x$ rightward, $y$ downward); Manhattan distance measured in tiles and converted to cost units at 10 per tile:

Node	(x, y)	Tiles to G	$h$	Node	(x, y)	Tiles to G	$h$
S	(1, 0)	5	50	F	(4, 0)	2	20
A	(2, 0)	4	40	H	(5, 1)	2	20
B	(2, 1)	5	50	K	(5, 0)	1	10
C	(3, 0)	3	30	M	(5, −1)	2	20
D	(3, 1)	4	40	L	(6, 1)	1	10
E	(4, 1)	3	30	G	(6, 0)	0	0

3.1 — A* working → `S,C,F,K,G`

MoveGen alphabetical; each entry shows $g + h = f$ exactly.

Step	Expanded ( $f$ )	Generate / update	OPEN after (cheapest first)
1	S : $0+50=50$	A : $15+40=55$ · B : $15+50=65$ · C : $15+30=45$	C 45 · A 55 · B 65
2	C : 45	D : $30+40=70$ · E : $30+30=60$ · F : $30+20=50$ (A, B, S seen)	F 50 · A 55 · E 60 · B 65 · D 70
3	F : 50	K : $45+10=55$ (E already at 60, C closed)	A 55 · K 55 · E 60 · B 65 · D 70
4	A : 55 (tie with K → labels)	nothing new (C, S seen)	K 55 · E 60 · B 65 · D 70
5	K : 55	L : $60+10=70$ · M : $60+20=80$ · G : $60+0=60$ · H : $60+20=80$	G 60 · E 60 · B 65 · D 70 · L 70 · H 80 · M 80
6	E : 60 (tie with G → labels)	H improves: $g$ $60 \to 45$ , $f = 45+20 = 65$ ; D stays at 70 ( $45+40 = 85$ worse)	G 60 · H 65 · B 65 · D 70 · L 70 · M 80
7	G : 60 — GOAL	—	—

Path: S → C → F → K → G ✓

3.2 — Cost of the path → `60`

Four edges × 15: $15 + 15 + 15 + 15 = \mathbf{60}$ ✓

3.3 — Admissible? → No (`B`)

Node	$h$	True cheapest cost $h^*$	Verdict
M	20	$15$ (single edge M–G)	overestimates ✗
H	20	$15$ (single edge H–K)	overestimates ✗

The figure joins nodes lying 2 Manhattan tiles apart (diagonal links) with a single cost-15 edge, while each tile counts as 10. So $h$ can exceed the true remaining cost → $h \not\le h^*$ → not admissible → B ✓ (A* still returned a cheapest path here because the offenders hang off the main corridor.)

Interactive A* trace

1 / 7

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

expandingin OPEN (f = g+h)expandedreturned path

Tricks & Tips

Answers: 3.1 S,C,F,K,G · 3.2 60 · 3.3 B