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
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.
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:
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.
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
South Hadley 11
Now we add Northampton's neighbors:
DONE
Easthampton 0
Northampton 6
FRONTIER
Florence 8
Westhampton 10 <-- Not clear if it's before or after Hadley
Hadley 10
South Hadley 11
Now we add Florence's neighbors:
DONE
Easthampton 0
Northampton 6
Florence 8
FRONTIER
Westhampton 10
Hadley 10
South Hadley 11
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
Hadley 10
South Hadley 11
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.
UCS returns an optimal path even if edge costs vary. Memory requirements for UCS are similar to BFS. They can be worse than BFS in some cases, because UCS can get stuck in extended areas of short edges rather than exploring longer but more promising edges.
You may have seen Dijkstra's algorithm in data structures class. It is basically similar to UCS, except that it finds the distance from the start to all states rather than stopping when it reaches a designated goal state.