Week 5 Lab — Optimal Search (A*)

Exercise 1

Complex Pathfinding Graph

The directed weighted graph below is given. Each node shows its heuristic h(n) — the estimated remaining cost to reach Z. Numbers on edges are movement costs.

Task

Find a path from S to Z using each algorithm below. Trace every step.

A* — maintain an open list sorted by f(n) = g(n) + h(n)
Greedy Best-First Search — always expand the node with the smallest h(n)

Exercise 2

Two Corridors — A* vs Hill Climbing

The directed weighted graph below has a left corridor and a right corridor. Each node shows h(n); edge numbers are movement costs.

Task

Find a path from S to Z using each algorithm below. Trace every step.

A*
Hill Climbing (Steepest Ascent) — keep only the current node; move to a neighbour with strictly smaller h, or stop if none exists

Exercise 3

Emergency Vaccine Delivery — Mekong Delta

During a dengue fever outbreak in the Mekong Delta, a vaccination team must deliver temperature-sensitive vaccines from the Provincial Cold-Chain Center to a Remote Commune Clinic cut off by seasonal flooding. Travel times (hours) account for road conditions, ferry waits, and flood detours.

Connections & Travel Times (hours)

Provincial Cold-Chain Center → Phú Hòa Ferry (2h) · Hưng Long Bridge (5h) · Tân An Canal Road (3h)
Phú Hòa Ferry → Bình Minh Market (3h) · Sông Hậu Crossing (6h)
Hưng Long Bridge → Sông Hậu Crossing (2h) · Mỹ Phước Levee (4h)
Tân An Canal Road → Mỹ Phước Levee (3h) · Long Khánh Dock (7h)
Bình Minh Market → Trung Thành Elevated Road (4h)
Sông Hậu Crossing → Trung Thành Elevated Road (2h) · Ngã Ba Đình Crossroads (5h)
Mỹ Phước Levee → Ngã Ba Đình Crossroads (3h)
Long Khánh Dock → Ngã Ba Đình Crossroads (2h)
Trung Thành Elevated Road → Remote Commune Clinic (5h)
Ngã Ba Đình Crossroads → Remote Commune Clinic (3h)

Heuristic h(n) — estimated direct boat travel time (hours) to the Clinic:

Location	h(n)	Location	h(n)
Provincial Cold-Chain Center	10	Sông Hậu Crossing	4
Phú Hòa Ferry	8	Mỹ Phước Levee	5
Hưng Long Bridge	6	Long Khánh Dock	4
Tân An Canal Road	7	Trung Thành Elevated Road	3
Bình Minh Market	6	Ngã Ba Đình Crossroads	2
Remote Commune Clinic	0

Task

Draw the state-space graph from the connection list above.
Apply A* to find the fastest route. Trace step by step.
Apply Greedy Best-First Search on the same graph. Trace step by step.

Tie-breaking: equal f → expand the node with smaller g; still tied → alphabetical order.

Questions

1.Do A* and Greedy find the same route? If not, which is faster and by how many hours?

2.Verify that h(n) is admissible by computing h*(n) for at least three locations of your choice.

3.If the ferry at Phú Hòa is shut down (all edges from Phú Hòa Ferry removed), does the A* optimal route change?

Exercise 4

Admissibility Check

The directed weighted graph below has 8 nodes (S = start, G = goal). Each node shows its heuristic h(n); edge labels are movement costs.

h values: S=8, A=8, B=6, C=4, D=7, E=3, F=2, G=0

Definition — Admissibility

A heuristic is admissible if and only if for every node n:

h(n) ≤ h*(n)

where h*(n) is the true optimal cost (shortest path cost) from n to G.

Task

Step 1. For each node S, A, B, C, D, E, F: find the shortest path to G and compute h*(n). Compare with the h(n) value shown in the graph.
Step 2. Is h admissible overall? Identify every violation and state by how much h(n) overestimates h*(n).
Step 3. If A* uses this heuristic as-is, is it still guaranteed to find the optimal path? Explain in one or two sentences.
Step 4. Bonus — Propose the minimal correction that restores admissibility: change as few values as possible, by as small an amount as possible.

Exercise 5

Consistency Check

Use the same graph and heuristic values as Exercise 4.

Definition — Consistency (Monotonicity)

A heuristic h is consistent if for every edge n → n' with cost c:

