CS 440/ECE 448

Margaret Fleck

Margaret Fleck

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.

A state is exactly one of

- not yet seen (can be a very large set in some applications)
- frontier, i.e. seen but we haven't explored its outgoing edges
- completely done (all outgoing edges followed)

Basic outline for search code

Loop until we find a solution

- take a state off frontier
- follow outgoing edges to find neighbors
- add neighbors to frontier if not already seen

Data structure for frontier determines type of search

- BFS: queue
- DFS: stack (or implicit stack via recursion)
- UCS (uniform cost search) and \(A^*\): priority queue

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:

- Solution is always optimal if and only if all edges have same cost.
- Frontier can get very large, often grows linearly with distance outwars from start.

Here is a fun animation of BFS set to music.

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:

- Solution can be very far from optimal.
- Frontier stays small.
- Not guaranteed to find the goal even if it's reachable

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

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.