Uniform-Cost Search is an uninformed search strategy that selects for expansion the frontier node with the smallest path cost from the initial state. The path cost, commonly written as g(n), is the sum of the step costs along the path leading to node n. UCS uses a priority queue ordered by this accumulated cost. When a lower-cost path to a state is discovered, the frontier entry may need to be updated. The algorithm checks for a goal when the lowest-cost frontier node is removed for expansion, rather than merely when a goal is first generated. Under nonnegative step costs and suitable conditions, this ensures that the first goal removed from the priority queue has minimum path cost. UCS is complete when step costs are bounded below by a positive value and a finite-cost solution exists. Its performance depends on the distribution of path costs and the number of nodes with costs below the optimal solution cost. It is particularly useful when different actions have different costs and no reliable heuristic is available.
Uniform-Cost Search
Uniform-Cost Search (UCS) expands the frontier node with the lowest accumulated path cost from the initial state.
g(n) = Σ c(aᵢ); UCS selects n = arg min g(n)
Explanation
Variables
| Symbol | Meaning |
|---|---|
g(n) | The accumulated cost of the path from the initial state to node n. |
c(aᵢ) | The cost of an individual action or transition. |
Priority Queue | A data structure that returns the frontier node with the lowest priority value. |
Example or application
Suppose a route from A to D can be taken through A → B → D with costs 4 and 8, or through A → C → D with costs 3 and 2. UCS compares total costs of 12 and 5 and selects the second route as the lower-cost solution.
Text
Unlike BFS, which prioritizes depth, UCS prioritizes total cost so far. It typically uses a priority queue and is suitable when actions have different nonnegative costs.
Key Points
UCS expands the frontier node with the lowest accumulated path cost.
It uses a priority queue.
It can handle different nonnegative action costs.
The goal test should be applied when a node is removed from the priority queue.
It finds a minimum-cost solution under its standard assumptions.
Applications
Route planning with different travel costs
Network routing with nonnegative link costs
Resource-aware planning
Weighted graph pathfinding
Cost-sensitive state-space search
Learning Outcomes
Explain how UCS selects the next node.
Calculate accumulated path costs.
Distinguish UCS from BFS when step costs differ.
Practice Questions
What value does UCS minimize?
Why does UCS use a priority queue?
When should UCS check whether a removed node is the goal?
Related Concepts
Breadth-First Search
Priority Queue
Path Cost
A* Search Algorithm
Common Mistakes
Choosing the node with the smallest individual edge cost instead of the smallest accumulated path cost.
Stopping as soon as a goal is generated.
Assuming UCS and BFS behave identically when edge costs differ.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Russell, S. and Norvig, P. Artificial Intelligence: A Modern Approach, uninformed search algorithms.
- Poole, D. and Mackworth, A. Artificial Intelligence: Foundations of Computational Agents, search methods.
Suggest a correction or source · More in Artificial Intelligence & Machine Learning