Stanford CS221 | Autumn 2025 | Lecture 6: Search II

Why It Matters

UCS guarantees optimal solutions for non‑negative cost graphs, forming the theoretical backbone of modern heuristic search methods such as A* used across AI and operations research.

Key Takeaways

• Uniform Cost Search expands nodes by increasing past cost.
• UCS handles cycles using a priority queue and non‑negative edges.
• Past cost equals priority, guaranteeing optimal path under assumptions.
• A* is essentially UCS with an admissible heuristic added.
• Visualizing UCS shows uniform expansion from start toward goal.

Summary

The lecture revisits search problems, introducing Uniform Cost Search (UCS) as an exact algorithm capable of handling cycles, and briefly foreshadows its relationship to A*.

Key concepts include the distinction between past cost (minimum cost from start) and future cost (minimum cost to goal). UCS processes states in order of increasing past cost using a priority queue, ensuring optimality when edge costs are non‑negative. The professor walks through a concrete graph example (A‑B‑C‑D) and a grid navigation problem, illustrating frontier updates, back‑pointers, and the proof that the priority equals past cost.

Notable moments feature the step‑by‑step expansion of nodes, the handling of duplicate frontier entries (e.g., updating C’s cost from 100 to 2), and a visual animation of UCS expanding uniformly across a large pixel‑grid. The instructor also emphasizes that A* can be viewed as UCS augmented with an admissible heuristic, linking the two algorithms conceptually.

The implications are clear: UCS provides a reliable foundation for optimal pathfinding in AI, especially when cycles exist, and its principles underlie more sophisticated heuristics like A*. Understanding UCS equips practitioners to design efficient search strategies for robotics, routing, and game AI.

Original Description

For more information about Stanford’s Artificial Intelligence professional and graduate programs, visit: https://stanford.io/ai

To learn more about enrolling in this course, visit: https://online.stanford.edu/courses/cs221-artificial-intelligence-principles-and-techniques

Please follow along with the course schedule: https://stanford-cs221.github.io/autumn2025/

Follow the playlist: https://youtube.com/playlist?list=PLoROMvodv4rMeDqwS1yFl3j3sR_-MQNEN&si=bVivXjDfVEQKky1D

Teaching Team

Percy Liang, Associate Professor of Computer Science (and courtesy in Statistics)