Coursework 1: Route Planning with Search Algorithms

Overview

Each city is a node; each road is an undirected weighted edge (km). City coordinates are used to compute the heuristic for A*.

Algorithms: BFS (example), DFS, UCS, A*
Metrics: path, total cost (km), expanded nodes, runtime (ms)
Outputs: console summary + standalone HTML (SVG) visualization

Learning Objectives

Formulate route planning as a graph search problem
Implement DFS/UCS/A* correctly and reproducibly
Use a coordinate-based heuristic and explain why it helps
Observe differences in optimality (hops vs distance) and efficiency (expansions/runtime)

Downloads & Canvas Submission

Download the materials below (these files are included in the coursework package).

Coursework handout (PDF)
Starter package
- route_planning.py — code template (you implement DFS/UCS/A*)
- run_all_tests.py — runs all algorithms on required test queries and writes test_results/
- cities.txt, roads.txt — dataset

Submitting on Canvas: . In short, you submit route_planning.py and the entire test_results/ directory, package them together into one zip file to submit.

Dataset

cities.txt format:

CityName latitude longitude
Beijing 39.9042 116.4074
Shanghai 31.2304 121.4737
XiAn 34.3416 108.9398

roads.txt format (undirected):

CityA CityB distance_km
Beijing Tianjin 120
Nanjing Shanghai 300
Hohhot Shanghai 1500

Design note: the dataset includes distractor branches and an expensive shortcut so BFS/DFS/UCS/A* show clearer differences.

Tasks (What you implement)

Starter code

route_planning.py: BFS is already implemented as an example; you implement DFS/UCS/A*
run_all_tests.py: runs all algorithms on required queries and writes test_results/

Implement these functions

dfs(graph, start, goal)
ucs(graph, start, goal)
astar(graph, coords, start, goal)

Visualization Output (Generated Automatically)

After each run, the program generates a standalone HTML visualization showing:

all cities and roads (gray)
explored edges (blue) and expanded nodes
final path (orange)
start (green) and goal (red)

Open the HTML file directly in a browser (Windows/macOS/Linux).

Running Instructions

Run a single query:

python route_planning.py --algorithm astar --start Beijing --goal Shenzhen

Specify output file:

python route_planning.py --algorithm bfs --start Beijing --goal Shanghai --output outputs/route_result.html

Run all required tests:

python run_all_tests.py --outdir test_results

What you should see if everything is correct (expected patterns)

BFS: often fewer hops; may have higher total cost than UCS/A*
DFS: not optimal; can expand many nodes depending on branch order
UCS: distance-optimal; may expand more nodes than A*
A*: distance-optimal; usually expands fewer nodes than UCS due to heuristic guidance

Check test_results/summary.csv (runtime_ms / expanded_nodes / total_cost) and compare.

Think about the differences (and conclusions)

Guiding questions

Optimality: which algorithms guarantee minimum total distance?
Efficiency: which expands fewer nodes? which runs faster?
Heuristic impact: why should A* expand fewer nodes than UCS?
Trade-off: when does BFS look “good” (few hops) but is still a bad route (high cost)?

Conclusions you should observe in this coursework

BFS is not distance-optimal on weighted graphs (optimizes hops).
DFS is not optimal and can be inefficient depending on branch order.
UCS is distance-optimal but can explore broadly.
A* is distance-optimal and typically explores fewer nodes than UCS.

Automated Tests (Submit the Output Directory)

The batch runner writes a directory containing per-case result.json and visualization.html, plus summary files. Test cases:

Beijing → Shanghai
Beijing → Shenzhen
Shanghai → Chengdu
Guangzhou → XiAn
Chengdu → Hangzhou

python run_all_tests.py

You must submit the entire test_results/ directory.

Submission Checklist

Implemented route_planning.py (DFS/UCS/A* completed; BFS unchanged)
Entire test_results/ directory generated by run_all_tests.py

No report is required.

Grading Rubric (100 points)

Component	Points
DFS implementation	20
UCS implementation	30
A* implementation	35
Running tests + correct outputs directory structure	10
Code clarity (readable, well-structured)	5
Total	100

Academic Integrity & Notes

Discussing high-level ideas is allowed, but your code must be your own.
Do not share code or copy implementations from others.
Cross-platform requirement: your code must run on Windows/macOS/Linux.