✦ScienexySCIENCE KNOWLEDGE LIBRARY
Science reference · SCI-CS-003-036

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

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.

Variables

SymbolMeaning

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