Uniform Cost Search (UCS) — Beginner-Friendly Notes

1. Why UCS Exists

BFS is optimal only when every step costs the same. Real problems have different costs (distance, fuel, time). UCS fixes that — it always expands the cheapest path first.

UCS = BFS generalised for weighted costs.

2. How It Works

Use a priority queue ordered by path cost $g(n)$ (cost from start to node).

frontier = priority queue by g(n)
frontier.push(initial, cost 0)
while frontier not empty:
  node = pop lowest g(n)
  if goal_test(node): return path  # first goal popped is optimal!
  for child: frontier.push(child, g(child))

Key rule: check goal when you pop, not when you generate — a cheaper path to same state may still be in queue.

3. Example — Road Map

• A→B cost 2, A→C cost 5, B→G cost 2 (total 4), C→G cost 1 (total 6). UCS expands A (0) → B (2) → C (5) → G via B (4) before G via C (6), so finds optimal cost 4, even though BFS would find C first.

4. Properties (exam must-know)

Property	Value
Complete	Yes (if step costs > 0)
Optimal	Yes — finds lowest-cost goal (Dijkstra's algorithm)
Time / Space	$O(b^{C*/\epsilon})$ where $C*$ = optimal cost, $\epsilon$ = minimum step cost — can be large, similar to BFS

Essentially BFS when all costs equal, but smarter otherwise.

5. UCS vs BFS vs A*

• BFS: cheapest in steps.
• UCS: cheapest in cost.
• A:* UCS + heuristic $h(n)$ to guide toward goal faster (next topic).

6. Common Mistake

Thinking UCS is heuristic — it is not; it uses only actual cost so far $g(n)$, no guess of remaining cost. That makes it uninformed but still cost-optimal.

7. One-Line Summary to Write in Exam

UCS expands nodes in order of increasing path cost $g(n)$ using a priority queue, is complete and optimal for positive step costs, and is the generalisation of BFS to weighted graphs.

8. Quick Self-Check

1. Why must you test goal on popping, not generating?
2. When does UCS behave exactly like BFS?