CS 440/ECE 448
Margaret Fleck

## Uniform-cost search

Breadth-first search only returns an optimal path if all edges have the same cost (e.g. length). Uniform-cost search (UCS) is a similar algorithm that finds optimal paths even when edge costs vary.

Recall that the frontier in a search algorithm contains states that have been seen but their outgoing edges have not yet been explored. BFS stores the frontier as a queue; DFS stores it as a stack. Uniform-cost search stores the frontier as a priority queue. So, in each iteration of our loop, we explore neighbors of the best state (i.e. lowest cost, shortest path) seen so far.

From now on, we will assume that

• edge costs are always positive, and
• all edge costs are >= b, where b is some minimum non-zero cost.

These assumptions are almost always true. If they aren't true, algorithm design and analysis can get much harder in ways that are beyond the scope of this class.

## The details

When we're using BFS on a problem where all edges have the same cost, we can safely return as soon as we see a goal state. There's no need to put the goal state back into the frontier for further processing. However, consider the following example:

Suppose we are going from Westhampton to Florence in the road graph below. When we look at Westhampton's neighbors, Williamsburg is closer than Northampton. So we'll first get to Florence via Williamsburg, a route that takes 15 miles. However, the best route is 12 miles, via Northampton.

Evidently, this method of finishing up our search doesn't guarantee an optimal path when edge costs vary. So we need to make a couple changes to ensure that we have really found the best path when we halt and declare success:

• When exploring a state, neighbors are put into the frontier even if they are goal states.
• We stop when goal state reaches the top of the priority queue, not when it is first seen.
• When we re-discover a state (i.e. via a different path), we update our record of its path length.

Also notice that our representation of a state should include the cost to reach it, along the best path seen so far. Computing this dynamically would be very slow.

## Longer Example

As an example, consider going from Easthampton to Hatfield in our road map.

As with any of these search algorithms, our priority queue starts off containing Easthampton and we then remove Easthampton from the frontier and add its neighbors. However, since we're doing UCS, we add the neighbors in order of distance, not some arbitrary search ordering (e.g. left to right). Our search (states with distances) now looks like this:

  DONE
Easthampton 0

FRONTIER
Northampton 6
Westhampton 10


  DONE
Easthampton 0
Northampton 6

FRONTIER
Florence 8
Westhampton 10  <-- Not clear if it's before or after Hadley


  DONE
Easthampton 0
Northampton 6
Florence 8

FRONTIER
Westhampton 10
Hatfield 13    <-- GOAL!  But don't stop yet
Williamsburg 14


We have a path to Hatfield, but we can't yet be sure that it's the best one. So we keep going, exploring routes outwards from Westhampton, Hadley, and South Hadley.

  DONE
Easthampton 0
Northampton 6
Florence 8
Westhampton 10

FRONTIER
Hatfield 13  <-- GOAL
Williamsburg 14
Amherst 14
Chesterfield 19


Now our goal is at the top of the priority queue, so there can't be a better path. So we return the path: Easthampton, Northampton, Florence, Hatfield.