UI logo
CS 440/ECE 448
Margaret Fleck

Uninformed Search 2


Our first few search algorithms will be uninformed. That is, they rely only on computed distances from the starting state. Next week, we'll see \(A^*\)). It's an informed search algorithm because it also uses an estimate of the distance remaining to reach the goal.

Basic search outline

A state is exactly one of

Basic outline for search code

Loop until we find a solution

Data structure for frontier determines type of search

BFS example

Let's find a route from Easthampton to Whately Using BFS. The actual best route is via Northampton, Florence, Hatfield (19 miles)

The frontier is stored as a queue. So we explore locations in rings, gradually moving outwards from the starting location. Let's assume we always explore edges counterclockwise (right to left)

Start
Easthampton
Add neighbors of Easthampton
South Hadley, Northampton, Westhampton
Add neighbors of South Hadley
Amherst, Hadley [Northampton is already seen]
Add neighbors of Northampton
Florence, Westhampton
Add neighbors of Westhampton
Williamsburg, Chesterfield
Add neighbors of Amherst
... FOUND WHATELY

We return the path Easthampton, South Hadley, Amherst, Whately (length 34). This isn't the shortest path by mileage, but it's one of the shortest paths by number of edges.

BFS properties:

Here is a fun animation of BFS set to music.

DFS example

The frontier is stored as a stack (explicitly or implicitly via recursive function calls). Again, we'll explore edges counterclockwise. The frontier looks like:

Start
Easthampton
Add neighbors of Easthampton
South Hadley, Northampton, Westhampton
Add neighbors of Westhampton
Williamsburg, Chesterfield
Add neighbors of Chesterfield
Goshen
Add neighbors of Goshen
... FOUND WHATELY

We return the path: Westhampton, Chesterfield, Goshen, Whately (length 38)

DFS properties:

Animation of DFS set to music. Compare this to the one for BFS.

Basic tricks

There are several basic tricks required to make DFS and BFS work right. First, store the list of seen states, so that your code can tell when it has returned to a state that has already been explored. Otherwise, your code may end up in an infinite loop and/or be massively inefficient.

Second, return as soon as a goal state has been found. The entire space of states may be infinite. Even when it is finite, searching the entire set of states is inefficient.

Third, don't use recursion to implement DFS unless paths are known to be short. A small number of programming languages make this safe by optimizing tail recursion. More commonly, each recursive call allocates stack space and you are likely to exceed limits on stack size and/or recursion depth.