Course contentsShow
← Computer Science
Lesson 2746 of 2,87261. AI and Search AlgorithmsFree lesson

Uniform-Cost Search

Expands lowest path-cost nodes first using priority queue for weighted graphs.

Uniform-Cost Search

What You'll Learn

You'll learn how Uniform-Cost Search (UCS) guarantees finding the lowest-cost path in weighted graphs by always expanding the cheapest node first.


The Core Idea

Unlike Breadth-First Search, which treats all edges equally, Uniform-Cost Search recognizes that edges can have different costs (weights). UCS ensures you find the cheapest path to the goal by always exploring the node with the lowest total path cost from the initial state.

Think of it like planning a road trip: BFS would explore all cities one highway exit away, then two exits away, etc. UCS, however, explores cities based on actual distance traveled—if one route is 50 miles and another is 30 miles, you'd explore the 30-mile destination first, even if it required more turns.


How It Works

UCS maintains the frontier as a priority queue ordered by path cost g(n), where g(n) is the cost from the initial state to node n.

Algorithm steps:

  1. Insert the initial state into the priority queue with cost 0
  2. Pop the node with the lowest path cost
  3. If it's the goal, return the solution
  4. Otherwise, expand it: generate successors and insert them with their cumulative path costs
  5. Repeat until the goal is found or the frontier is empty

Key properties:

  • Complete: Yes, if all step costs are positive
  • Optimal: Yes, always finds the lowest-cost solution
  • Time/Space complexity: O(b^(C*/ε)) where C* is the optimal cost and ε is the minimum step cost

Key Takeaway:
Uniform-Cost Search guarantees the optimal solution in weighted graphs by using a priority queue to expand nodes in order of increasing path cost.