What is Uniform-Cost Search?

Uniform-Cost Search is a search algorithm used when actions have different costs — that is, when moving from one state to another does not always cost the same (unlike BFS).

 Example — Romania Map (from Figure )

We want to go from Sibiu → Bucharest.

Connections and their costs (distances):

From	To	Cost
Sibiu	Rimnicu Vilcea	80
Sibiu	Fagaras	99
Rimnicu Vilcea	Pitesti	97
Fagaras	Bucharest	211
Pitesti	Bucharest	101

Step-by-Step Explanation

Step 1: Start from Sibiu

Successors:

• Rimnicu Vilcea (cost = 80)
• Fagaras (cost = 99)

The lowest-cost node is Rimnicu Vilcea (80).

Step 2: Expand Rimnicu Vilcea

From Rimnicu Vilcea → Pitesti
New cost = 80 + 97 = 177

Now we have these paths in the frontier:

• Fagaras (cost 99)
• Pitesti (cost 177)

 The least-cost node is Fagaras (99).

Step 3: Expand Fagaras

From Fagaras → Bucharest
New cost = 99 + 211 = 310

Now the frontier has:

• Pitesti (177)
• Bucharest (310)

Even though Bucharest is the goal, we do not stop yet.
Uniform-Cost Search checks for a goal only when expanding a node, not when generating one.

So, next we expand Pitesti (177) because it’s cheaper.

Step 4: Expand Pitesti

From Pitesti → Bucharest

New cost=177+101=278

That is

Now we have a better path to Bucharest than before (278 < 310).

So UCS replaces the previous higher-cost path.

Step 5: Expand Bucharest (278)

Now Bucharest is the lowest-cost node in the frontier, and it’s the goal.

Algorithm stops.
The path found (via Rimnicu Vilcea → Pitesti) is the optimal (lowest cost) path.

Key Idea

Uniform-Cost Search expands nodes in order of increasing path cost
—not by depth (like BFS), and not by heuristic (like A*).

Complexity

Let:

• C* = cost of the optimal solution (smallest total path cost)
• ε = smallest positive step cost

Then:

This means UCS can explore many low-cost paths before finding the right one.

When all step costs are equal (like 1 per move), UCS behaves just like BFS.

Properties of Uniform-Cost Search

Property	Description
Complete	Yes, it always finds a solution if one exists (assuming positive costs).
Optimal	Yes, it always finds the least-cost path.
Time & Space	Can be large (depends on cost distribution).
Type	Uninformed search (no heuristic).