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:
- Insert the initial state into the priority queue with cost 0
- Pop the node with the lowest path cost
- If it's the goal, return the solution
- Otherwise, expand it: generate successors and insert them with their cumulative path costs
- 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.