h(n) ≤ c + h(n')

This is a local check — verify one edge at a time, without needing h*(n).

The table below lists every edge with the relevant h and cost values. For each row, compute c + h(n') and determine whether the condition holds.

Edge	h(n)	Cost c	h(n')
S → A	8	2	8
S → B	8	5	6
A → C	8	4	4
A → D	8	1	7
B → D	6	2	7
B → E	6	3	3
C → F	4	3	2
D → F	7	4	2
D → E	7	2	3
E → G	3	4	0
F → G	2	2	0

Questions

1.List every edge that violates consistency. By how much does h(n) exceed c + h(n')?

2.Which node caused an admissibility violation in Ex 4 and causes consistency violations here?

3.Node A was also inadmissible in Ex 4 (h(A)=8 > h*(A)=7). Are edges A→C and A→D consistent? Use your findings to answer: does admissibility imply consistency?

4.Bonus — If you fix the single node responsible for the consistency violations, does that also fix the admissibility violation from Ex 4?

Exercise 6

Heuristic Dominance — 8-Puzzle

The 8-puzzle is a 3×3 sliding-tile board with tiles 1–8 and one blank. A move slides an adjacent tile into the blank. Goal state:

Goal state

1

2

3

4

5

6

7

8

_

h₁ — Misplaced Tiles

Count tiles not in their goal position (blank excluded).

Relaxed problem: each misplaced tile can teleport to its goal in one move.

h₂ — Manhattan Distance

Sum of horizontal + vertical distances of each tile from its goal (blank excluded).

Relaxed problem: tiles pass through each other freely, but still pay 1 per step.

Task — Three puzzle states

For each state below, compute h₁ and h₂ by hand. Show the per-tile breakdown for each state.

State A

5

1

3

4

_

2

7

6

8

State B

1

2

3

4

_

6

5

7

8

State C

1

2

3

4

5

6

8

7

_

Questions

1.For each state, is h₂ ≥ h₁? Summarise in a table: State | h₁ | h₂ | h₂ ≥ h₁?

2.Both h₁ and h₂ are admissible. Which one is more informed? Justify with your results.

3.Explain in your own words why h₂(n) ≥ h₁(n) must always hold for any 8-puzzle state. (Hint: what does each misplaced tile contribute to h₁ vs. h₂?)

4.If h₂ dominates h₁ and both are admissible, what does that guarantee about A* using h₂ compared to A* using h₁?

Exercise 7

Grid Pathfinding — Warehouse Robot

A warehouse delivery robot starts at its charging station S = (0,0) and must reach the pickup zone G = (4,4). The floor is a 5 × 5 grid; the robot moves in four directions and each step costs 1. Gray cells are storage shelves (blocked).

Shelves (blocked): (0,3) · (1,1) · (2,1) · (2,3) · (3,3)

h₁ — Euclidean Distance

h₁(r,c) = √[(r−4)² + (c−4)²]

Relaxed: robot flies in a straight line, ignoring shelves.

h₂ — Manhattan Distance

h₂(r,c) = |r−4| + |c−4|

Relaxed: shelves are transparent — robot still pays 1 per step.

Questions

1.Compute h₁ and h₂ for these five cells: (0,0), (0,2), (1,0), (2,2), (1,4). Round h₁ to two decimal places.

2.Dominance. Is h₂(n) ≥ h₁(n) for all five cells? Complete the sentence: "h₂ dominates h₁ because Manhattan distance is always ________ Euclidean distance."

3.Admissibility. For each of the five cells, find the true shortest path to G (count steps, avoid walls) and verify h₁ ≤ h* and h₂ ≤ h*.

4.A* trace with h₂. Starting from S=(0,0), trace A* using Manhattan distance. Record each expanded node, its g, h₂, f values, and the open list.

Tie-breaking: equal f → smaller h₂; still tied → smaller (row, col) lexicographically.

5.Effect of obstacles. Suppose an extra wall is added at (3,4).

Does h₂(2,4) change? Why or why not?
Find h*(2,4) with the new wall. Is h₂ still admissible?
What does this reveal about how obstacles affect the tightness of the Manhattan-distance heuristic?

Exercise 8

Metro Navigation — A* vs Greedy

A tourist arrives at Central Station and needs to reach the International Airport. The city metro has two lines and a shuttle service:

Line 1 (Red Express): Central Station → Riverside → Midtown → Westgate → Airport
Line 2 (Blue Local): Central Station → Uptown → Docklands → Eastfield → Skyview → (shuttle) → Airport

Transfer on foot at: Riverside ↔ Uptown, Midtown ↔ Docklands, Westgate ↔ Eastfield. All connections are one-directional.

Travel times (minutes)

From	To	min	Service
Central Station	Riverside	3	Line 1
Central Station	Uptown	2	Line 2
Riverside	Midtown	4	Line 1
Riverside	Uptown	2	Transfer
Midtown	Westgate	3	Line 1
Midtown	Docklands	3	Transfer
Westgate	Airport	2	Line 1
Westgate	Eastfield	2	Transfer
Uptown	Docklands	3	Line 2
Docklands	Eastfield	4	Line 2
Eastfield	Skyview	2	Line 2
Skyview	Airport	9	Shuttle ⏳

Heuristic h(n) — straight-line distance to Airport (min)

Station	h(n)
Central Station	10
Riverside	8
Midtown	5
Westgate	2
Uptown	3
Docklands	3
Eastfield	2
Skyview ★	1
Airport	0

Abbreviations for A* trace: Ce · Ri · Mi · We · Up · Do · Ea · Sk · G

Questions

1.A* trace. Trace A* step by step using f = g + h. For each step record: station expanded, g, h, f, and the open list.

Tie-breaking: equal f → smaller h; still tied → alphabetical. Use abbreviations Ce/Ri/Mi/We/Up/Do/Ea/Sk/G.

2.Greedy trace. Apply Greedy Best-First Search (always expand the node with the smallest h). List the stations visited and the total travel time.

3.Do A* and Greedy find the same route? Which is faster, and by how many minutes?

4.Why Greedy fails. Trace Greedy's decisions step by step and identify the first station where it takes the wrong branch. What makes h(n) misleading there?

5.A* escapes the trap. A* also visits Skyview during its search, yet does not report the Skyview→Airport path as optimal. Explain why, using the f values in your trace.

6.Admissibility check. Compute h*(n) for Uptown, Skyview, and Midtown. Confirm h(n) ≤ h*(n) for each.

7.Bonus — Skyview has h=1 but h*=9 (underestimates by 8 minutes). Is this an admissibility violation? What does this reveal about the difference between admissible and tight (accurate)?