Q3 — A* Search for Optimal Solution (Edge Cost 5)

A* on a uniform-cost graph (edge = 5) — the h function overestimates and A* returns S,B,F,L,G at cost 20.

The Question

A graph with uniform edge cost 5. Start S, goal G. Manhattan heuristic.

#	Question	Official answer
3.1	A* path	`S,B,F,L,G`
3.2	Cost of the path	`20`
3.3	Is Manhattan admissible?	B — No

The Topic in 60 Seconds

A* orders OPEN by $f(n) = g(n) + h(n)$ . Uniform edge costs make $g$ a multiple of 5 (one edge = one move). Admissibility needs $h(n) \le h^*(n)$ everywhere — a single counterexample kills it.

Deep-dive: A* Search.

Step 0 — Grid coordinates and the h-table

Reading tile positions off the figure ( $x$ rightward, $y$ downward), each grid step is charged like one edge (cost 5):

Node	(x, y)	Tiles to G	$h = 5 \times$ tiles	Node	(x, y)	Tiles to G	$h = 5 \times$ tiles
S	(1, 0)	5	25	F	(4, 0)	2	10
A	(2, 0)	4	20	H	(5, 1)	2	10
B	(3, 0)	3	15	L	(5, 0)	1	5
C	(2, 1)	5	25	M	(5, −1)	2	10
D	(3, 1)	4	20	K	(6, 1)	1	5
E	(4, 1)	3	15	G	(6, 0)	0	0

3.1 — A* working → `S,B,F,L,G`

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

Step	Expanded ( $f$ )	Generate / update	OPEN after (cheapest first)
1	S : $0+25=25$	A : $5+20=25$ · B : $5+15=20$ · C : $5+25=30$	B 20 · A 25 · C 30
2	B : 20	D : $10+20=30$ · E : $10+15=25$ · F : $10+10=20$ (A, C, S seen)	F 20 · A 25 · E 25 · C 30 · D 30
3	F : 20	L : $15+5=20$ (E already at 25, B closed)	L 20 · A 25 · E 25 · C 30 · D 30
4	L : 20	G : $20+0=20$ · K : $20+5=25$ · M : $20+10=30$ · H : $20+10=30$	G 20 · A 25 · E 25 · K 25 · C 30 · D 30 · H 30 · M 30
5	G : 20 — GOAL	—	—

Path: S → B → F → L → G ✓

3.2 — Cost of the path → `20`

Four edges × 5: $5+5+5+5 = \mathbf{20}$ ✓

3.3 — Is Manhattan admissible? → B (No)

Admissibility dies on a single node, and this figure has several:

Node	$h$	True cheapest cost $h^*$	Verdict
M	10	$5$ (single edge M–L)	overestimates ✗
E	15	$5$ (single edge E–L)	overestimates ✗

The figure joins nodes that are 2 Manhattan tiles apart with a single cost-5 edge, so the tile count (× 5) exceeds the true remaining cost → $h \not\le h^*$ → not admissible → B ✓ (A* still happened to return a cheapest path here because the overestimates sit off the main corridor.)

Interactive A* trace

1 / 6

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

expandingin OPEN (f = g+h)expandedreturned path

Tricks & Tips

Answers: 3.1 S,B,F,L,G · 3.2 20 · 3.3 B