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

• 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

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:

• 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.

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:

• 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.

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.