CS 440/ECE 448

Margaret Fleck

Margaret Fleck

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.

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.

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.