Uniform-Cost Search Algorithm

Uniform Cost Search (UCS) in AI is a fundamental search algorithm used to find the least-cost path in a state space where actions have different costs. It is widely taught in artificial intelligence courses and frequently appears in university exams and technical interviews.

Uniform Cost Search belongs to the family of uninformed search strategies, meaning it does not use heuristics and relies only on path cost.

What is Uniform Cost Search (UCS)?

Uniform Cost Search is an uninformed search algorithm that expands the node with the lowest cumulative path cost using a priority queue, guaranteeing an optimal solution when all step costs are non-negative.

This definition is central to understanding the uniform cost search algorithm and is commonly used in exams and AI theory explanations.

How Uniform Cost Search Works

Uniform Cost Search explores the search space by always choosing the cheapest path so far, rather than the shallowest path.

Step-by-Step UCS Algorithm

1. Insert the start node into the priority queue with path cost = 0

2. Use a priority queue (min-heap) ordered by cumulative path cost

3. Remove the node with the lowest total cost

4. Expand the node and generate its successors

5. Add successors to the queue with updated path costs

6. Repeat until the goal node is dequeued

The algorithm stops only when the goal node is removed from the priority queue, ensuring optimality.

Master AI Search Algorithms

Learn the math and logic behind UCS, A*, and other advanced algorithms in Scaler's Data Science & Machine Learning Course.

Data Structure Used in Uniform Cost Search

Priority Queue (Min-Heap)

Uniform Cost Search uses a priority queue, where nodes are ordered based on their cumulative path cost, not insertion order.

This is why UCS works correctly on weighted graphs.

Why BFS Fails on Weighted Graphs

Breadth-First Search (BFS) uses a FIFO queue and assumes all edges have equal cost. In weighted graphs:

• BFS may find a shorter path in terms of steps

• But not the minimum-cost path

UCS fixes this limitation by always expanding the lowest-cost path first.

Uniform Cost Search Example (Solved)

Weighted Graph Example

Assume the following graph:

• Start node: A

• Goal node: G

Edges and costs:

• A → B (1)

• A → C (4)

• B → D (2)

• B → G (6)

• C → G (1)

• D → G (3)

Step-by-Step UCS Execution (Queue State)

Optimal Path: A → C → G    Total Cost: 5

This example clearly shows how uniform cost search prioritizes cost over depth.

Properties of Uniform Cost Search

Uniform Cost Search is both complete and optimal, provided all step costs are non-negative.

Time and Space Complexity of UCS

Time Complexity

O(b^(C/ε))*

Where:

• b = branching factor

• C** = cost of the optimal solution

• ε = minimum step cost

This means UCS may explore many nodes with cost less than the optimal solution. You can learn more about time complexity calculations here.

Space Complexity

Same as time complexity

UCS stores all generated nodes in memory because it keeps the entire frontier in the priority queue.

In simple terms:    Uniform Cost Search is memory-intensive.

Uniform Cost Search vs Other Algorithms

This comparison is frequently tested in AI exams and interviews.

When Should You Use Uniform Cost Search?

Use uniform cost search in AI when:

• The graph is weighted

• No heuristic information is available

• Finding the least-cost path is more important than speed

• You need a guaranteed optimal solution

Avoid UCS when memory is limited or when a good heuristic exists (A* is better then).

Applications of Uniform Cost Search

Uniform Cost Search is used in:

• Route planning with varying travel costs

• AI planning problems

• Pathfinding in weighted environments

• Cost-based decision-making systems

It forms the conceptual foundation for advanced algorithms like A*.