Home

# Uninformed search

We learned in the Search lecture notes that search problems have the following components: an initial state, possible actions, a transition model that describes how actions change one state to another, a goal criteria, and a way of calculating the cost of a sequence of actions (a “path” cost). We do not use the path cost when executing uninformed search.

The transition model defines a state space, which can be represented as a directed graph (vertices are states, edges are actions).

For example, consider the 8-puzzle game, which requires that tokens are shifted around until a particular goal state is reached.

Each “state” is a configuration of the puzzle. Each state can be followed by at most four other states, resulting from moving a neighboring token left, right, up, or down into the space (thus shifting the space). If the space is on an edge or in a corner, fewer than four movements are possible.

## Generic search algorithm

All searches essentially follow the same algorithm:

```1. create a list called "tocheck" of states to check
- put the initial state in this list

2. loop:
a. if the "tocheck" list is empty:
- oh no! we have nothing left to check, and we never found a
goal state! we'll have to quit with "no solution"

b. otherwise, pull a state from the "tocheck" list, ensuring that
we have not yet checked this state

i. if this state is a goal state, we're done (return this state)

ii. otherwise,
- find the next states accessible from this state
- put each next state in the "tocheck" list
- repeat the loop
```

We see that whenever the search algorithm discovers a state is not a goal state, all accessible states are calculated and added to the “tocheck” list. This “tocheck” list typically grows quite rapidly. However, rarely do we check every state in the “tocheck” list. In fact, the different varieties of search differ almost only in how they process this “tocheck” list, as we will see.

## Random search

A random search, while never practical as far as I know, is nevertheless interesting to consider as a worst case search. To program this search, modify step `2.b.` so that a random “tocheck” state is chosen. Given enough time, the goal state should be found, but a random search will probably take more time (more states are checked) than any other method.

In breadth-first search (BFS), we want to check all states (which we’ll call “children states”) accessible from the previous state (the “parent state”) before we check states accessible from the children. So if some state is to be checked, say state X, and there are 15 children of state X, then we will check all of those 15 children before checking any of their children.

Breadth-first search appears to search horizontally before searching vertically.

To implement BFS, modify step `2.b.` to pick out of the “tocheck” list the state that was added first. This means that earlier-discovered states are checked first. For example, the children of the initial state are checked before the their children, because the children of the initial state are discovered earlier. The “tocheck” list in BFS is essentially a queue.

Here is an example of BFS operating on the 8-puzzle:

## Depth-first search

A trivial change to breadth-first search gives us depth-first search (DFS). For DFS, modify step `2.b.` to pick out of the “tocheck” list the state that was added last. So in DFS, the “tocheck” list is essentially a stack. The purpose is to check the initial state’s first discovered child, and then that child’s first child, etc. before checking the initial state’s second child. DFS appears to search vertically before it searches horizontally.

### Iterative-deepening depth-first search

Depending on the search problem, DFS may go off into “never-never-land,” seemingly never arriving at a goal state, while say, BFS, arrives at the solution rather quickly. We see this behavior in the 8-puzzle problem because DFS just keeps trying moves that are built off prior moves until it either repeats a state (somewhat unlikely; there are 9! = 362,880 states) or finds the goal. If the true goal is only five moves away from the initial state, then BFS will find this goal in less than 1024 checks while DFS may require, well, 362,880 checks.

To solve the problem of DFS going to “deep” into “never-never-land,” we can put a limit on the depth of DFS. Step `2.b.ii.` is modified so that only states that have depth less than some constant are added to the “tocheck” list. The depth is calculated as the number of actions that have been applied to the initial state.

Because it is often difficult to know what the correct depth limit is, the iterative-deepening depth-first search (IDDFS if you like) first tries DFS with depth limit 1; if no goal state is found, DFS is run again with depth limit 2; and so on, until the goal state is found.